实现二叉搜索树的一种好方法是利用二叉树抽象数据类型。我们以BisTree这个名称来代表二叉搜索树这种数据结构。通过typedef方式将BisTree(二叉搜索树)实现为BiTree（二叉树）的别名。

采用typedef方法使得二叉搜索树具有了某种程度的多态能力，如同栈和队列一样。这意味着除了专属于二叉搜索树的操作外，还可以在其上执行属于二叉树的操作。

数据结构AvlNode代表树中的结点，AvlNode包含3个成员：

data是存储在结点中的数据；hidden用来标识结点是否已经移除；factor则代表该结点的平衡因子。

我们使用标识符来标识平衡因子可能的值：AVL_LEFT_HEAVY定义为1，AVL_BALANCED定义为0，AVL_RGT_HEAVY定义为-1。

示例代码1：二叉搜索树抽象数据类型的头文件

/*bistree.h*/
#ifndef BISTREE_H
#define BISTREE_H

#include "bitree.h"

/*定义平衡因子的标识符*/
#define AVL_LFT_HEAVY 1
#define AVL_BALANCED  0
#define AVL_RGT_HEAVY -1

/*定义AVL树中节点的数据结构*/
typedef struct AvlNode_
{
    void *data;
    int hidden;
    int factor;
}AvlNode;

/*通过typedef方式将BisTree(二叉搜索树)实现为BiTree（二叉树）*/
typedef BiTree BisTree;

/*公用接口部分*/
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 // BISTREE_H

bistree_init

该操作用来初始化一棵二叉树。由于二叉搜索树实际上也是一棵二叉树，因此调用bitree_init来完成初始化工作。这里需要显示地将compare成员设置为指定的比较函数，该成员在二叉树中并没有使用到。

bistree_init的时间复杂度和bitree_init一样都是O(1)。

bistree_destroy

该操作用来销毁一棵二叉树。为了实现该操作，引入两个额外的辅助函数destroy_left和destroy_right。这两个函数按照递归的方式销毁某个结点下方的左右子树。针对二叉搜索树，需要单独的析构函数来销毁AvlNode中数据成员所引用的空间以及AvlNode结构体本身所占用的资源。

bistree_destroy的时间复杂度同bitree_destroy一样，都是O(n)，这里的n代表树中的结点个数。

bistree_insert

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

从检查是否将结点插入空树开始，如果是这种情况，简单的将结点设为根结点，并设它的平衡因子为AVL_BALANCED。

否则，将待插入结点的数据与当前结点的数据相比较，以此来判断需要往哪个方向移动（左子树还是右子树）。当要插入的结点数据小于当前结点的数据时，递归调用该函数使我们移动到左边。当待插入结点的数据大于当前结点的数据时，递归调用该函数将使我们移动到右边。一旦找到了插入的位置，就动态分配一个AvlNode结构体，并将其插入树中，作为当前结点的子结点。

如果待插入结点的数据恰好与某个隐藏的结点的数据一致（由于执行了移除操作，使结点成为隐藏的，但并未真正移除），就销毁当前结点中的数据，将新的数据插入到原来的位置上，并标识该结点不再为隐藏的。在这种情况下不需要再平衡树。

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

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

和插入一颗完全平衡的二叉树中一样，它们的时间复杂度都是O(lgn)。

结合下图可以更好的理解更新平衡因子和执行旋转操作：

bistree_remove

该操作将一个节点从二叉搜索树中移除。但它只是将结点隐藏起来而不是真正的移除，我们称之为“惰性移除”。

要隐藏一个结点，将AvlNode结构中的hidden成员设置为1。如果稍后插入同样的数据，只需简单的将hidden成员再次设置为0。

如果移除的结点数目很大，可能就需要考虑将结点真正的移除并重新调整树的结构。

要定位隐藏的结点，以递归的方式调用hide，直到找到目标为止。一旦将结点隐藏了，就没有必要重新平衡树了，因为并没有对树的结构做任何修改。因此，直接将balanced值设置为1。

从AVL树中移除结点的过程分析同插入结点一样，因此bistree_remove的时间复杂度为O(lg n)。

 从AVL移除结点的过程分析同插入结点一样，因此，bistree_remove的时间复杂度为O(lgn)。

bistree_lookup

该操作用来在二叉搜索树中查找结点。返回一个指向AvlNode结构体中数据域成员的指针。该操作通过递归的方式调用lookup，从根结点开始，逐层降低遍历树的结点，直到找到目标结点为止。在每个层级上，我们首先检查是否到达了分支的边缘。如果我们处于分支的边缘就说明我们要找的结点不存在。否则，我们要么移动到左子结点，要么移动到右子结点，移动方式同前面介绍过的bistree_insert一样。当我们遇到目标结点时，递归终结，此时返回0。