内容简介：在文章什么是 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。
右旋转其实很简单，按照下面的操作即可：
TreeNode *t3 = x.right;
x.right = y;
y.left = t3;
旋转后的 AVL 树是这样的，旋转后任然满足 BST 的条件，可以通过 T1 < z < T2 < x < T3 < y < T4 这个条件推导：
左旋转
当右子树发生不平衡时， 右子树的高度比左子树的高度大于 1 ，需要进行「左旋转」。比如下面这颗树失去了平衡性，不平衡节点为 Y，满足：T4<Y<T3<X<T2<Z<T1：
左旋转其实很简单，按照下面的操作即可：
TreeNode *t3 = x.left;
x.left = y;
y.right = t3;
旋转后的 AVL 树是这样的，旋转后任然满足 BST 的条件：
至此，我们学习了什么是 AVL 树，当由于插入新节点破坏 AVL 树的平衡性后（平衡因子不为 -1、0、1），通过左、右旋转来重新达到平衡性。 前面我们也动手用 Swift 实现了一颗 BST（二分搜索树） 使用 Swift 实现一颗二分搜索树 。 这一切其实都是为了下一篇文章做准备： 用 Swift 实现一颗 AVL 树。
推荐阅读：
图解数据结构和算法
以上所述就是小编给大家介绍的《AVL 树的左旋转、右旋转》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- C语言数组中字符串的旋转（左旋与右旋）
- 数据结构-AVL 左旋和右旋
- leetcode - 189. 旋转数组
- 【Leetcode】61.旋转链表
- 圆环旋转加显隐的加载效果
- 通过优雅的方式强制旋转屏幕
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
大型网站系统与Java中间件开发实践
曾宪杰 / 电子工业出版社 / 2014-4-24 / 65.00
本书围绕大型网站和支撑大型网站架构的 Java 中间件的实践展开介绍。从分布式系统的知识切入，让读者对分布式系统有基本的了解；然后介绍大型网站随着数据量、访问量增长而发生的架构变迁；接着讲述构建 Java 中间件的相关知识；之后的几章都是根据笔者的经验来介绍支撑大型网站架构的 Java 中间件系统的设计和实践。希望读者通过本书可以了解大型网站架构变迁过程中的较为通用的问题和解法，并了解构建支撑大型......一起来看看 《大型网站系统与Java中间件开发实践》 这本书的介绍吧!
