刚看到jjdyt老师的数据结构与算法对于平衡二叉树的讲解(最后会附上地址),有如下理解,希望能帮助大家!哪里需要改正的欢迎指正!
平衡二叉树:一种二叉排序树(BST Binary Sort Tree)的升级,传统的二叉排序树容易形成类似链表的结构,造成平均查询次数较高,所以引入平衡二叉树,使得左右子树的高度差不超过1;
我们知道了平衡二叉树的原理之后,就要在添加结点后就要判断是否需要将此树转化成平衡二叉树!如下例:4,3,5,2,1,0
如图,当添加到1这个结点的时候,4的左子树高为2,4的右子树高为0。 两者高度差为2,此时这棵树不是平衡二叉树,那么就需要将其转换成平衡二叉树(先按照这个例子来进行,下面会说明其他情况):具体操作如下:
先将必要类和方法写出:
同时:我们还要写计算左子树高和右子树高的方法!这个方法可以帮助我们判断当添加数据之后是否需要进行转化。
//计算左子树的高度public int leftHeigh() {if(left==null) {return 0;}return left.height();}//计算右子树的高度public int rightHeigh() {if(right==null) {return 0;}return right.height();}//计算结点的树高度public int height() {return Math.max(left==null ? 0 : left.height(), right==null?0:right.height())+1;}当有了这些方法之后就可以进行转换了:举贤惠的棉花糖在课堂上的例子4,3,6,5,7,8
当我们添加完8后,发现不满足平衡二叉树的条件了,就需要对其进行操作使其转化成平衡二叉树,这里的操作叫做左旋(当然还有右旋,双旋,放到后面来讲那些例子)!
操作如下:将其分为两步,很简单就是赋值的两步操作;
第一步.创建新节点,
新结点的值=当前结点的值(也就是4);
新结点的左节点=当前节点的左节点(3)
新结点的右节点=当前结点的右结点的左节点(5)
第二步.修改当前节点
当前结点的值=当前节点的右节点
当前节点的右子树=当前节点的右子树的右子树
当前节点的左子树=新结点
这里第一步的操作实质上可以理解成,将上面三个点记录下来,作为第二步当前结点的右节点
第二步的操作为:将当前节点的值修改成6,并将当前节点的左右结点修改,如图,到此,转化过程就到此结束了,(这里的白色6因为没有被任何的GC roots指向,将会被回收)
左旋的代码
在add方法加上左旋转的代码
if(this.rightHeigh()-this.leftHeigh()>1) {this.leftRotate();} 右旋其实右旋和左旋的操作相似,举个例子10,12,8,9,7,6
当添加6后,发现需要调整,调整的操作也为两步
第一步.创建新节点,
新结点的值=当前结点的值(也就是10);
新结点的右节点=当前节点的右节点(12)
新结点的左节点=当前结点的左结点的右节点(9)
第二步.修改当前节点
当前结点的值=当前节点的左节点的值(8)
当前节点的左子树=当前节点的左子树的左子树
当前节点的右子树=新结点
右旋方法
在add方法添上如下代码
if(this.leftHeigh()-this.rightHeigh()>1) {this.rightRotate();} 双旋但是当我们遇到这样的情况该怎么办呢?
如:左子树高>右子树---->采用右旋(但是当前节点的左子树的左子树高>它的左子树的右子树)
举例:10,7,11,6,8,9
7的左子树高(1)<右子树高(2)
我们发现直接右旋无法将其转化成平衡二叉树!
解决办法:
当我们发现:7的左子树高(1)<右子树高(2),先对7进行左旋,将其转化成左子树高>右子树高的形式,操作步骤如下图,
先将左子树(7)进行左旋之后,我们就可以直接将整棵树进行右旋了!
小结一下:当发现整个树需要右旋的时候,我们要先判断对于它的左子树,是否存在 它的左子树的左子树高<它的左子树的右子树高的情况,若存在,则需要先对左子树进行左旋!再对其进行右旋!
对于整棵树要先左旋的情况,我们要先判断对于它的右子树,是否存在 它的左=右子树的左子树高>它的左=右子树的右子树高的情况,若存在,则需要先对左子树进行右旋!再对整棵树进行左旋!
对add进行调整修改
至此,对于左旋,右旋,双旋的情况进行了详细的分析!建议大家在纸上画一下左旋右旋的示意图,希望对大家有帮助!
jjdyt老师数据结构与算法连接:
https://www.bilibili.com/video/BV1E4411H73v?p=135