AVL(平衡二叉搜索树) - Mahfuzur

21-08-10 banq

在最好的情况下,BST (二叉搜索树 BST 的插入、删除和查找操作)可以提供 O(log n) 的复杂度,但在最坏的情况下,这给我们 O(n) 的复杂度。如果输入数据按任何顺序排序,则可能发生最坏的情况。为了防止最坏的情况,有一些扩展可以帮助我们保持二叉树的平衡并获得最佳结果。他们之中有一些是,

  • AVL树
  • 红黑树
  • 陷阱
  • B树

今天,我们将讨论高度平衡的 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);
      }
    });
  }
}

 

猜你喜欢