二叉搜索树

二叉搜索树介绍

二叉搜索树是由二叉树组成的专用于查找和搜索目的的一种数据结构。

要在二叉搜索树中查询一个结点，从根结点开始一层一层往下查找，直到找到目标结点为止。当遇到一个比目标结点值大的结点时，顺着该结点的左子树继续查找。如果遇到的结点值小于目标结点，则顺着该结点的右子树继续查找。

二叉搜索树是一种用于查找操作的高效数据结构，因为在最坏的情况下，只需要查找一个分支上的数据就可以了，而不用检索每一个数据。因此，查找操作的复杂度是O（lg n），这里n代表树中的结点个数。这里树必须是保持平衡的。

Note:
正式的说法是，如果满足树的所有叶子结点都在同一层上，或者所有叶子结点都在最后两层上，且倒数第二层是满的，则这棵树是平衡的。

二叉搜索树的实现与分析

将二叉搜索树实现为 AVL 树是保持一棵二叉搜索树平衡较好的方法。

AVL树（Adel’son-Vel’skii and Landis）是一种特殊类型的二叉树，它的每个结点都保存一份额外的信息：结点的平衡因子。结点的平衡因子是它的左子树高度减去它的右子树高度的结果（见下图）。当插入结点时，AVL树需要自我调整，使得所有结点的平衡因子保持为+1、-1或0。当子树的根结点平衡因子为+1时，它是左倾斜的（left-heavy）。当子树的根结点平衡因子为-1时，它是右倾斜的（right-heavy）。一棵子树的根结点的平衡因子就代表该子树的平衡性。保持所有子树几乎都处于平衡状态，AVL树在总体上就能够基本保持平衡。

当向AVL树中插入一个结点后，还有一些额外的工作要做。首先，必须计算因为执行了插入操作对平衡因子带来的改变。其次，如果任何平衡因子变为了±2，就必须从这个结点开始往下重新平衡这棵树，这个重新平衡的过程就称为旋转。

旋转操作用来重新平衡AVL树的某个部分。通过重新安排结点，同时又必须保持结点之间的关系仍然是左子结点小于父结点，父结点小于右子结点——即必须保持该树仍然是一棵二叉搜索树。旋转过后，旋转子树中的所有结点的平衡因子都为+1、-1或0。

共有4种旋转类型。它们是LL（left-left）、LR（left-right）、RR（right-right）和RL（right-left）旋转。

LL旋转

如下图所示，当x位于A的左子树的左子树上时，执行LL旋转。设left为A的左子树，要执行LL旋转，将A的左指针指向left的右子结点，left的右指针指向A，将原来指向A的指针改为指向left。旋转过后，将A和left的平衡因子都改为0。所有其他结点的平衡因子没有发生改变。

LR旋转

如下图所示，当x位于A的左子树的右子树上时，执行LR旋转。设left是A的左子结点，并设A的子孙结点grandchild为left的右子结点。要执行LR旋转，将left的右子结点指向grandchild的左子结点，grandchild的左子结点指向left,A的左子结点指向grandchild的右子结点，再将grandchild的右子结点指向A，最后将原来指向A的指针指向grandchild。

执行LR旋转之后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子值。如果grandchild结点的原始平衡因子为+1，就将A的平衡因子设置为-1，将left结点的平衡因子设置为0。如果grandchild结点的原始平衡因子为0，就将A和left结点的平衡因子都设置为0。如果grandchild结点的原始平衡因子为-1，就将A的平衡因子设置为0，将left的平衡因子置为+1。在所有情况下，grandchild的新平衡因子都是0。所有其他结点的平衡因子都没有改变。

RR旋转

当x位于A的右子树的右子树上时，执行RR旋转。RR旋转与LL旋转是对称的关系。设A的右子结点为right。要执行RR旋转，将A的右指针指向right的左子结点，right的左指针指向A，原来指向A的指针修改为指向right。完成旋转后，将A和left的平衡因子都修改为0。所有其他结点的平衡因子都没有改变。

RL旋转

当x位于A的右子树的左子树上时，执行RL旋转。RL旋转与LR旋转是对称的关系。设A的右子结点为right,right的左子结点为grandchild。要执行RL旋转，将right结点的左子结点指向grandchild的右子结点，将grandchild的右子结点指向right，将A的右子结点指向grandchild的左子结点，将grandchild的左子结点指向A，最后将原来指向A的指针指向grandchild。

