Java数据结构之平衡二叉树的实现详解

定义

动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子树尽可能平衡。

平衡二叉树（AVL树）：称一棵二叉查找树为高度平衡树，当且仅当或由单一外结点组成，或由两个子树形 Ta 和 Tb 组成，并且满足：

|h(Ta) - h(Tb)| <= 1，其中 h(T) 表示树 T 的高度 Ta 和 Tb 都是高度平衡树

即：每个结点的左子树和右子树的高度最多差 1 的二叉查找树。

设 T 为高度平衡树中结点 q 的平衡系数为 q 的右子树高度减去左子树高度高度平衡树所以结点的平衡系数只可能为：-1, 0, 1

结点结构

key：关键字的值

value：关键字的存储信息

height：树的高度（只有一个结点的树的高度为1）

left：左子树根结点的的引用

right：右子树根结点的引用

class AVLNode<K extends Comparable<K>, V> {
  public K key;
  public V value;
  public int height;
  public AVLNode<K, V> left;
  public AVLNode<K, V> right;

  public AVLNode(K key, V value, int height) {
      this.key = key;
      this.value = value;
      this.height = height;
  }
}

查找算法

同二叉查找树的查找算法： Java数据结构之二叉查找树的实现

插入算法

AVL 树是一种二叉查找树，故可以使用二叉查找树的插入方法插入结点，但插入一个新结点时，有可能破坏 AVL 树的平衡性。

如果发生这种情况，就需要在插入结点后对平衡树进行调整，恢复平衡的性质。实现这种调整的操作称为[旋转]。

在插入一个新结点 X 后，应调整失去平衡的最小子树，即从插入点到根的路径向上找第一个不平衡结点 A。

平衡因子：该结点的左子树高度和右子树高度的差值。如果差值的绝对值小于等于1，则说明该结点平衡，如果差值的绝对值为2（不会出现其他情况），则说明该结点不平衡，需要做平衡处理。

造成结点 A 不平衡的的原因以及调整方式有以下几种情况。

LL 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点左子结点的左子结点，所以为 LL 型。

扁担原理：右旋

将 A 的左孩子 B 提升为新的根结点；将原来的根结点 A 降为 B 的右孩子；各子树按大小关系连接(BL 和 AR 不变，BR 调整为 A 的左子树)。高度调整：由于调整后 B 的高度依赖于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

    private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
      AVLNode<K, V> b = a.left;
      a.left = b.right;
      b.right = a;
      a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
      b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
      return b;
  }

RR 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点右子结点的右子结点，所以为 RR 型。

扁担原理：左旋

将 A 的右孩子 B 提升为新的根结点；将原来的根结点 A 降为 B 的左孩子；各子树按大小关系连接(AL 和 BR 不变，BL 调整为 A 的右子树)。高度调整：由于调整后 B 的高度依赖于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

    private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
      AVLNode<K, V> b = a.right;
      a.right = b.left;
      b.left = a;
      a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
      b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1;
      return b;
  }

LR 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点左子结点的右子结点，所以为 LR 型。

从旋转的角度：对 B 左旋，然后对 A 右旋将 B 的左孩子 C 提升为新的根结点；将原来的根结点 A 降为 C 的右孩子；各子树按大小关系连接(BL 和 AR 不变，CL 和 CR 分别调整为 B 的右子树和 A 的左子树)。

    private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
      a.left = leftRotate(a.left);   // 对 B 左旋
      return rightRotate(a);         // 对 A 右旋
  }

RL 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点右子结点的左子结点，所以为 RL 型。

从旋转的角度：对 B 右旋，然后对 A 左旋将 B 的左孩子 C 提升为新的根结点；将原来的根结点 A 降为 C 的左孩子；各子树按大小关系连接(AL 和 BR 不变，CL 和 CR 分别调整为 A 的右子树和 B 的左子树)。

    private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
      a.right = rightRotate(a.right);
      return leftRotate(a);
  }

插入方法

根结点默认高度为1

某结点的左右子树高度差的绝对值为2，则需要进行平衡处理

I.左子树高

key小于root.left.key：LL型，进行右旋

key大于root.left.key：LR型，进行左右旋

II.右子树高

key大于root.right.key：RR型，进行左旋

key小于root.right.key：RR型，进行右左旋

    public void insert(K key, V value) {
      root = insert(root, key, value);
  }

  private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
      if (t == null) {
          return new AVLNode<>(key, value, 1);
      } else if (key.compareTo(t.key) < 0) {
          t.left = insert(t.left, key, value);
          t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
          // 平衡因子判断
          if (getHeight(t.left) - getHeight(t.right) == 2) {
              if (key.compareTo(root.left.key) < 0) // 左左：右旋
                  t = rightRotate(t);
              else                                 // 左右：先左旋，再右旋
                  t = leftRightRotate(t);
          }
      } else if (key.compareTo(t.key) > 0) {
          t.right = insert(t.right, key, value);
          t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
          // 平衡因子判断
          if (getHeight(t.left) - getHeight(t.right) == -2) {
              if (key.compareTo(root.right.key) > 0) // 右右：左旋
                  t = leftRotate(t);
              else                                  // 右左：先右旋，再左旋
                  t = rightLeftRotate(t);
          }
      } else {
          t.value = value;
      }
      return t;
  }

