【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。 (3)

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

 

这是一种比查找二叉树还特别的树哦,这种树就可以帮助我们解决二叉查找树刚才的那种所有节点都倾向一边的缺点的。具有如下特性:

 

具有二叉查找树的全部特性。

每个节点的左子树和右子树的高度差至多等于1。

 

例如:图一就是一颗AVL树了,而图二则不是(节点右边标的是这个节点的高度)。

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

 

对于图二,因为节点9的左孩子高度为2,而右孩子高度为0。他们之间的差值超过1了。

 

这种树就可以保证不会出现大量节点偏向于一边的情况了。

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

听起来这种树还不错,可以对于图1,如果我们要插入一个节点3,按照查找二叉树的特性,我们只能把3作为节点4的左子树插进去,可是插进去之后,又会破坏了AVL树的特性,那我们那该怎么弄?

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

右旋

 

我们在进行节点插入的时候,可能会出现节点都倾向于左边的情况,例如:

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

我们把这种倾向于左边的情况称之为 左-左型。这个时候,我们就可以对节点9进行右旋操作,使它恢复平衡。

 

【漫画】以后在有面试官问你平衡(AVL)树,你就把这篇文章扔给他。

 

即:顺时针旋转两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子

 

再举个例子:

 

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwygw.html