执行RL旋转之后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子。这里也有三种情况需要考虑：如果grandchild结点的原始平衡因子值为+1，将A的平衡因子更新为0，right的平衡因子设置为-1。如果grandchild的原始平衡因子为0，将A和left的平衡因子都更新为0。如果grandchild的原始平衡因子为-1，将A的平衡因子设置为+1，而将left的平衡因子设置为0。在所有情况中，都将grandchild的新平衡因子设为0。所有其他结点的平衡因子不发生改变。

由于要保持一棵二叉搜索树的平衡状态，需要每个结点除了存储数据外，还需要存储一些额外的信息。数据结构AvlNode代表树中的结点。AvlNode包含3个成员：data是存储在结点中的数据，hidden用来标识结点是否已经移除的一个成员，factor则代表该结点的平衡因子。

插入节点到AVL树

bistree_insert将一个结点插入二叉搜索树中。该操作按照递归的方式调用bitree_insert来找到结点应该插入的位置。一旦插入结点，就需要更新相关结点的平衡因子，更新操作在递归的回归过程中完成。如果在处理的过程中有任何结点的平衡因子的绝对值为2，都需要执行一次旋转。

从检查是否将结点插入空树开始。如果是这种情况，简单地将结点设为根结点，并设它的平衡因子为AVL_BALANCED。否则，将待插入结点的数据与当前结点的数据相比较，以此来判断需要往哪个方向移动（左子树还是右子树）。我们按照前面介绍过的方法来处理插入操作。当要插入的结点数据小于当前结点的数据时，递归调用该函数使我们移动到左边。当待插入的结点数据大于当前结点的数据时，递归调用该函数将使我们移动到右边。一旦找到了插入的位置，就动态分配一个AvlNode结构体，并将其插入树中，作为当前结点的子结点。如果待插入结点的数据恰好与某个隐藏结点的数据一致（由于执行了移除操作，使结点成为隐藏的，但并未真正移除），就销毁当前结点中的数据，将新的数据插入原来的位置上，并标识该结点不再为隐藏的。在这种情况下，不需要重新平衡树。

除了替换先前隐藏的节点之外，接下来需要评估树的平衡性受到的影响，这样如果有必要的话可以对其修复。不论结点插入左边还是右边，都用balanced来表示插入操作是否破坏了树的平衡性。这导致执行一条用来调整当前结点的平衡因子的switch语句。调整当前结点的平衡因子反过来可能会导致该结点上层的结点平衡因子被打乱。因此，每次调用insert操作时，如果balanced为0，就遍历树当前这一层的所有结点，并更新结点的平衡因子。一旦发现没有结点需要更新了，就将balanced设置为1，以此表示之前的操作已经完成。

switch语句决定如何更新平衡因子，也决定何时应该执行旋转操作。实际用来执行旋转操作的函数要么是rotate_left要么是rotate_right，它们决定旋转的类型：如果调用rotate_left则是LL或者LR；如果调用rotate_right则是RR或RL。由于旋转操作会改变结点的平衡因子，因此每个旋转函数也会修正平衡因子。理解更新平衡因子和执行旋转操作的最好方式就是追踪下图中给出的例子。

二叉搜索树抽象数据类型的头文件

/*****************************************************************************
*                                                                            *
*  ------------------------------- bistree.h ------------------------------  *
*                                                                            *
*****************************************************************************/

#ifndef BISTREE_H
#define BISTREE_H

#include "bitree.h"

/*****************************************************************************
*                                                                            *
*  Define balance factors for AVL trees.                                     *
*                                                                            *
*****************************************************************************/

#define            AVL_LFT_HEAVY         1
#define            AVL_BALANCED          0
#define            AVL_RGT_HEAVY        -1

/*****************************************************************************
*                                                                            *
*  Define a structure for nodes in AVL trees.                                *
*                                                                            *
*****************************************************************************/

typedef struct AvlNode_ {

void               *data;
int                hidden;
int                factor;

} AvlNode;

/*****************************************************************************
*                                                                            *
*  Implement binary search trees as binary trees.                            *
*                                                                            *
*****************************************************************************/

typedef BiTree BisTree;

/*****************************************************************************
*                                                                            *
*  --------------------------- Public Interface ---------------------------  *
*                                                                            *
*****************************************************************************/

void bistree_init(BisTree *tree, int (*compare)(const void *key1, const void
   *key2), void (*destroy)(void *data));

void bistree_destroy(BisTree *tree);

int bistree_insert(BisTree *tree, const void *data);

int bistree_remove(BisTree *tree, const void *data);

int bistree_lookup(BisTree *tree, void **data);

#define bistree_size(tree) ((tree)->size)

#endif

实际上红黑树的统计性能比 AVL 树更好，红黑树也是一种平衡搜索树。