瑞_数据结构与算法_AVL树

🙊前言：本文章为瑞_系列专栏之《数据结构与算法》的AVL树篇。由于博主是从B站黑马程序员的《数据结构与算法》学习到的相关知识，所以本系列专栏主要针对该课程进行笔记总结和拓展，文中的部分原理及图解也是来源于黑马提供的资料。本文仅供大家交流、学习及研究使用，禁止用于商业用途，违者必究！

1 什么是AVL树

1.1 AVL树的背景及定义

  AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。

  在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。

瑞：关于二叉搜索树的相关知识，可以参考《瑞_数据结构与算法_二叉搜索树》

  为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。

  由于二叉搜索树在插入和删除时，节点可能失衡，诞生了AVL 树，如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树，AVL 是自平衡二叉搜索树的实现之一。

  AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。

  如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下二叉树所示，如果要搜索1，则需要比较3次，效率很低

		 3(高度3)/2(高度2)/1(高度1)

  通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边仍然小，右边仍然大）

  上面的二叉树根节点高度是3，右孩子为null，可以认为高度为0，所以高度差3-0=3>1，将上面的二叉树进行右旋后，如下所示，最多只要比较2次，效率提升

		   2(高度2)/			\1(高度1) 	     3(高度1)

瑞：注意旋转是不会破坏二叉树的性质的，左边小，右边大

1.2 判断失衡

  如果一个节点的左右孩子，高度差超过 1，则此节点失衡，才需要旋转。失衡的情况发生在二叉树的新增和删除操作的时候。

瑞：关于二叉搜索树的高度，可以参考《瑞_数据结构与算法_二叉搜索树》。高度如下图所示，注意如果某节点为null，则将该节点的高度视作0。

1.2.1 平衡因子

  由于判断失衡的条件为：一个节点的左右孩子，高度差超过 1，所以定义平衡因子（balance factor）简写bf，如下：

	平衡因子 = 左子树高度 - 右子树高度

  上图二叉树中

• 对于节点2，左孩子节点1（高度为1）和右孩子节点4（高度为2）的高度差为-1，表示左右平衡
• 对于节点4，左孩子节点3（高度为1）和右孩子节点5（高度为1）的高度差为0，表示左右平衡

  如果修改如下：

	2(高度2)\4(高度1)

  上图二叉树中，对于节点2，左孩子节点null（高度为0）和右孩节点4（高度为1）的高度差为1，表示左右平衡

  继续修改如下：

	 	3(高度3)/2(高度2)/1(高度1)

  上图二叉树中，对于节点3，左孩子节点2（高度为2）和右孩节点null（高度为0）高度差为2>1，表示左边太高

  继续修改如下：

	 2(高度3)\4(高度2)\5(高度1)

  上图二叉树中，对于节点2，左孩子节点null（高度为0）和右孩节点4（高度为2）高度差为-2<-1，表示右边太高

  所以当平衡因子

• bf = 0，1，-1 时，表示左右平衡
• bf > 1 时，表示左边太高
• bf < -1 时，表示右边太高

瑞：不取绝对值就是为了区分是左边高还是右边高

1.2.2 失衡的四种情况

  通过前人的经验总结，失衡的情况一共有LL、LR、RL、RR四种情况。

1.2.2.1 LL

  bf > 1 && bf(node.left) >= 0为LL情况，如下图所示：

• 失衡节点（图中 5 红色）的 bf > 1，即左边更高
• 失衡节点的左孩子（图中 3 黄色）的 bf >= 0 即左孩子这边也是左边更高或等高

1.2.2.2 LR

  bf > 1 && bf(node.left) < 0为LR情况，如下图所示：

• 失衡节点（图中 6 ）的 bf > 1，即左边更高
• 失衡节点的左孩子（图中 2 红色）的 bf < 0 即左孩子这边是右边更高
  

1.2.2.3 RL

  与LR对称的情况，bf < -1 && bf(node.right) > 0为RL情况，如下图所示：