删除算法

概述

可采用二叉查找树的删除算法进行删除。 Java 数据结构之二叉查找树的实现删除某结点 X 后，沿从 X 到根节点的路径上考察沿途结点的平衡系数，若第一个不平衡点为 A，平衡以 A 为根的子树。平衡后，可能使子树 A 高度变小。这样可能导致 A 的父节点不满足平衡性。所以要继续向上考察结点的平衡性，最远可能至根结点，即最多需要做O(logn)次旋转。对比[插入]操作：平衡 A 后，子树高度不变，A 子树以外的结点不受影响，即插入最多涉及O(1)次旋转。

实例分析

下面举个删除的例子：

删除以下平衡二叉树中的 16 结点

16 为叶子，将其删除即可，如下图。

指针 g 指向实际被删除节点 16 之父 25，检查是否失衡，25 节点失衡，用 g 、u 、v 记录失衡三代节点（从失衡节点沿着高度大的子树向下找三代），判断为 RL 型，进行 RL 旋转调整平衡，如下图所示。

继续向上检查，指针 g 指向 g 的双亲 69，检查是否失衡，69 节点失衡，用 g 、u 、v 记录失衡三代节点，判断为 RR 型，进行 RR 旋转调整平衡，如下图所示。

代码

代码描述：

1.若当前结点为空，则返回该节点

2.若关键值小于当前结点的关键值，则递归处理该结点的左子树

3.若关键值大于当前结点的关键值，则递归处理该结点的右子树

4.若关键值等于当前结点的关键值

若当前结点的左子树为空，则返回该结点的右子树根节点若当前结点的右子树为空，则返回该结点的左子树根节点若当前结点左右子树都不为空，则找到该结点的中序前驱结点（该结点左子树的最右结点）或中序后继结点（该结点右子树的最左结点），将其值赋予该结点，然后递归删除中序前驱或后继结点。

5.更新结点高度

6.若该结点左子树高度更高，且处于不平衡状态

若为 LL 型，进行右旋若为 LR 型，先左旋，再右旋

7.若该结点右子树高度更高，且处于不平衡状态

若为 RL 型，先右旋，再左旋若我 RR 型，进行左旋

8.返回该结点

    public void remove(K key) {
      this.root = delete(root, key);
  }

  public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
      if (t == null) return t;
      if (key.compareTo(t.key) < 0) {
          t.left = delete(t.left, key);
      }
      else if (key.compareTo(t.key) > 0) {
          t.right = delete(t.right, key);
      }
      else {
          if(t.left == null) return t.right;
          else if(t.right == null) return t.left;
          else {         // t.left != null && t.right != null
              AVLNode<K, V> pre = t.left;
              while (pre.right != null) {
                  pre = pre.right;
              }
              t.key = pre.key;
              t.value = pre.value;
              t.left = delete(t.left, t.key);
          }
      }
      if (t == null) return t;
      t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
      if(getHeight(t.left) - getHeight(t.right) >= 2) {
          if(getHeight(t.left.left) > getHeight(t.left.right)) {
              return rightRotate(t);
          } else {
              return leftRightRotate(t);
          }
      }
      else if(getHeight(t.left) - getHeight(t.right) <= -2) {
          if(getHeight(t.right.left) > getHeight(t.right.right)) {
              return rightLeftRotate(t);
          }
          else {
              return leftRotate(t);
          }
      }
      return t;
  }

完整代码

class AVLNode<K extends Comparable<K>, V> {
  public K key;
  public V value;
  public int height;
  public AVLNode<K, V> left;
  public AVLNode<K, V> right;

  public AVLNode(K key, V value, int height) {
      this.key = key;
      this.value = value;
      this.height = height;
  }
}

class AVLTree<K extends Comparable<K>, V> {

  public AVLNode<K, V> root;

  public int getHeight(AVLNode<K, V> t) {
      return t == null ? 0 : t.height;
  }

  public void insert(K key, V value) {
      root = insert(root, key, value);
  }

  public void remove(K key) {
      this.root = delete(root, key);
  }

