别人做的网站不能用怎么办,创办一个网站,学做缝纫的网站,成都网站建设028net前言
本文章将介绍 AVL 树的概念#xff0c;重点介绍AVL 树的插入代码是如何实现的#xff0c;如果大家对 AVL 树的删除#xff08;还是和二叉搜索树一样使用的是替换删除法#xff0c;然后需要判断是否进行旋转调整#xff09;感兴趣的话#xff0c;可以自行去翻阅其他…前言
本文章将介绍 AVL 树的概念重点介绍AVL 树的插入代码是如何实现的如果大家对 AVL 树的删除还是和二叉搜索树一样使用的是替换删除法然后需要判断是否进行旋转调整感兴趣的话可以自行去翻阅其他资料~~
概念
回顾二叉搜索树
之前我们就了解到二叉搜索树中序遍历的时候数据是有序的这是由于二分搜索树具有以下性质 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树
最好的搜索时间复杂度为 O(logN)但是如果插入的数据是有序或者逆序的时候二叉搜索树就会变成一颗单分支的二叉树搜索的时间复杂度也最差为 O(N)
那么能不能让二叉搜索树在插入结点的时候就能始终保持平衡也就是保持一颗饱满的二叉树形态呢
这就是我们要学习的 AVL 树
AVL 树
两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述二叉搜索树存在的问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树具有以下性质 AVL 树同时具有二叉搜索树的性质 它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过 1 (-1、0、1)即始终保持高度平衡 如果一棵二叉搜索树是高度平衡的它就是AVL树。 平衡因子
平衡因子就是左右子树高度之差 这里我定义平衡因子等于右子树高度减去左子树的高度 以下图为例 A 结点右子树高度等于左子树高度平衡因子为0 B 结点右子树高度减左子树高度等于 -1平衡因子为 -1 C 结点右子树高度减左子树高度等于 1平衡因子为 1 D 结点右子树高度等于左子树高度平衡因子为0 E 结点右子树高度等于左子树高度平衡因子为0
结点定义
和普通的树结点一样具有左引用右引用数据val以及构造方法 但是 AVL 树还要再加一个平衡因子Balance Factor简写为 bf 还有一个双亲结点的引用和平衡因子一样插入的时候要用到
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val val;}
}插入实现
首先完成结点的插入工作这里的插入和之前我们在二叉搜索树已经学习过这里就直接上代码如果不了解的可以点开这个连接JavaDS —— 二叉搜索树、哈希表、Map 与 Set public boolean insert(int val) {TreeNode node new TreeNode(val);//如果根节点本身为空就直接赋值if(root null) {root node;return true;}TreeNode prev null;TreeNode cur root;//找到新结点的位置while(cur ! null) {if(cur.val val) {//相同的数据无法再次插入return false;} else if(cur.val val) {prev cur;cur cur.right;} else {prev cur;cur cur.left;}}//插入结点if(prev.val val) {prev.left node;} else {prev.right node;}node.parent prev;}现在就是调整平衡因子这里我设定为右子树高度减左子树高度如果你是插入到左子树的话那平衡因子就要自减如果是插入到右子树的话那平衡因子就要自增。
首先就要先拿到 node 的位置将cur 重置为 node
cur node;//左子树-- 右子树if(prev.left cur) {prev.bf--;} else {prev.bf;}调节完平衡因子之后此时调节过的平衡因子有五种情况0 、1 、-1 、2 、-2
如下图所示红色的结点为新插入的结点灰色的结点则是已经存在的 如果调节过后平衡因子依旧为 0 则说明该树本身就已经平衡了不需要进行旋转调整.
如果调节过后的平衡因子为 1 或者 -1说明该结点的兄弟结点为空这个结点的插入可能会导致不平衡需要我们继续向上调整平衡因子这时候我们会使用 parent 引用让prev 和 cur 一起向上移动大家就会想到使用循环来调整平衡因子。
循环的部分代码如下 cur node;//调整平衡因子与AVL树while(prev ! null) {//左子树-- 右子树if(prev.left cur) {prev.bf--;} else {prev.bf;}//检查是否需要旋转if(prev.bf 0) {//平衡因子为0说明树已经平衡不用调整break;} else if(prev.bf -1 || prev.bf 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到需要继续调整cur prev;prev prev.parent;}}如果调节过后的平衡因子为 2 或者 -2说明该树出现不平衡需要进行旋转调整
大家可以记一下旋转的口诀旋转内容会在下面继续讲解 左左型右单旋 右右型左单旋 左右型左右双旋 右左型右左双选 else {//此时怕平衡因子有两种情况2 或者 -2需要旋转重新建立平衡树if(prev.bf 2) {//说明右子树过高if(cur.bf 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf -2 说明左子树过高if(cur.bf 1) {//左右型左右双旋rotateLR(prev);} else if(cur.bf -1) {//左左型 右单旋rotateRight(prev);}}//旋转完成后树已经平衡直接退出循环break;}经过旋转过后树就会平衡就无需继续调整平衡因子直接跳出循环即可。 旋转实现 下面所有的实例图绿色的数字表示经过旋转后平衡因子变为多少 左单旋
当新插入的结点插在某个结点的右孩子的右子树时这个简称为右右型那么这个某个结点采用左单旋
简单情况 我们需要让 prev 成为 cur 的左孩子这时候我们需要修改 prev 的 parent 引用 cur 的左孩子引用以及parent 引用并且cur 结点的 parent 引用需要改成原来 prev 的parent引用记为 pParent所以我们事先就要保存好pParent最后我们要将pParent 的左引用或者右引用 来连接cur 这里需要判断一下最后的最后这两个结点的平衡因子置为 0
特殊情况如果prev 本身就是 根节点的话那么根节点的引用要变成 cur 的。
如果 cur 的左孩子本身就存在呢 那么我们需要将 cur 左孩子结点先保存起来让 prev.right cur 的左孩子结点并且左孩子结点的 parent 的引用要修改为 prev所以这里引申出我们需要判断 cur 的左孩子结点存不存在如果不存在则不需要修改其 parent 引用避免发生空指针异常 //左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent prev.parent;TreeNode cur prev.right;TreeNode curL cur.left;prev.right curL;if(curL ! null) {curL.parent prev;}cur.left prev;prev.parent cur;cur.parent pParent;if(prev root) {root cur;} else if(pParent.left prev) {pParent.left cur;} else {pParent.right cur;}//调整平衡因子cur.bf prev.bf 0;}右单旋
当新插入的结点插在某个结点的左孩子的左子树时这个简称为左左型那么这个某个结点采用右单旋
简单情况 这个和左单旋很相似大家可以类比左单旋。
特殊情况如果 prev 本身就是根节点的话就要修改根结点的引用。
还有如果 cur 自身就有右孩子让 prev.left cur 的右孩子结点并且判断右孩子结点是否为空不为空的话将 parent 的引用要修改为 prev //右单旋private void rotateRight(TreeNode prev) {TreeNode pParent prev.parent;TreeNode cur prev.left;TreeNode curR cur.right;prev.left curR;if(curR ! null) {curR.parent prev;}cur.right prev;prev.parent cur;cur.parent pParent;if(prev root) {root cur;} else if(pParent.left prev) {pParent.left cur;} else {pParent.right cur;}//调整平衡因子cur.bf prev.bf 0;}左右双旋
当新插入的结点插在某个结点的左孩子的右子树时这个简称为左右型那么这个某个结点采用左右双旋
简单情况 左右双旋是指先进行左单旋再进行右单旋当然你也可以一步到位我这里采用分步 所以左右双旋需要先对 cur 调用左单旋再对 prev 调用右单旋 特殊情况由于在单旋代码中我们已经处理好根节点和prev 的parent 结点了但是这三个结点的平衡因子最后一定是 0 吗 这次我们讨论的是如果是下面两种复杂的情况时我们就需要修改一下某些结点的平衡因子 进行完两个单旋转后最后这三个结点的平衡因子都为0但是看到上面的情况之后其实并不是都为0所以我们在进行旋转的时候就要先保存好cur 的右孩子的平衡因子等到旋转结束后就要调整平衡因子。
当 cur.right.bf -1 时prev.bf 1 当 cur.right.bf 1 时cur.bf -1 //左右双旋private void rotateLR(TreeNode prev) {TreeNode cur prev.left;TreeNode curR cur.right;int bf curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf 1) {cur.bf -1;} else if(bf -1) {prev.bf 1;}//bf 为 0 的时候不需要调整}右左双旋
当新插入的结点插在某个结点的右孩子的左子树时这个简称为右左型那么这个某个结点采用右左双旋
和左右双旋是类似的这里就给出三种情况的图片给大家参考 简单情况 特殊情况 当 cur.left.bf -1 时cur.bf 1 当 cur.left.bf 1 时prev.bf -1 //右左双旋private void rotateRL(TreeNode prev) {TreeNode cur prev.right;TreeNode curL cur.left;int bf curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf 1) {prev.bf -1;} else if(bf -1) {cur.bf 1;}//bf 为 0 的时候不需要调整}测试
写好AVL 树记得测试自己的代码有没有错误这里要测试两个东西第一个是中序遍历的时候是否有序检测是否为二叉搜索树第二个东西就是平衡因子有没有错误以及是否是一个高度平衡的二叉树因为都与高度有关所以可以放在同一个方法里去写测试代码。
性能分析
AVL 树始终都能保持高度的平衡即左右子树的高度差 1所以在搜索数据的时候时间复杂度为O(log N)举个例子加上有10亿个数据需要在其中找到一个数据如果使用 AVL 树2的30次方等于1,073,741,824所以最多只需要查找30次就能找到目标值可见AVL 树在查找中的优秀表现。
由于AVL树在插入和删除的时候会进行旋转调整这也就意味着大量时间和资源的消耗所以AVL 树比较适合静态数据的查找如果数据涉及大量的删除或者插入就会导致AVL 树的效率下降这也就是为什么现在AVL 树应用范围比较小。
最终代码
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode parent;int bf; //平衡因子 右子树高度减去左子树高度public TreeNode(int val) {this.val val;}
}public class AVLTree {public TreeNode root;public boolean insert(int val) {TreeNode node new TreeNode(val);//如果根节点本身为空就直接赋值if(root null) {root node;return true;}TreeNode prev null;TreeNode cur root;//找到新结点的位置while(cur ! null) {if(cur.val val) {//相同的数据无法再次插入return false;} else if(cur.val val) {prev cur;cur cur.right;} else {prev cur;cur cur.left;}}//插入结点if(prev.val val) {prev.left node;} else {prev.right node;}node.parent prev;cur node;//调整平衡因子与AVL树while(prev ! null) {//左子树-- 右子树if(prev.left cur) {prev.bf--;} else {prev.bf;}//检查是否需要旋转if(prev.bf 0) {//平衡因子为0说明树已经平衡不用调整break;} else if(prev.bf -1 || prev.bf 1) {//如果出现 -1 或者 1 则说明树的平衡性已经被新结点影响到需要继续调整cur prev;prev prev.parent;} else {//此时怕平衡因子有两种情况2 或者 -2需要旋转重新建立平衡树if(prev.bf 2) {//说明右子树过高if(cur.bf 1) {//右右型 左单旋rotateLeft(prev);} else if(cur.bf -1) {//右左型 右左双旋rotateRL(prev);}} else {//此时 prev.bf -2 说明左子树过高if(cur.bf 1) {//左右型左右双旋rotateLR(prev);} else if(cur.bf -1) {//左左型 右单旋rotateRight(prev);}}//旋转完成后树已经平衡直接退出循环break;}}return true;}//左右双旋private void rotateLR(TreeNode prev) {TreeNode cur prev.left;TreeNode curR cur.right;int bf curR.bf;rotateLeft(cur);rotateRight(prev);//调整平衡因子if(bf 1) {cur.bf -1;} else if(bf -1) {prev.bf 1;}//bf 为 0 的时候不需要调整}//右左双旋private void rotateRL(TreeNode prev) {TreeNode cur prev.right;TreeNode curL cur.left;int bf curL.bf;rotateRight(cur);rotateLeft(prev);//调整平衡因子if(bf 1) {prev.bf -1;} else if(bf -1) {cur.bf 1;}//bf 为 0 的时候不需要调整}//右单旋private void rotateRight(TreeNode prev) {TreeNode pParent prev.parent;TreeNode cur prev.left;TreeNode curR cur.right;prev.left curR;if(curR ! null) {curR.parent prev;}cur.right prev;prev.parent cur;cur.parent pParent;if(prev root) {root cur;} else if(pParent.left prev) {pParent.left cur;} else {pParent.right cur;}//调整平衡因子cur.bf prev.bf 0;}//左单旋private void rotateLeft(TreeNode prev) {TreeNode pParent prev.parent;TreeNode cur prev.right;TreeNode curL cur.left;prev.right curL;if(curL ! null) {curL.parent prev;}cur.left prev;prev.parent cur;cur.parent pParent;if(prev root) {root cur;} else if(pParent.left prev) {pParent.left cur;} else {pParent.right cur;}//调整平衡因子cur.bf prev.bf 0;}
}
