1int Search_Seq(SSTable ST, KeyType key) {
2    // 在顺序表ST中顺序查找其关键字等于key的数据元素。
3    // 若找到，则函数值为该元素在表中的位置，否则为0。
4    int i = 0;
5    ST.elem[0].key = key;	// 设置哨兵
6    // 从后往前找
7    for(i = ST.length; ST.elem[i].key != key; --i) ;
8    return i;  // 找不到时，i为0
9}

 1int Search_Bin(SSTable ST, KeyType key) {
 2    // 置区间初值
 3    int low = 1;
 4    int high = ST.length;
 5    while(low <= high) {
 6        int mid = (low + high) / 2;
 7        if(key == ST.elem[mid].key) {
 8            return  mid;	    // 找到待查元素
 9        }
10        else if(key < ST.elem[mid].key) {
11            high = mid - 1;     // 继续在前半区间进行查找
12        }
13        else {
14            low = mid + 1;      // 继续在后半区间进行查找
15        }
16    }
17    return 0;                   // 顺序表中不存在待查元素
18}

1// 二叉排序树的定义
2typedef struct BiTNode {
3    TElemType data;
4    struct BiTNode  *lchild, *rchild;	// 左右指针
5 } BiTNode, *BiTree;

 1BiTree SearchBST(BiTree T, KeyType key) {	
 2    // 查找不成功，返回空
 3    if (!T) {
 4        return NULL;
 5    }
 6    // 查找成功，返回树根
 7    else if( key == T->data.key ) {
 8        return T;
 9    }
10    else if( key < T->data.key ) {
11        // 在左子树中继续查找
12        return SearchBST(T->lchild, key);
13    }
14    else {
15        // 在右子树中继续查找
16        return SearchBST(T->rchild, key); 
17    }
18}

 1// 更新搜索算法：f指向T的双亲，p记录查找位置
 2bool SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {	
 3    // 查找不成功
 4    if(!T) {
 5        p = f;
 6        return false;
 7    }
 8    // 查找成功
 9    else if(key == T->data.key) {			
10        p = T;
11        return true;
12    }
13    else if(key < T->data.key) {
14        return SearchBST(T->lchild, key, T, p);
15    }
16    else {
17        return SearchBST(T->rchild, key, T, p);
18    }
19}
20
21// 插入算法
22bool InsertBST(BiTree &T, ElemType e) { 
23    if (!SearchBST (T, e.key, NULL, p)) {
24        BiNode *s = new BiTNode;      // 为新结点分配空间
25        s->data = e;
26        s->lchild = s->rchild = NULL;  
27        if(!p) {
28            T = s;            // 插入 s 为新的根结点
29        }
30        else if(e.key < p->data.key) {
31            p->lchild = s;    // 插入 *s 为 *p 的左孩子
32        }
33        else {
34            p->rchild = s;    // 插入 *s 为 *p 的右孩子
35        }
36        return true;
37    }
38    else {
39        return false;
40    }
41}

 1/* ----- 删除主函数 ----- */
 2bool DeleteBST(BiTree &T, KeyType key, BiTree &f) {
 3    if (!T) {
 4        return false;       // 不存在关键字等于 key 的数据元素
 5    }
 6    else {
 7        // 找到关键字等于 key 的数据元素
 8        if(key == T->data.key) { 
 9            Delete(T, f);  
10            return true; 
11        }
12        // 继续在左子树中查找
13        else if(key < T->data.key) {    
14            return DeleteBST(T->lchild, key, T);
15        }
16        // 继续在右子树中查找
17        else {  
18            return DeleteBST(T->rchild, key, T);
19        }
20    }
21}
22
23/* ----- 删除操作过程 ----- */
24void Delete(BiTree &p, BiTree f) {
25    BiTree *q = (BiTree*)malloc(sizeof(BiTree));
26    // 从二叉排序树中删除结点 p，并重接它的左子树或右子树
27
28    // 右子树为空树，则只需重接它的左子树
29    if(!p->rchild)  {	
30        q = p;
31        p = p->lchild;
32        if(f->lchild == q) {
33            f->lchild = p; 
34        }
35        else if(f->rchild == q) {
36            f->rchild = p;
37        }
38        delete(q);	
39    } 
40    // 左子树为空树，只需重接它的右子树
41    else if(!p->lchild) {	
42        q = p;
43        p = p->rchild;
44        if (f->lchild == q) {
45            f->lchild = p;
46        }
47        else if(f->rchild == q) {
48            f->rchild = p;
49        }
50        delete(q);
51    } 
52    // 左右子树均不空
53    else {	
54        q = p;  
55        s = p->lchild;
56        while (s->rchild) {
57            q = s;	
58            s = s->rchild;
59        }	// s 指向被删结点的前驱
60        p->data = s->data;
61        // 重接*q的左子树
62        if(q != p ) {
63            q->rchild = s->lchild;
64        }
65        else {
66            q->lchild = s->lchild;
67        }
68        delete(s);	
69    }
70}

 1// 右旋算法
 2void R_Rotate(BSTree &p){
 3    lc = p->lchild;
 4    p->lchild = lc->rchild;
 5    lc->rchild = p;
 6    p = lc;
 7}
 8
 9// 左旋算法 
10void L_Rotate(BSTree &p){
11    rc = p->rchild;
12    p->rchild = rc->lchild;
13    rc->lchild = p;
14    p = rc;
15} 
16
17// 左平衡算法
18#define LH 1    // 左高
19#define EH 0    // 等高
20#define RH -1   // 右高
21
22void LeftBalance(BSTree &T) {	// T对应图中的树根A
23    lc = T->lchild;             // lc对应图中的树根B
24    switch(lc->bf) {           // 看T的左子(B)，只能是LL或LR型
25        // 左左->右旋（LL型）
26        case LH:                
27            T->bf = lc->bf = EH;
28            R_Rotate(T);
29            break;
30        // LR型，先左旋后右旋
31        case RH:
32            rd = lc->rchild; 	// 结点C
33            switch(rd->bf) {	// 修改BF值
34                case LH:	
35                    T->bf = RH;
36                    lc->bf = EH;
37                    break;
38                case EH:	
39                    T->bf = lc->bf = EH;
40                    break;
41                case RH:
42                    T->bf = EH; 
43                    lc->bf = LH;
44                    break;
45            }
46            rd->bf = EH;
47            L_Rotate(T->lchild);	
48            R_Rotate(T);
49    }
50}