• 失衡节点（图中 2）的 bf <-1，即右边更高
• 失衡节点的右孩子（图中 6 红色）的 bf > 0，即右孩子这边左边更高
  

1.2.2.4 RR

  与LL对称的情况，bf < -1 && bf(node.right) <= 0为RL情况，如下图所示：

• 失衡节点（图中 2 红色）的 bf <-1，即右边更高
• 失衡节点的右孩子（图中 4 黄色）的 bf <= 0，即右孩子这边右边更高或等高

1.3 解决失衡

  失衡可以通过树的旋转解决。

  树的旋转是：在不干扰元素顺序的情况下更改结构，通常用来让树的高度变得平衡。

1.3.1 左旋（RR）

  RR情况通过一次左旋即可恢复平衡

  如上图，对于节点2，左孩子节点1的高度为1，右孩子节点4的高度为3，高度差为1-3=-2<-1，所以右边太高，应当向左旋转，降低右边高度。

  进行左旋需要操作的节点有4、2、3，对2进行左旋后，4变为根节点，2变为其左子树，而原来4的左子树节点3要更改为节点2的右子树（换爹）。

  向左旋转后的结果如下图所示：

1.3.2 右旋（LL）

  LL情况通过一次右旋即可恢复平衡

  如上图，对于节点5，左孩子节点3的高度为3，右孩子节点6的高度为1，高度差为3-1=2>1，所以左边太高，应当向右旋转，降低左边高度。

  进行右旋需要操作的节点有5、3、4，对5进行右旋后，3变为根节点，5变为其右子树，而原来3的右子树节点4要更改为节点5的左子树（换爹）。

  向右旋转后的结果如下图所示：

1.3.3 先左旋再右旋（LR）

  LR情况需要先让左子树向左
旋转，变为LL的情况，然后再向右旋转，恢复平衡

  如上图，对节点6的左子树（4，2，3）进行左旋，变为LL的情况，如下图：

  再对其进行右旋就恢复平衡，如下图：

1.3.4 先右旋再左旋（RL）

  RL情况需要先让右子树向右
旋转，变为RR的情况，然后再向左旋转，恢复平衡

  如上图，对节点2的右子树（4，6，5）进行右旋，变为RR的情况，如下图：

  再对其进行左旋就恢复平衡，如下图：

1.4 AVL树的优缺点

1.4.1 AVL树的优点

1. AVL树是一种自平衡树，保证了树的高度平衡，从而保证了树的查询和插入操作的时间复杂度均为O(logn)。
2. 相比于一般二叉搜索树，AVL树对查询效率的提升更为显著，因为其左右子树高度的差值不会超过1，避免了二叉搜索树退化为链表的情况，使得整棵树的高度更低。
3. AVL树的删除操作比较简单，只需要像插入一样旋转即可，在旋转过程中树的平衡性可以得到维护。

1.4.2 AVL树的缺点

1. AVL树每次插入或删除节点时需要进行旋转操作，这个操作比较耗时，因此在一些应用中不太适用。
2. 在AVL树进行插入或删除操作时，为保持树的平衡需要不断进行旋转操作，在一些高并发环节和大数据量环境下，这可能会导致多余的写锁导致性能瓶颈。
3. AVL树的旋转操作相对较多，因此在一些应用中可能会造成较大的空间浪费。

---

2 AVL树的Java实现

1️⃣内部节点类AVLNode中含有属性：

• 索引
• 存储值
• 左孩子
• 右孩子
• 节点高度

2️⃣AVLTree二叉搜索树类含有方法：

• 求任意节点高度height(AVLNode node)
• 更新节点高度updateHeight(AVLNode node)
• 求平衡因子bf(AVLNode node)
• 右旋rightRotate(AVLNode red)
• 左旋leftRotate(AVLNode red)
• 先左旋再右旋leftRightRotate(AVLNode node)
• 先右旋再左旋rightLeftRotate(AVLNode node)
• 判断及调整平衡balance(AVLNode node)
• 新增put(int key, Object value)
• 删除remove(int key)

