快捷搜索:  汽车  科技

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)伪代码:(a)LL的旋转,步骤如下:AVL树插入的第一步其实跟二叉查找树一样,但是插入数据后,可能会导致树失去平衡,那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。树失去平衡会有四种情况:AVL树失去平衡之后,可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下:

前言

在《一文彻底掌握二叉查找树,非史上最全总结(多图,附代码) 》我们讲了二叉查找树,在文章的最后我们也提到了,二叉查找树查找的效率受到树的深度的影响,最坏情况是O(N)。而二叉查找树的深度是根据数据插入的顺序不同而表现出不同的。那么有没有可能让树的深度尽可能低,从而提高我们查询的效率呢?答案就是今天要讲的平衡二叉树(AVL树)。

定义

AVL树是二叉查找树的一个特例,所以上一篇文章说到的二叉查找树的定义是AVL树定义的前提。在这个前提之下,AVL树再提出了写更加严格的定义。那就是,树的任意节点的子树的高度差都小于等于1。

树的操作

由于AVL树比普通的二叉查找树有个更加苛刻的要求,要求子树的高度差小于等于1。那么在树的插入、删除等操作时将会比普通的二叉查找树更加麻烦。

插入

AVL树插入的第一步其实跟二叉查找树一样,但是插入数据后,可能会导致树失去平衡,那么这时就需要对子树进行旋转了。通过选择来使得树继续保持平衡。

树失去平衡会有四种情况:

  1. 节点的左儿子的左子树插入节点,导致左子树比右子树高(LL),如下图树插入节点1之后,6的左子树高度比右子树高2。
  2. 节点的右儿子的右子树插入节点,导致右子树比左子树高(RR)
  3. 节点的左儿子的右子树插入节点,导致左子树比右子树高(LR)
  4. 节点的右儿子的左子树插入节点,导致左子树比右子树高(RL)

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)(1)

AVL树失去平衡之后,可以通过旋转使其恢复平衡。四种失去平衡的情况下对应的旋转方法分别如下:

(a)LL的旋转,步骤如下:

  1. 将根节点的左孩子作为新根节点。
  2. 将新根节点的右孩子作为原根节点的左孩子。
  3. 将原根节点作为新根节点的右孩子。

伪代码:

// 要旋转的节点为node,其父节点是parent Node temp = node.left; node.left = temp.right; temp.right = node; parent.left = temp;

LL 旋转示意图如下:

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)(2)

(b)RR的旋转,旋转方法与LL旋转对称,步骤如下:

  1. 将根节点的右孩子作为新根节点。
  2. 将新根节点的左孩子作为原根节点的右孩子。
  3. 将原根节点作为新根节点的左孩子。

RR旋转示意图如下:

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)(3)

(c)LR的旋转:

LR失去平衡的情况,单旋转不能解决问题,需要进行两次旋转,步骤如下:

  1. 根节点的左孩子做一次RR旋转。
  2. 根节点做一次LL旋转。

LR的旋转示意图如下:

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)(4)

(d)RL的旋转:

RL旋转方法与LR旋转对称,步骤如下:

  1. 根节点的右孩子做一次LL旋转。
  2. 根节点做一次RR旋转。

RL的旋转示意图如下:

构建二叉平衡树时怎么旋转(二叉平衡树AVLTree)(5)

删除

平衡二叉树的节点删除操作会比较复杂,我们可以这么分析,左子树上节点的删除相当于我们在右子树上插入了一个新节点,右子树上节点的删除相当于在左子树上插入了一个新节点。我们可以根据这一点进行判断并采取对应的平衡调整操作。

具体做法需要从当前节点判断树是否失去平衡,通过计算左右子树的高度差,判断是哪种失衡。然后运用旋转,将树调整为平衡树。

  1. 排序二叉树的删除
  2. 判断左右子树高度差是否小于2,判断结点是否失衡
  3. 当前结点失衡,将删除视为另一侧的插入,依照插入的旋转思想进行旋转
  4. 如此反复直至根节点

查询

由于AVL树本身就是一颗二叉查找树,所以其节点查询与普通的二叉树没什么两样,这里就不赘述了。如果有不清楚的同学,可以翻看我的上篇文章。

代码

代码我在上篇文章的基础上进行修改,Node类上加入字段height标识子树的高度,比在insert、delete方法上加上判断结构和旋转

