红黑树对比二叉树好处有哪些,二叉树到底有啥用

首页 > 经验 > 作者:YD1662022-11-14 14:26:52

在插入之前树是一颗AVL树,而插入之后结点T的左右子树高度差的绝对值不再 < 1,此时AVL树的平衡性被破坏,我们要对其进行旋转。由上图可知我们是在结点T的左结点的左子树上做了插入元素的操作,我们称这种情况为左左情况,我们应该进行右旋转(只需旋转一次,故是单旋转)。具体旋转步骤是:

T向右旋转成为L的右结点,同时,Y放到T的左孩子上。这样即可得到一颗新的AVL树,旋转过程图如下:

红黑树对比二叉树好处有哪些,二叉树到底有啥用(9)

另一个:

红黑树对比二叉树好处有哪些,二叉树到底有啥用(10)

以上就是插入操作时的单旋转情况!我们要注意的是:谁是T谁是L,谁是R还有谁是X,Y,Z!T始终是开始不平衡的左右子树的根节点。显然L是T的左结点,R是T的右节点。X、Y、Y是子树当然也可以为NULL.NULL归NULL,但不能破坏插入时我上面所说的左左情况或者右右情况。

AVL树的插入,双旋转的第一种情况---左右(先左后右)旋#

红黑树对比二叉树好处有哪些,二叉树到底有啥用(11)

我们在T结点的左结点的右子树上插入一个元素时,会使得根为T的树的左右子树高度差的绝对值不再 < 1,如果只是进行简单的右旋,得到的树仍然是不平衡的。我们应该按照如下图所示进行二次旋转:

红黑树对比二叉树好处有哪些,二叉树到底有啥用(12)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.