二叉查找树和AVL树


知识准备

二叉树基础请见:二叉树基础

1 二叉查找树

二叉查找树又称二叉搜索树(Binary Search Tree)或二叉排序树(Binary Sort Tree)。其或者是一棵空树,或者是具有下列性质的二叉树:

1 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
3 左、右子树也分别为二叉排序树;
4 没有键值相等的节点(no duplicate nodes)。

二叉查找树

**二叉查找树的平均深度是O(logN)**,所以查询速度是非常快的,实际使用也非常多。但是从定义我们可以知道,二叉查找树可以任意地构造,同样是上图六个数字,也可以按照下图的方式来构造:

二叉查找树

这样这棵二叉树的查询效率就变得很低了。因此若想二叉树的查询效率尽可能高,需要这棵二叉树是平衡的,从而引出新的定义——平衡二叉树,或称AVL树。

2 平衡二叉树(AVL树)

平衡二叉树(AVL树)是在符合二叉查找树的条件下,还满足如下性质的二叉树:

任何节点的两个子树的高度最大差为1

下面的两张图片,左边是AVL树,它的任何节点的两个子树的高度差<=1;右边的不是AVL树,其根节点的左子树高度为3,而右子树高度为1。

AVL树与非AVL树对比

如果在AVL树中进行插入或删除节点,可能导致AVL树失去平衡,这种失去平衡的二叉树可以概括为四种姿态:LL(左左)、RR(右右)、LR(左右)、RL(右左)。它们的示意图如下:

AVL树失去平衡

AVL树失去平衡之后,可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。

LL旋转

LL失去平衡的情况下,可以通过一次旋转让AVL树恢复平衡。步骤如下:

  1. 将根节点的左孩子作为新根节点。
  2. 将新根节点的右孩子作为原根节点的左孩子。
  3. 将原根节点作为新根节点的右孩子。

LL旋转示意图如下:

LL旋转

RR旋转

RR失去平衡的情况下,可以通过一次旋转让AVL树恢复平衡,旋转方法与LL旋转对称。步骤如下:

  1. 将根节点的右孩子作为新根节点。
  2. 将新根节点的左孩子作为原根节点的右孩子。
  3. 将原根节点作为新根节点的左孩子。

RR旋转示意图如下:

LL旋转

LR旋转

LR失去平衡的情况下,需要进行两次旋转。步骤如下:

  1. 围绕根节点的左孩子进行RR旋转。
  2. 围绕根节点进行LL旋转。

LR旋转示意图如下:

LL旋转

RL旋转

RL失去平衡的情况下也需要进行两次旋转,旋转方法与LR旋转对称。步骤如下:

  1. 围绕根节点的右孩子进行LL旋转。
  2. 围绕根节点进行RR旋转。

RL旋转示意图如下:

LL旋转

从这四种旋转可以看出,首先我们应该判断失去平衡的树是LL、RR、LR、RL,然后针对性的进行旋转,然后就可以重新把树转化成平衡树。

平衡二叉树和avl树的C++示例代码如下:

1
(待整理)。