AVL 树的左旋转、右旋转

栏目: 编程工具 · 发布时间: 5年前

内容简介:在文章什么是 AVL 树?中,我们讲解了 AVL 树的基本概念,以及它存在的意义。这篇文章,我们来讲解如何维护 AVL 树的平衡性。AVL树是一棵「自平衡」的 BST(二分搜索树),也就说,它需要一种机制来维护 BST 的平衡性。这种机制就是左旋转和右旋转。右旋转「旋转」其实就是移动 BST 中节点的位置,使节点的平衡因子为0、-1、1。当左子树发生不平衡,需要使用右旋转来达到平衡性。图中的节点 Y(4)为不平衡节点,T1,T2,T3,T4 均平衡,满足 T1 < z < T2 < x < T3 < y <

在文章什么是 AVL 树?中,我们讲解了 AVL 树的基本概念,以及它存在的意义。这篇文章,我们来讲解如何维护 AVL 树的平衡性。AVL树是一棵「自平衡」的 BST(二分搜索树),也就说,它需要一种机制来维护 BST 的平衡性。这种机制就是左旋转和右旋转。

右旋转

「旋转」其实就是移动 BST 中节点的位置,使节点的平衡因子为0、-1、1。当左子树发生不平衡,需要使用右旋转来达到平衡性。图中的节点 Y(4)为不平衡节点,T1,T2,T3,T4 均平衡,满足 T1 < z < T2 < x < T3 < y < T4。

AVL 树的左旋转、右旋转

右旋转其实很简单,按照下面的操作即可:


 

TreeNode *t3 = x.right;

x.right = y;

y.left = t3;

旋转后的 AVL 树是这样的,旋转后任然满足 BST 的条件,可以通过 T1 < z < T2 < x < T3 < y < T4 这个条件推导:

AVL 树的左旋转、右旋转

左旋转

当右子树发生不平衡时, 右子树的高度比左子树的高度大于 1 ,需要进行「左旋转」。比如下面这颗树失去了平衡性,不平衡节点为 Y,满足:T4<Y<T3<X<T2<Z<T1:

AVL 树的左旋转、右旋转

左旋转其实很简单,按照下面的操作即可:


 

TreeNode *t3 = x.left;

x.left = y;

y.right = t3;

旋转后的 AVL 树是这样的,旋转后任然满足 BST 的条件:

AVL 树的左旋转、右旋转

至此,我们学习了什么是 AVL 树,当由于插入新节点破坏 AVL 树的平衡性后(平衡因子不为 -1、0、1),通过左、右旋转来重新达到平衡性。 前面我们也动手用 Swift 实现了一颗 BST(二分搜索树) 使用 Swift 实现一颗二分搜索树 这一切其实都是为了下一篇文章做准备: 用 Swift 实现一颗 AVL 树。

推荐阅读:

图解数据结构和算法

AVL 树的左旋转、右旋转


以上所述就是小编给大家介绍的《AVL 树的左旋转、右旋转》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

硅谷之火

硅谷之火

保罗·弗赖伯格、迈克尔·斯韦因 / 张华伟 编译 / 中国华侨出版社 / 2014-11-1 / CNY 39.80

《硅谷之火:人与计算机的未来》以生动的故事,介绍了计算机爱好者以怎样的创新精神和不懈的努力,将计算机技术的力量包装在一个小巧玲珑的机壳里,实现了个人拥有计算机的梦想。同时以独特的视角讲述了苹果、微软、太阳微系统、网景、莲花以及甲骨文等公司的创业者们在实现个人计算机梦想的过程中创业的艰辛、守业的艰难、失败的痛苦,在激烈竞争的环境中奋斗的精神以及在技术上不断前进的历程。一起来看看 《硅谷之火》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具