ジャバで平衡二分木を実装する方法
バランスのとれた2分木を実現するには、赤黒木やAVL木などの自己調整2分探索木を使用することができる。以下にAVL木を使ってバランスのとれた2分木を実現するコード例を示す。
// AVL树节点类
class Node {
int val;
int height;
Node left;
Node right;
Node(int val) {
this.val = val;
this.height = 1;
} } // 平衡二叉树类 class AVLTree {
private Node root;
// 获取节点的高度
private int getHeight(Node node) {
if (node == null) {
return 0;
}
return node.height;
}
// 更新节点的高度
private void updateHeight(Node node) {
node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
// 获取节点的平衡因子
private int getBalanceFactor(Node node) {
if (node == null) {
return 0;
}
return getHeight(node.left) – getHeight(node.right);
}
// 右旋操作
private Node rightRotate(Node node) {
Node newRoot = node.left;
node.left = newRoot.right;
newRoot.right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 左旋操作
private Node leftRotate(Node node) {
Node newRoot = node.right;
node.right = newRoot.left;
newRoot.left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 平衡节点
private Node balance(Node node) {
if (node == null) {
return null;
}
updateHeight(node);
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1) {
if (getBalanceFactor(node.left) >= 0) {
return rightRotate(node);
} else {
node.left = leftRotate(node.left);
return rightRotate(node);
}
} else if (balanceFactor < -1) {
if (getBalanceFactor(node.right) <= 0) {
return leftRotate(node);
} else {
node.right = rightRotate(node.right);
return leftRotate(node);
}
}
return node;
}
// 插入节点
public void insert(int val) {
root = insert(root, val);
}
private Node insert(Node node, int val) {
if (node == null) {
return new Node(val);
}
if (val < node.val) {
node.left = insert(node.left, val);
} else if (val > node.val) {
node.right = insert(node.right, val);
} else {
// 如果树中已经存在相同值的节点，则不进行插入
return node;
}
return balance(node);
}
// 中序遍历
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.val + ” “);
inorderTraversal(node.right);
} } // 测试代码 public class Main {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(3);
tree.insert(2);
tree.insert(1);
tree.inorderTraversal(); // 输出：1 2 3
} }
平衡2分木の代表的な実装であるAVL木の作成サンプルコードです。ノードの挿入とその再構築、中順巡回の実装を含んでいます。必要に応じて修正、拡張してください。
