网站建设公司需要交税么,福建省城乡建设厅网站,佛山市seo点击排名软件,盘锦做网站文章目录 1 什么是AVL树1.1 AVL树的背景及定义1.2 判断失衡1.2.1 平衡因子1.2.2 失衡的四种情况1.2.2.1 LL1.2.2.2 LR1.2.2.3 RL1.2.2.4 RR 1.3 解决失衡1.3.1 左旋#xff08;RR#xff09;1.3.2 右旋#xff08;LL#xff09;1.3.3 先左旋再右旋#xff08;LR#xff0… 文章目录 1 什么是AVL树1.1 AVL树的背景及定义1.2 判断失衡1.2.1 平衡因子1.2.2 失衡的四种情况1.2.2.1 LL1.2.2.2 LR1.2.2.3 RL1.2.2.4 RR 1.3 解决失衡1.3.1 左旋RR1.3.2 右旋LL1.3.3 先左旋再右旋LR1.3.4 先右旋再左旋RL 1.4 AVL树的优缺点1.4.1 AVL树的优点1.4.2 AVL树的缺点 2 AVL树的Java实现2.1 AVL树节点类AVLNode2.2 实现求任意节点高度方法height(AVLNode node)2.3 实现更新节点高度方法updateHeight(AVLNode node)2.4 实现求平衡因子方法bf(AVLNode node)2.5 实现右旋方法rightRotate(AVLNode red)2.6 实现左旋方法leftRotate(AVLNode red)2.7 实现先左旋再右旋方法leftRightRotate(AVLNode node)2.8 实现先右旋再左旋方法rightLeftRotate(AVLNode node)2.9 实现判断及调整平衡方法balance(AVLNode node) ★2.10 实现新增方法put(int key, Object value)2.11 实现删除方法remove(int key) 3 AVL树Java实现代码完整版复制粘贴用 前言本文章为瑞_系列专栏之《数据结构与算法》的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-031将上面的二叉树进行右旋后如下所示最多只要比较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高度差为21表示左边太高 继续修改如下 2(高度3)\4(高度2)\5(高度1)上图二叉树中对于节点2左孩子节点null高度为0和右孩节点4高度为2高度差为-2-1表示右边太高 所以当平衡因子
bf 01-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-121所以左边太高应当向右旋转降低左边高度。 进行右旋需要操作的节点有5、3、4对5进行右旋后3变为根节点5变为其右子树而原来3的右子树节点4要更改为节点5的左子树换爹。 向右旋转后的结果如下图所示
1.3.3 先左旋再右旋LR LR情况需要先让左子树向左 旋转变为LL的情况然后再向右旋转恢复平衡 如上图对节点6的左子树423进行左旋变为LL的情况如下图 再对其进行右旋就恢复平衡如下图 1.3.4 先右旋再左旋RL RL情况需要先让右子树向右 旋转变为RR的情况然后再向左旋转恢复平衡 如上图对节点2的右子树465进行右旋变为RR的情况如下图 再对其进行左旋就恢复平衡如下图 1.4 AVL树的优缺点
1.4.1 AVL树的优点
AVL树是一种自平衡树保证了树的高度平衡从而保证了树的查询和插入操作的时间复杂度均为O(logn)。相比于一般二叉搜索树AVL树对查询效率的提升更为显著因为其左右子树高度的差值不会超过1避免了二叉搜索树退化为链表的情况使得整棵树的高度更低。AVL树的删除操作比较简单只需要像插入一样旋转即可在旋转过程中树的平衡性可以得到维护。
1.4.2 AVL树的缺点
AVL树每次插入或删除节点时需要进行旋转操作这个操作比较耗时因此在一些应用中不太适用。在AVL树进行插入或删除操作时为保持树的平衡需要不断进行旋转操作在一些高并发环节和大数据量环境下这可能会导致多余的写锁导致性能瓶颈。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 /*** h3AVL 树/h3* ul* li二叉搜索树在插入和删除时节点可能失衡/li* li如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树/li* liAVL 是自平衡二叉搜索树的实现之一/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节点类中已经有了高度属性但是也有可能传入nullnull不可能去调用属性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 01-1 时表示左右平衡bf 1 时表示左边太高bf -1 时表示右边太高 /*** 平衡因子 (balance factor) 左子树高度-右子树高度** param node 要计算平衡因子的节点类* return 平衡因子值* - bf 01-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实现代码完整版复制粘贴用
/*** h3AVL 树/h3* ul* li二叉搜索树在插入和删除时节点可能失衡/li* li如果在插入和删除时通过旋转, 始终让二叉搜索树保持平衡, 称为自平衡的二叉搜索树/li* liAVL 是自平衡二叉搜索树的实现之一/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 01-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);}
}本文是博主的粗浅理解可能存在一些错误或不完善之处如有遗漏或错误欢迎各位补充谢谢 如果觉得这篇文章对您有所帮助的话请动动小手点波关注你的点赞收藏⭐️转发评论都是对博主最好的支持~