public class AVLTree { private Node root; public void insert(int value) { root = insert(root value); } private Node insert(Node x int value) { if (x == null) {// 首次插入 return new Node(value 1); } int xVal = x.value; if (value < xVal) { x.left = insert(x.left value); if (getHeight(x.left) - getHeight(x.right) > 1) {// left if (getHeight(x.left.left) > getHeight(x.left.right)) {// left x = leftLeftRotation(x); } else { x = leftRightRotation(x); } } } else if (value > xVal) { x.right = insert(x.right value); if (getHeight(x.right) - getHeight(x.left) > 1) {// right if (getHeight(x.right.right) > getHeight(x.right.left)) {// right x = rightRightRotation(x); } else { x = rightLeftRotation(x); } } } else { // 重复数据 do nothing } x.height = reCalcHeight(x); return x; } public Node select(int value) { return select(root value);// work when BST is empty } private Node select(Node x int value) { if (x == null) return null; int xVal = x.value; if (value < xVal) return select(x.left value); else if (value > xVal) return select(x.right value); else return x; } public void delete(int value) { root = delete(root value); } private Node delete(Node x int value) { if (x == null) { return null; } int xVal = x.value; if (value < xVal) x.left = delete(x.left value);// 左子树 else if (value > xVal) x.right = delete(x.right value);// 右子树 else { if (x.right == null) { return x.left; } if (x.left == null) { return x.right; } Node temp = x;// 要被删除的节点,先拿着 x = min(temp.right); // 获取右子树最小的节点 x.right = deleteMin(temp.right);// 删除右子树最小节点,并将删除后的树作为x的右子树 x.left = temp.left;// 原来的左子树保持,作为新根节点的左子树 } // 删除完成,调整平衡性 x.height = reCalcHeight(x); // 失衡 if (getHeight(x.left) - getHeight(x.right) >= 2) { // 删除发生在右子树,模拟插入发生在左子树 if (getHeight(x.left.left) > getHeight(x.left.right)) { // 插入发生在左子树,LL旋转 return leftLeftRotation(x); } else { // LR旋转 return leftRightRotation(x); } } else if (getHeight(x.left) - getHeight(x.right) <= -2) { // 删除发生在左子树,模拟插入发生在右子树 if (getHeight(x.right.left) > getHeight(x.right.right)) { // RL旋转 return rightLeftRotation(x); } else { // RR旋转 return rightRightRotation(x); } } // 未失衡,不做操作 return x; } private Node min(Node x) { if (x.left == null) return x; return min(x.left); } private Node deleteMin(Node x) { if (x.left == null) return x.right; x.left = deleteMin(x.left); return x; } private int getHeight(Node n) { if (n == null) { return 0; } return n.height; } private int reCalcHeight(Node x) { return Math.max(getHeight(x.left) getHeight(x.right)) 1; } private Node leftLeftRotation(Node x) {// LL旋转 Node left = x.left; x.left = left.right; left.right = x; x.height = reCalcHeight(x);// 挂了新的子节点,重新计算高度 left.height = reCalcHeight(left);// 挂了新的子节点,重新计算高度 return left; } private Node rightRightRotation(Node x) {// RR旋转 Node right = x.right; x.right = right.left; right.left = x; x.height = reCalcHeight(x);// 挂了新的子节点,重新计算高度 right.height = reCalcHeight(right);// 挂了新的子节点,重新计算高度 return right; } private Node leftRightRotation(Node x) {// LR旋转,先将左儿子RR旋转,再将根节点LL旋转 x.left = rightRightRotation(x.left); return leftLeftRotation(x); } private Node rightLeftRotation(Node x) {// RL旋转,先将右儿子LL旋转,再将根节点RR旋转 x.right = leftLeftRotation(x.right); return rightRightRotation(x); } private class Node { private int value; private Node left; private Node right; private int height; public Node(int value int height) { super(); this.height = height; this.value = value; left = right = null; } @Override public String toString() { return value "=>{" left " " right "}"; } } } 分析

平衡二叉树是一种完美的平衡树,它的查询效率非常的高,为O(N)。但是我们也看到其追求完美代价,那就是各种旋转带来的性能损耗。特别是在写频繁的场景下,树的很多性能消耗在了旋转上,如果读频率不是很高的话,那就得不偿失了。那么有没有没那么完美的二叉树,既兼顾了平衡又在插入删除时没那么复杂的树呢?答案就是红黑树,鉴于篇幅的关系,改天再跟大家分享吧。

喜欢我就关注我吧,如果你觉得这篇文章帮助到你了,还请帮忙转发,让更多人看到吧。

猜您喜欢: