在最好的情况下,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); } }); } }
|