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

更新时间:2023-10-23 来源:黑马程序员浏览量:

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

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

什么是平衡二叉树

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

1698056233442_二叉树.png

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

• 左左

• 左右

• 右右

• 右左

平衡二叉树-左左

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

平衡二叉树-左右

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

1698056876728_左右.png
平衡二叉树-右右

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

1698056696203_右右.png

平衡二叉树-右左

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

1698056778339_右左.png

最新资讯