💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
- 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
- 导航
- 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
- 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
- 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
- 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
- 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
博客目录
- 一.简介
- 1.AVL 历史
- 2.如何判断失衡?
- 3.节点的高度
- 4.何时触发失衡判断?
- 二.自平衡
- 1.失衡的四种情况
- 2.LL
- 3.LR
- 4.RL
- 5.RR
- 6.解决失衡
- 7.右旋
- 8.左旋
- 9.左右旋
- 10.右左旋
- 三.新增与删除
- 1.新增
- 2.删除
- 3.完整代码
- 4.小结
一.简介
1.AVL 历史
AVL 树是一种自平衡二叉搜索树,由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字:Adelson-Velsky 和 Landis,他们是苏联数学家,于 1962 年发表了一篇论文,详细介绍了 AVL 树的概念和性质。
在二叉搜索树中,如果插入的元素按照特定的顺序排列,可能会导致树变得非常不平衡,从而降低搜索、插入和删除的效率。为了解决这个问题,AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2,则通过旋转操作来重新平衡树。
AVL 树是用于存储有序数据的一种重要数据结构,它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率,而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展,AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。
如果一棵二叉搜索树长的不平衡,那么查询的效率会受到影响,如下图
通过旋转可以让树重新变得平衡,并且不会改变二叉搜索树的性质(即左边仍然小,右边仍然大)
2.如何判断失衡?
如果一个节点的左右孩子,高度差超过 1,则此节点失衡,才需要旋转
叶子节点的高度默认为 1
网上遍历,高度越高
3.节点的高度
如何得到节点高度?一种方式之前做过的一道题目:E05. 求二叉树的最大深度(高度),但由于求高度是一个非常频繁的操作,因此将高度作为节点的一个属性,将来新增或删除时及时更新,默认为 1(按力扣说法)
static class AVLNode {int height = 1;int key;Object value;AVLNode left;AVLNode right;// ...
}
求高度代码
这里加入了 height 函数方便求节点为 null 时的高度
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;
}
4.何时触发失衡判断?
定义平衡因子(balance factor)如下
平衡因子 = 左子树高度 − 右子树高度 平衡因子 = 左子树高度 - 右子树高度 平衡因子=左子树高度−右子树高度
当平衡因子
- bf = 0,1,-1 时,表示左右平衡
- bf > 1 时,表示左边太高
- bf < -1 时,表示右边太高
对应代码
private int bf(AVLNode node) {return height(node.left) - height(node.right);
}
当插入新节点,或删除节点时,引起高度变化时,例如
目前此树平衡,当再插入一个 4 时,节点们的高度都产生了相应的变化,8 节点失衡了
在比如说,下面这棵树一开始也是平衡的
当删除节点 8 时,节点们的高度都产生了相应的变化,6 节点失衡了
二.自平衡
1.失衡的四种情况
- LL
- LR
- RL
- RR
2.LL
- 失衡节点(图中 8 红色)的 bf > 1,即左边更高
- 失衡节点的左孩子(图中 6)的 bf >= 0 即左孩子这边也是左边更高或等高
3.LR
- 失衡节点(图中 8)的 bf > 1,即左边更高
- 失衡节点的左孩子(图中 6 红色)的 bf < 0 即左孩子这边是右边更高
对称的还有两种情况
4.RL
- 失衡节点(图中 3)的 bf <-1,即右边更高
- 失衡节点的右孩子(图中 6 红色)的 bf > 0,即右孩子这边左边更高
5.RR
- 失衡节点(图中 3)的 bf <-1,即右边更高
- 失衡节点的右孩子(图中 6 红色)的 bf <= 0,即右孩子这边右边更高或等高
6.解决失衡
失衡可以通过树的旋转解决。什么是树的旋转呢?它是在不干扰元素顺序的情况下更改结构,通常用来让树的高度变得平衡。
观察下面一棵二叉搜索树,可以看到,旋转后,并未改变树的左小右大特性,但根、父、孩子节点都发生了变化
4 2/ \ 4 right / \2 5 --------------------> 1 4/ \ <-------------------- / \1 3 2 left 3 5
7.右旋
旋转前
- 红色节点,旧根(失衡节点)
- 黄色节点,旧根的左孩子,将来作为新根,旧根是它右孩子
- 绿色节点,新根的右孩子,将来要换爹作为旧根的左孩子
旋转后
代码
private AVLNode rightRotate(AVLNode red) {AVLNode yellow = red.left;AVLNode green = yellow.right;yellow.right = red;red.left = green;return yellow;
}
8.左旋
旋转前
- 红色节点,旧根(失衡节点)
- 黄色节点,旧根的右孩子,将来作为新根,旧根是它左孩子
- 绿色节点,新根的左孩子,将来要换爹作为旧根的右孩子
旋转后
代码
private AVLNode leftRotate(AVLNode red) {AVLNode yellow = red.right;AVLNode green = yellow.left;yellow.left = red;red.right = green;return yellow;
}
9.左右旋
指先左旋左子树,再右旋根节点(失衡),这时一次旋转并不能解决失衡
左子树旋转后
根右旋前
根右旋后
代码
private AVLNode leftRightRotate(AVLNode root) {root.left = leftRotate(root.left);return rightRotate(root);
}
10.右左旋
指先右旋右子树,再左旋根节点(失衡)
右子树右旋后
根左旋前
根左旋后
代码
private AVLNode rightLeftRotate(AVLNode root) {root.right = rightRotate(root.right);return leftRotate(root);
}
判断及调整平衡代码
private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) {return rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) {return rightLeftRotate(node);} else if (bf < -1 && bf(node.right) > 0) {return leftRightRotate(node);} else if (bf < -1 && bf(node.right) <= 0) {return rightRotate(node);}return node;
}
以上四种旋转代码里,都需要更新高度,需要更新的节点是红色、黄色,而绿色节点高度不变
三.新增与删除
1.新增
public void put(int key, Object value) {root = doPut(root, key, value);
}private AVLNode doPut(AVLNode node, int key, Object value) {if (node == null) {return new AVLNode(key, value);}if (key == node.key) {node.value = value;return node;}if (key < node.key) {node.left = doPut(node.left, key, value);} else {node.right = doPut(node.right, key, value);}updateHeight(node);return balance(node);
}
2.删除
public void remove(int key) {root = doRemove(root, key);
}private AVLNode doRemove(AVLNode node, int key) {if (node == null) {return null;}if (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} 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.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}if (node == null) {return null;}updateHeight(node);return balance(node);
}
3.完整代码
public class AVLTree {static class AVLNode {int height = 1;int key;Object value;AVLNode left;AVLNode right;public AVLNode(int key) {this.key = key;}public AVLNode(int key, Object value) {this.key = key;this.value = value;}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 AVLNode leftRotate(AVLNode p) {AVLNode r = p.right;AVLNode b = r.left;r.left = p;p.right = b;updateHeight(p);updateHeight(r);return r;}private void updateHeight(AVLNode node) {node.height = Integer.max(height(node.left), height(node.right)) + 1;}private AVLNode rightRotate(AVLNode r) {AVLNode a = r.left;AVLNode b = a.right;a.right = r;r.left = b;updateHeight(r);updateHeight(a);return a;}private AVLNode leftRightRotate(AVLNode p) {AVLNode r = p.left;p.left = leftRotate(r);return rightRotate(p);}private AVLNode rightLeftRotate(AVLNode p) {AVLNode r = p.right;p.right = rightRotate(r);return leftRotate(p);}private int height(AVLNode node) {return node == null ? 0 : node.height;}public void remove(int key) {root = doRemove(root, key);}private AVLNode doRemove(AVLNode node, int key) {if (node == null) {return null;}if (key < node.key) {node.left = doRemove(node.left, key);} else if (node.key < key) {node.right = doRemove(node.right, key);} 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.right = doRemove(node.right, s.key);s.left = node.left;node = s;}}if (node == null) {return null;}updateHeight(node);return balance(node);}public void put(int key, Object value) {root = doPut(root, key, value);}private AVLNode doPut(AVLNode node, int key, Object value) {if (node == null) {return new AVLNode(key, value);}if (key == node.key) {node.value = value;return node;}if (key < node.key) {node.left = doPut(node.left, key, value);} else {node.right = doPut(node.right, key, value);}updateHeight(node);return balance(node);}private int bf(AVLNode node) {return height(node.left) - height(node.right);}private AVLNode balance(AVLNode node) {if (node == null) {return null;}int bf = bf(node);if (bf > 1 && bf(node.left) >= 0) {return rightRotate(node);} else if (bf > 1 && bf(node.left) < 0) {return rightLeftRotate(node);} else if (bf < -1 && bf(node.right) > 0) {return leftRightRotate(node);} else if (bf < -1 && bf(node.right) <= 0) {return rightRotate(node);}return node;}
}
4.小结
AVL 树的优点:
- AVL 树是一种自平衡树,保证了树的高度平衡,从而保证了树的查询和插入操作的时间复杂度均为 O(logn)。
- 相比于一般二叉搜索树,AVL 树对查询效率的提升更为显著,因为其左右子树高度的差值不会超过 1,避免了二叉搜索树退化为链表的情况,使得整棵树的高度更低。
- AVL 树的删除操作比较简单,只需要像插入一样旋转即可,在旋转过程中树的平衡性可以得到维护。
AVL 树的缺点:
- AVL 树每次插入或删除节点时需要进行旋转操作,这个操作比较耗时,因此在一些应用中不太适用。
- 在 AVL 树进行插入或删除操作时,为保持树的平衡需要不断进行旋转操作,在一些高并发环节和大数据量环境下,这可能会导致多余的写锁导致性能瓶颈。
- AVL 树的旋转操作相对较多,因此在一些应用中可能会造成较大的空间浪费。
觉得有用的话点个赞
👍🏻
呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