在最好的情况下，BST (二叉搜索树 BST 的插入、删除和查找操作)可以提供 O(log n) 的复杂度，但在最坏的情况下，这给我们 O(n) 的复杂度。如果输入数据按任何顺序排序，则可能发生最坏的情况。为了防止最坏的情况，有一些扩展可以帮助我们保持二叉树的平衡并获得最佳结果。他们之中有一些是，
今天，我们将讨论高度平衡的 AVL 树。
AVL 树是二叉搜索树的扩展。它有一个额外的字段，称为平衡因子。在插入、删除或修改操作之后，它总是检查每个节点的平衡因子。
根据平衡因子的值，树自我平衡。这里提供源代码。
平衡系数
AVL 树中节点的平衡因子是该节点左子树的高度与右子树的高度之差。
平衡因子 = 左子树的高度 - 右子树的高度（或逆）
平衡因子的值应始终为 [-1, 0 或 +1]
public class TreeNode<T extends Comparable<T>> {
private T key;
private TreeNode<T> parent;
private TreeNode<T> left;
private TreeNode<T> right;
private int height;
private int balanceFactor;
// getter / setter
public void updateBalanceFactor() {
int left = 0, right = 0;
if (this.left != null) {
left = this.left.height;
}
if (this.right != null) {
right = this.right.height;
}
this.height = Math.max(left, right) + 1;
this.balanceFactor = left - right;
}
public boolean isBalanced() {
return this.getBalanceFactor() <= 1 && this.getBalanceFactor() >= -1;
}
|
我们将为我们的 AVL 树插入和删除方法使用回调模式。
public interface Callback<T> {
void success(T value);
}
|
我们在这里插入和删除操作以维护 AVL 属性。
public class BST<T extends Comparable<T>> {
public void insert(T key, Callback<TreeNode<T>> callback) {
callback.success(node);
}
public void delete(T key, Callback<TreeNode<T>> callback) {
callback.success(node);
}
}
|
AVL 实现：
public class AVL<T extends Comparable<T>> extends BST<T> {
@Override
public void insert(T key, Callback<TreeNode<T>> callback) {
super.insert(key, (node) -> {
fixAVLProperties(node, node.getKey());
if (callback != null) {
callback.success(node);
}
});
}
@Override
public void delete(T key, Callback<TreeNode<T>> callback) {
super.delete(key, (node) -> {
TreeNode<T> parent = node.getParent();
if (parent == null) {
parent = root;
}
updateChildBalanceFactor(parent);
TreeNode<T> unbalancedNode = getUnbalancedNode(parent);
if (unbalancedNode != null) {
T unbalancedKey = getUnbalancedKey(unbalancedNode);
fixAVLProperties(unbalancedNode, unbalancedKey);
}
if (callback != null) {
callback.success(node);
}
});
}
}
|