2.1 AVL树节点类AVLNode

/*** <h3>AVL 树</h3>* <ul>*     <li>二叉搜索树在插入和删除时，节点可能失衡</li>*     <li>如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树</li>*     <li>AVL 是自平衡二叉搜索树的实现之一</li>* </ul>*/
public class AVLTree {static class AVLNode {/*** 索引*/int key;/*** 存储值*/Object value;/*** 左孩子*/AVLNode left;/*** 右孩子*/AVLNode right;/*** 节点高度，初始默认为1*/int height = 1;public AVLNode(int key, Object value) {this.key = key;this.value = value;}public AVLNode(int key) {this.key = key;}public AVLNode(int key, Object value, AVLNode left, AVLNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}
}

2.2 实现求任意节点高度方法height(AVLNode node)

  height(AVLNode node)方法为查找该节点在AVL树中的高度

  虽然已经在AVLNode节点类中已经有了高度属性，但是也有可能传入null，null不可能去调用属性height，所以要特别定义方法进行处理，实现很简单如下：

    // 求任意节点高度private int height(AVLNode node) {return node == null ? 0 : node.height;}

2.3 实现更新节点高度方法updateHeight(AVLNode node)

  updateHeight(AVLNode node)方法为私有方法，因为将来新增、删除、旋转时，高度都可能发生变化，需要内部调用本方法更新高度值。

	思路：取该节点的左孩子和右孩子中索引更大的一个值，高度+1的结果则为该节点的高度（如果孩子节点为null，则高度视作0）

  下面是更新高度的代码：

    // 更新节点高度 (新增、删除、旋转)private void updateHeight(AVLNode node) {node.height = Integer.max(height(node.left), height(node.right)) + 1;}

求一个节点左右子树的高度差

2.4 实现求平衡因子方法bf(AVLNode node)

  bf(AVLNode node)方法为私有方法，因为判断失衡需要用到平衡因子。

  平衡因子 (balance factor) = 左子树高度-右子树高度

  本方法返回一个整数，含义如下：

• bf = 0，1，-1 时，表示左右平衡
• bf > 1 时，表示左边太高
• bf < -1 时，表示右边太高

    /*** 平衡因子 (balance factor) = 左子树高度-右子树高度** @param node 要计算平衡因子的节点类* @return 平衡因子值* - bf = 0，1，-1 时，表示左右平衡* - bf > 1 时，表示左边太高* - bf < -1 时，表示右边太高**/private int bf(AVLNode node) {return height(node.left) - height(node.right);}

2.5 实现右旋方法rightRotate(AVLNode red)

  向右旋转前，如下图所示：

• 红色节点，旧根（失衡节点）
• 黄色节点，旧根的左孩子，将来作为新根，旧根是它右孩子
• 绿色节点，新根的右孩子，将来要换爹作为旧根的左孩子

  右旋后，如下图所示：

  实现代码如下：