  public AVLNode<K, V> delete(AVLNode<K, V> t, K key) {
      if (t == null) return t;
      if (key.compareTo(t.key) < 0) {
          t.left = delete(t.left, key);
      }
      else if (key.compareTo(t.key) > 0) {
          t.right = delete(t.right, key);
      }
      else {
          if(t.left == null) return t.right;
          else if(t.right == null) return t.left;
          else {         // t.left != null && t.right != null
              AVLNode<K, V> pre = t.left;
              while (pre.right != null) {
                  pre = pre.right;
              }
              t.key = pre.key;
              t.value = pre.value;
              t.left = delete(t.left, t.key);
          }
      }
      if (t == null) return t;
      t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
      if(getHeight(t.left) - getHeight(t.right) >= 2) {
          if(getHeight(t.left.left) > getHeight(t.left.right)) {
              return rightRotate(t);
          } else {
              return leftRightRotate(t);
          }
      }
      else if(getHeight(t.left) - getHeight(t.right) <= -2) {
          if(getHeight(t.right.left) > getHeight(t.right.right)) {
              return rightLeftRotate(t);
          }
          else {
              return leftRotate(t);
          }
      }
      return t;
  }


  private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) {
      if (t == null) {
          return new AVLNode<>(key, value, 1);
      }
      if (key.compareTo(t.key) < 0) {
          t.left = insert(t.left, key, value);
          // 平衡因子判断
          if (getHeight(t.left) - getHeight(t.right) == 2) {
              if (key.compareTo(t.left.key) < 0) // 左左：右旋
                  t = rightRotate(t);
              else                                  // 左右：先左旋，再右旋
                  t = leftRightRotate(t);
          }
      } else if (key.compareTo(t.key) > 0) {
          t.right = insert(t.right, key, value);
          // 平衡因子判断
          if (getHeight(t.left) - getHeight(t.right) == -2) {
              if (key.compareTo(t.right.key) > 0) // 右右：左旋
                  t = leftRotate(t);
              else                                   // 右左：先右旋，再左旋
                  t = rightLeftRotate(t);
          }
      } else {
          t.value = value;
      }
      t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1;
      return t;
  }

  private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) {
      a.right = rightRotate(a.right);
      return leftRotate(a);
  }

  private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) {
      a.left = leftRotate(a.left);
      return rightRotate(a);
  }

  private AVLNode<K, V> leftRotate(AVLNode<K, V> a) {
      AVLNode<K, V> b = a.right;
      a.right = b.left;
      b.left = a;
      a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
      b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
      return b;
  }

  private AVLNode<K, V> rightRotate(AVLNode<K, V> a) {
      AVLNode<K, V> b = a.left;
      a.left = b.right;
      b.right = a;
      a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1;
      b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1;
      return b;
  }

  private void inorder(AVLNode<K, V> root) {
      if (root != null) {
          inorder(root.left);
          System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
          inorder(root.right);
      }
  }

  private void preorder(AVLNode<K, V> root) {
      if (root != null) {
          System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
          preorder(root.left);
          preorder(root.right);
      }
  }

  private void postorder(AVLNode<K, V> root) {
      if (root != null) {
          postorder(root.left);
          postorder(root.right);
          System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") ");
      }
  }

  public void postorderTraverse() {
      System.out.print("后序遍历：");
      postorder(root);
      System.out.println();
  }

  public void preorderTraverse() {
      System.out.print("先序遍历：");
      preorder(root);
      System.out.println();
  }

  public void inorderTraverse() {
      System.out.print("中序遍历：");
      inorder(root);
      System.out.println();
  }
}

方法测试

    public static void main(String[] args) {
      AVLTree<Integer, Integer> tree = new AVLTree<>();
      tree.insert(69, 1);
      tree.insert(25, 1);
      tree.insert(80, 1);
      tree.insert(16, 1);
      tree.insert(56, 1);
      tree.insert(75, 1);
      tree.insert(90, 1);
      tree.insert(30, 1);
      tree.insert(78, 1);
      tree.insert(85, 1);
      tree.insert(98, 1);
      tree.insert(82, 1);

      tree.remove(16);
      tree.preorderTraverse();
      tree.inorderTraverse();
      tree.postorderTraverse();
  }

输出

先序遍历：(key: 80 , value: 1 , height: 4) (key: 69 , value: 1 , height: 3) (key: 30 , value: 1 , height: 2) (key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 85 , value: 1 , height: 2) (key: 82 , value: 1 , height: 1) (key: 98 , value: 1 , height: 1)
中序遍历：(key: 25 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 56 , value: 1 , height: 1) (key: 69 , value: 1 , height: 3) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 80 , value: 1 , height: 4) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 90 , value: 1 , height: 3) (key: 98 , value: 1 , height: 1)
后序遍历：(key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 69 , value: 1 , height: 3) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 98 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 80 , value: 1 , height: 4)

以上就是Java数据结构之平衡二叉树的实现详解的详细内容，更多关于Java平衡二叉树的资料请关注其它相关文章！

原文链接：https://www.cnblogs.com/gonghr/p/16064797.html

查看更多关于Java数据结构之平衡二叉树的实现详解的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://www.haodehen.cn/did193817

更新时间：2023-04-25 阅读：14次