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

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

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

什么是平衡二叉树

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

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

• 左左

• 左右

• 右右

• 右左

平衡二叉树-左左

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

平衡二叉树-左右

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

平衡二叉树-右右

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

平衡二叉树-右左

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