    /*** 右旋** @param red 要旋转的节点* @return 新的根节点**/private AVLNode rightRotate(AVLNode red) {AVLNode yellow = red.left;AVLNode green = yellow.right;yellow.right = red;   // 上位（旋转）red.left = green;     // 换爹updateHeight(red);    // 更新高度updateHeight(yellow); // 更新高度return yellow;}

由于是右旋操作，左子树肯定比右子树高，所以黄色节点不可能为null，也就是yellow.right不会报空指针异常，无需判断。只有红色和黄色节点的高度会发生变化，所以更新高度只需要更新红色节点和黄色节点。

2.6 实现左旋方法leftRotate(AVLNode red)

  向左旋转前，如下图所示：

• 红色节点，旧根（失衡节点）
• 黄色节点，旧根的右孩子，将来作为新根，旧根是它左孩子
• 绿色节点，新根的左孩子，将来要换爹作为旧根的右孩子

  左旋后，如下图所示：

  实现代码如下：

    /*** 左旋** @param red 要旋转的节点* @return 新的根节点**/private AVLNode leftRotate(AVLNode red) {AVLNode yellow = red.right;AVLNode green = yellow.left;yellow.left = red;  // 上位red.right = green;  // 换爹updateHeight(red);  // 更新高度updateHeight(yellow); // 更新高度return yellow;}

只有红色和黄色节点的高度会发生变化，所以更新高度只需要更新红色节点和黄色节点。

2.7 实现先左旋再右旋方法leftRightRotate(AVLNode node)

  先让左子树调用左旋方法，变为LL的情况，然后再调用右旋方法，恢复平衡

    // 先左旋左子树, 再右旋根节点private AVLNode leftRightRotate(AVLNode node) {node.left = leftRotate(node.left);return rightRotate(node);}

2.8 实现先右旋再左旋方法rightLeftRotate(AVLNode node)

  先让右子树调用右旋方法，变为RR的情况，然后再调用左旋方法，恢复平衡

    // 先右旋右子树, 再左旋根节点private AVLNode rightLeftRotate(AVLNode node) {node.right = rightRotate(node.right);return leftRotate(node);}

2.9 实现判断及调整平衡方法balance(AVLNode node) ★

  balance(AVLNode node)是为了检查节点是否失衡，重新平衡。是比较重要的综合性方法。

    // 检查节点是否失衡, 重新平衡代码private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) { // LLreturn rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) { // LRreturn leftRightRotate(node);} else if (bf < -1 && bf(node.right) > 0) { // RLreturn rightLeftRotate(node);} else if (bf < -1 && bf(node.right) <= 0) { // RRreturn leftRotate(node);}return node;}

注意LL和RR的删除情况，所以要考虑等于0的情况。以上四种旋转代码里，都需要更新高度，需要更新的节点是红色、黄色，而绿色节点高度不变

2.10 实现新增方法put(int key, Object value)

    /*** 根节点*/AVLNode root;/*** 新增节点 - 递归实现** @param key   索引* @param value 存储值**/public void put(int key, Object value) {root = doPut(root, key, value);}private AVLNode doPut(AVLNode node, int key, Object value) {// 1. 找到空位, 创建新节点if (node == null) {return new AVLNode(key, value);}// 2. key 已存在, 更新if (key == node.key) {node.value = value;return node;}// 3. 继续查找if (key < node.key) {node.left = doPut(node.left, key, value); // 向左} else {node.right = doPut(node.right, key, value); // 向右}// 以下为AVL树和二叉树的新增区别，需要更新高度，判断平衡updateHeight(node);return balance(node);}

2.11 实现删除方法remove(int key)

    /*** 删除节点 - 递归实现** @param key 要删除节点的索引值**/public void remove(int key) {root = doRemove(root, key);}private AVLNode doRemove(AVLNode node, int key) {// 1. node == nullif (node == null) {return null;}// 2. 没找到 keyif (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} else {// 3. 找到 key  1) 没有孩子 2) 只有一个孩子 3) 有两个孩子if (node.left == null && node.right == null) {return null;} else if (node.left == null) {node = node.right;} else if (node.right == null) {node = node.left;} else {AVLNode s = node.right;while (s.left != null) {s = s.left;}// s 后继节点s.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}// 4. 更新高度updateHeight(node);// 5. balancereturn balance(node);}

---

3 AVL树Java实现代码完整版（复制粘贴用）

/*** <h3>AVL 树</h3>* <ul>*     <li>二叉搜索树在插入和删除时，节点可能失衡</li>*     <li>如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树</li>*     <li>AVL 是自平衡二叉搜索树的实现之一</li>* </ul>*/
public class AVLTree {static class AVLNode {/*** 索引*/int key;/*** 存储值*/Object value;/*** 左孩子*/AVLNode left;/*** 右孩子*/AVLNode right;/*** 节点高度，初始默认为1*/int height = 1;public AVLNode(int key, Object value) {this.key = key;this.value = value;}public AVLNode(int key) {this.key = key;}public AVLNode(int key, Object value, AVLNode left, AVLNode right) {this.key = key;this.value = value;this.left = left;this.right = right;}}/*** 根节点*/AVLNode root;// 求任意节点高度private int height(AVLNode node) {return node == null ? 0 : node.height;}// 更新节点高度 (新增、删除、旋转)private void updateHeight(AVLNode node) {node.height = Integer.max(height(node.left), height(node.right)) + 1;}/*** 平衡因子 (balance factor) = 左子树高度-右子树高度** @param node 要计算平衡因子的节点类* @return 平衡因子值* - bf = 0，1，-1 时，表示左右平衡* - bf > 1 时，表示左边太高* - bf < -1 时，表示右边太高**/private int bf(AVLNode node) {return height(node.left) - height(node.right);}/*** 右旋** @param red 要旋转的节点* @return 新的根节点**/private AVLNode rightRotate(AVLNode red) {AVLNode yellow = red.left;AVLNode green = yellow.right;yellow.right = red;   // 上位red.left = green;     // 换爹updateHeight(red);updateHeight(yellow);return yellow;}/*** 左旋** @param red 要旋转的节点* @return 新的根节点**/private AVLNode leftRotate(AVLNode red) {AVLNode yellow = red.right;AVLNode green = yellow.left;yellow.left = red;  // 上位red.right = green;  // 换爹updateHeight(red);updateHeight(yellow);return yellow;}// 先左旋左子树, 再右旋根节点private AVLNode leftRightRotate(AVLNode node) {node.left = leftRotate(node.left);return rightRotate(node);}// 先右旋右子树, 再左旋根节点private AVLNode rightLeftRotate(AVLNode node) {node.right = rightRotate(node.right);return leftRotate(node);}// 检查节点是否失衡, 重新平衡代码private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) { // LLreturn rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) { // LRreturn leftRightRotate(node);} else if (bf < -1 && bf(node.right) > 0) { // RLreturn rightLeftRotate(node);} else if (bf < -1 && bf(node.right) <= 0) { // RRreturn leftRotate(node);}return node;}/*** 新增节点 - 递归实现** @param key   索引* @param value 存储值**/public void put(int key, Object value) {root = doPut(root, key, value);}private AVLNode doPut(AVLNode node, int key, Object value) {// 1. 找到空位, 创建新节点if (node == null) {return new AVLNode(key, value);}// 2. key 已存在, 更新if (key == node.key) {node.value = value;return node;}// 3. 继续查找if (key < node.key) {node.left = doPut(node.left, key, value); // 向左} else {node.right = doPut(node.right, key, value); // 向右}updateHeight(node);return balance(node);}/*** 删除节点 - 递归实现** @param key 要删除节点的索引值**/public void remove(int key) {root = doRemove(root, key);}private AVLNode doRemove(AVLNode node, int key) {// 1. node == nullif (node == null) {return null;}// 2. 没找到 keyif (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} else {// 3. 找到 key  1) 没有孩子 2) 只有一个孩子 3) 有两个孩子if (node.left == null && node.right == null) {return null;} else if (node.left == null) {node = node.right;} else if (node.right == null) {node = node.left;} else {AVLNode s = node.right;while (s.left != null) {s = s.left;}// s 后继节点s.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}// 4. 更新高度updateHeight(node);// 5. balancereturn balance(node);}
}

---

本文是博主的粗浅理解，可能存在一些错误或不完善之处，如有遗漏或错误欢迎各位补充，谢谢

  如果觉得这篇文章对您有所帮助的话，请动动小手点波关注💗，你的点赞👍收藏⭐️转发🔗评论📝都是对博主最好的支持~