平衡二叉树是什么？平衡二叉树旋转的4种情况

- 日理万妓 2024-02-21 11:29 13阅读 0赞

二叉查找树的作用是提高检索数据的性能， 小的存左边，大的存右边，一样的不存。但出现瘸子现象，导致查询的性能与单链表一样，拉低查询速度。

这时候需要用到平衡二叉树，在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

![format_png][]

什么是平衡二叉树

可以从以下二叉树中找到平衡二叉树的特点，任意节点的左右两个子树的高度差不超过1，**任意节点的左右两个子树都是一颗平衡二叉树**。

![format_png 1][]

平衡二叉树在添加元素后可能导致不平衡，基本策略是进行左旋，或者右旋保证平衡。旋转可能出现的四种情况：

• 左左

• 左右

• 右右

• 右左

平衡二叉树-左左

当根节点左子树的左子树有节点插入，导致二叉树不平衡。

![format_png 2][]

平衡二叉树-左右

当根节点左子树的右子树有节点插入，导致二叉树不平衡

![format_png 3][]

平衡二叉树-右右

当根节点右子树的右子树有节点插入，导致二叉树不平衡

![format_png 4][]

平衡二叉树-右左

当根节点右子树的左子树有节点插入，导致二叉树不平衡

![format_png 5][]

[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/0a6df31cdf3c475ab93ff08d4824b0ed.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/3f3649cc09e443419d7611204b9fa282.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6c686d92295346cb9a6415e494104b8f.png
[format_png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/6e2c10662f884484b30236c6a881fc93.png
[format_png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/393f8be72d7741e58c766c9ce99779b3.png
[format_png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/0e7a2fbccf9240c09e6f2bbd052745a4.png