数据结构：二叉查找树

gaunthan Posted on Jan 5 2017

? Searching ? ? Data Structures ?

## 定义
二叉查找树是一棵特殊的[二叉树](http://leanote.com/blog/post/5872478eab6441209e017c58)，它在二叉树的基础上附加了该性质：对于树中的每个结点X，它的左子树中所有关键字都小于或等于X的关键字，而它的右子树中所有关键字都大于或等于X的关键字。如下图所示：

![](https://leanote.com/api/file/getImage?fileId=587e3cb0ab644121e3000959)

查找树的设计目标都是减少最坏情况下单次操作的时间，但是由于查找树的典型应用经常需要执行一系列的查找操作，因此此时更关心的性能指标是所有这些操作总共需要多少时间。对于此类应用，更好的目标就是降低操作的摊还时间，此处的摊还时间是指在一系列最坏情况下的操作序列中单次操作的平均时间。获得摊还效率的一种方法就是使用“自调整”的数据结构。

中序遍历二叉查找树，可以得到有序的序列，尽管这不是创建二叉查找树的目的。创建二叉查找树的目的是提高查找、插入和删除关键字的速度。

## 实现
### 头文件声明
```C
#ifndef BIN_SEARCH_TREE_H
#define BIN_SEARCH_TREE_H

/* Type define */

struct BinTreeNode;
typedef struct BinTreeNode* PtrToNode;
typedef struct PtrToNode BinSearchTree;
 
/* Interface declaration */

BinSearchTree MakeEmpty(BinSearchTree T);
PtrToNode Find(ElemType X, BinSearchTree T);
PtrToNode FindMin(BinSearchTree T);
PtrToNode FindMax(BinSearchTree T);
BinSearchTree Insert(ElemType X, BinSearchTree T);
BinSearchTree Delete(ElemType X, BinSearchTree T);
ElemType Retrieve(PtrToNode p);
 
#endif /* BIN_SEARCH_TREE_H */
```

### 结构体定义
```C
/* Place in implement file. */
struct BinTreeNode {
    ElemType elem;
    strcut BinTreeNode* left;
    strcut BinTreeNode* right;
};
```

## 关键操作
### MakeEmpty()
这项操作主要用于初始化，使树置空:
```C
BinSearchTree MakeEmpty(BinSearchTree T)
{
    if(T != NULL) {
        MakeEmpty(T->left);
        MakeEmpty(T->right);
        free(T);
    }
    return NULL;
}
```

### Find()
这个操作一般需要返回指向树T中具有关键字X的结点的指针，如果这样的结点不存在则返回NULL:
```C
PtrToNode Find(ElemType X, BinSearchTree T)
{
    if(T == NULL)   return NULL;
    
    if(X < T->elem)
        return Find(X, T->left);
    else if(X > T->elem)
        return Find(X, T->right);
    else
        return T;
}
```

### FindMin()
这个例程返回树中最小元的位置。从根开始并且只要有左儿子就向左进行，终止点就是最小的元素:
```C
PtrToNode FindMin(BinSearchTree T)
{
    if(T != NULL) {
        while(T->left != NULL)
            T = T->left;                         
    }
    return T;
}
```

### FindMax()
这个例程返回树中最大元的位置。从根开始并且只要有右儿子就向右进行，终止点就是最大的元素:
```C
PtrToNode FindMax(BinSearchTree T)
{
    if(T != NULL) {
        while(T->right != NULL)
            T = T->right;                         
    }
    return T;
}
```

### Insert()
为了将X插入到树T中，可以像Find那样沿着树查找。如果找到X，则什么都不用做（或做一些更新）。否则，将X插入到遍历的路径上的最后一点:
```C
BinSearchTree Insert(ElemType X, BinSearchTree T)
{
    if(T == NULL) {
        /* Create and return a one-node tree */
        T = (BinSearchTree)malloc(sizeof(struct BinTreeNode));
        
        if(T == NULL) {
            puts("Out of space!");
            return NULL;
        }
        T->elem = X;
        T->left = T->right = NULL;
    }else if(X < T->elem) {
        T->left = Insert(X, T->left);
    }else if(X > T->elem) {
        T->right = Insert(X, T->right);
    }
    /* Else X is in the tree already;we'll do nothing */
     
    return T;
}
```

### Delete()
正如许多数据结构一样，最困难的操作是删除。要根据情况进行不同的删除操作:

- 结点是树叶：直接删除。
- 结点只有一个儿子：调整其父指针绕过该结点指向它的儿子。
- 结点有两个儿子：用该结点的右子树的最小的数据代替该结点的数据，并递归地删除这个被使用的最小树叶。

实现如下：
```C
BinSearchTree Delete(ElemType X, BinSearchTree T)
{
    PtrToNode tmp;
     
    if(T == NULL) {
        puts("Element not found!");
    }else if(X < T->elem) {        /* Go left */
        T->left = Delete(X, T->left);
    }else if(X > T->elem) {        /* Go right */
        T->right = Delete(X, T->right);
    }else {    /* Found element to be deleted */
        if(T->left && T->right) {   /* Two children */
            /* Replace with smallest in right subtree */
            tmp = FindMin(T->right);
            T->elem = tmp;
            T->right = Delete(T->elem, T->right);
        }else {   /* One/Zero children */
            tmp = T;
            if(T->left == NULL) {
                T = T->right;
            }else if(T->right == NULL) {
                T = T->left;
            }
            free(tmp);
        }
    }
    return T;
}
```

如果删除的次数不多，则通常使用的策略是**懒惰删除**(lazy deletion)：当一个元素要被删除时，它仍留在树中，只是做了个被删除的记号。这种做法特别是在有重复关键字时很流行，因为此时记录出现频率数的域可以减1。如果树中的实际结点数和“被删除”的结点数相同，那么树的深度预计只上升一个小的常数。