@quinn 2015-04-14T10:20:07.000000Z 字数 8899 阅读 2731

搜索（2）：二叉搜索树 BST

搜索算法

搜索（2）：二叉搜索树 BST

1. 二分搜索

将分治法应用于基于数组符号表的顺序搜索中，可以大大降低大型数据集合的搜索时间。
把数据集合分成两部分，确定搜索关键字属于哪一部分，然后集中处理那一部分。划分依据的一种合理方式是：保持数据项有序。此方法称为二分搜索。

//基于数组的符号表的二分搜索
Item Search(int l, int r, Key v);
Item BinarySearch(Key v)
{
    Search(0, N-1, v);
}
Item Search(int l, int r, Key v)
{
    if(r < l)
        return NULLItem;
    int m = (l+r) / 2;
    //int m = l + (r-l) * (v-Key(l)) / (Key(a[r])-Key(a[l]));//改进--插值搜索
    if(eq(Key(st[m]), v)
        return st[m];
    if(r == l)
        return NULLItem;
    if(less(v, Key(st[m]))
        return Search(l, m-1, v);
    else
        return Search(m, r, v);
}

二分搜索的一种改进方法：更精确的猜测搜索关键字将落入当前区间的什么位置，而不是盲目选择中间元素。这种方法称为插值搜索。
将上述

int m = (l+r) / 2;

改为

int m = l + (r-l) * (v-Key(l)) / (Key(a[r])-Key(a[l]));//改进--插值搜索

2. 二叉搜索树

为解决插入开销高的问题，二叉搜索树允许我们使用一种搜索、插入、选择和排序的快速且性能中等的算法。
定义：二叉搜索树（binary search tree, BST）是一棵二叉树，它的每个内部节点都关联一个关键字。有以下性质：每个左节点都小于它的根节点，每个右节点都大于它的根节点。
性能特征:算法在二叉搜索树上的运行时间与树的形状无关。在树是完美平衡（完全二叉树）的情况下，根节节点与外部节点（叶节点）之间大约有 $lgN$ 个节点；最坏情况下有 $N$ 个节点。

2.1 二叉搜索树的初始化、插入、搜索

typedef char Item;
typedef int Key;
typedef struct BSTree* Link;
struct BSTree
 {
    Item item;
    Link left;
    Link right;
    int N; //引入计数，是为了实现select操作
 }; 
 static Link head, z;
//=====新建一个节点=====
Link NewItem(Item item, Link left, Link right, int N)
{
    Link x = (Link)malloc(sizeof(*x));
    x->item = item;
    x->left = left;
    x->right = right;
    x->N = N;
    return x;
}
// ============初始化=================
Link BSTreeInit()
{
    //head是指向树的根节点的哑节点，尾节点 z 表示空树
    head = (z = NewItem(NULLItem, NULL, NULL, 0));
    if(head == NULL)
    {
        printf("内存不足，分配失败\n");
        exit(1);
    }
    return head;
}
// =============插入新项===========
Link InsertR(Item item, Link h)
{
    if(h == z)
    {
        return NewItem(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if(less(v, t))
        h->left = InsertR(item, h->left); //注意要有 h->left= ,容易忘记，想象仅有一个节点时，
                                           //InsertR()仅仅是返回的是新项的链接
    else
        h->right = InsertR(item, h->right);
    (h->N)++;
    return h;
}
void BSTreeInsert(Item item)
{
    head = InsertR(item, head);
}
//===========搜索====================
Item SearchR(Key v, Link h)；
Item BSTreeSearch(Key v)
{
    return SearchR(v, head);
}
Item SearchR(Key v, Link h)
{
    if(h == z)
        return NULLItem;
    Key t = key(h->item);
    if(eq(v, t))
        return h->item;
    else if(less(v, t))
        return SearchR(v, h->left);
    else
        return SearchR(v, h->right);
}

2.2 使用BST排序

只需要中序遍历该二叉树：先访问左节点，然后访问根节点，最后访问右节点。

//=============排序===================
void visit(Link h)
{
    if(h != NULL)
        printf("%c\t", h->item);
}
void BSTreeSort()                                                                     
{
    BSTreeSortR(head);
}
void BSTreeSortR(Link h)
{
    if(h == z)
        return;
    BSTreeSortR(h->left);
    visit(h);
    BSTreeSortR(h->right);
}

2.3 BST上根节点的插入(insert)

将一个新的数据项插入到BST的根，使得最近插入的关键字在树的顶部附近。
新的数据项基本不能满足，既大于原BST的左子树，又小于原BST的右子树，因此我们插入时，仍然先插入到树的底部，通过旋转操作，将其提升到根部。旋转操作涉及2个节点3条链接，旋转不改变树的性质。
这里写图片描述
如上图所示，右旋操作将k2节点向上提升，左旋将k1向上提升。因此当插入到树的叶节点上时，当处于当前根的左侧时，右旋成根；当处于当前根的右侧时，左旋成根。

//=====BST中的旋转============
Link rotR(Link h)
{
    Link x = h->left;
    h->left = x->right;
    x->right = h;
    h->N -= (h->left->N + 1);
    x->N += (h->right->N + 1); 
    return x;
}
Link rotL(Link h)
{
    Link x = h->right;
    h->right = x->left;
    x->left = h;
    h->N -= (h->right->N + 1);
    x->N += (h->left->N + 1); 
    return x;
}

BST上根的插入：

// ===========BST中的根的插入============
Link BSTreeInsertRoot(Item item)
{
    head = InsertRoot(item, head);
}
Link InsertRoot(Item item, Link h)
{
    if(h == z)
        return NewItem(item, z, z, 1);
    Key v = key(item);
    Key t = key(h->item);
    if(less(v, t))
    {
        h->left = InsertRoot(item, h->left);
        h = rotR(h);//在根的左侧，右旋
    }
    else
    {
        h->right = InsertRoot(item, h->right);
        h = rotL(h);//在根的右侧，左旋
    }
    return h;
}

2.4 BST上的选择(select)操作，划分操作

select操作找到关键字第k小的数据项，假设k = 0对应最小的数据项。左子树节点个数为t:若 t == k，则第k小即当前根节点的项；t > k，则第k小在左子树中；t < k，在右子树中的第k-t-1个（多减的1是当前子树的根节点）。

// ========select-选择第k小的数据项，第0小是最小=========
Item BSTreeSelect(int k)
{
    return SelectR(k, head);
}
Item SelectR(int k, Link h)
{
    if(h == z)
        return NULLItem;
    int t = ( (h->left == z) ? 0 : h->left->N );
    if(k < t)
        return SelectR(k, h->left);
    else if(k > t)
        return SelectR(k-t-1, h->right); //-1,减的是根节点
    else
        return h->item;
}

将select改造成划分操作，实现重排树，将第k小的数据项放在根节点。即2.3中的根插入法：递归的把所有所求的节点放到当前子树的根节点，通过一次旋转。

// === 划分操作（根据select，递归后添加旋转）=======
Link partR(Link h, int k)
{
    if(h == z)
        return z;
    int t = (h->left == z)?0:h->left->N;
    if(k < t)
    {
        partR(h->left, k);
        h = rotR(h);
    }
    else if(k > t)
    {
        partR(h->right, k-t-1);
        h = rotL(h);
    }
    return h;
}

2.5 BST上的删除(delete)操作

在BST上删除给定关键字的一个节点，如果删除的节点在根部，需要组合两棵子树，而要组合它们，需要将右子树通过划分操作，将最小的元素当做划分元素，使得右子树中最小的元素旋转到根节点，此时该根的左子树为空：然后将原左子树连接到该根的左节点上（右子树全部大于左子树）。

// ==============删除给定关键字的节点=========
void BSTreeDelete(Key v)
{
    head = deleteR(head, v);
}
Link deleteR(Link h, Key v)
{   
    if(h == z)
        return z;
    Key t = key(h->item);
    if(less(v, t))
        h->left = deleteR(h->left, v);
    else if(less(t, v))
        h->right = deleteR(h->right, v);
    else
    {
        Link tmp = h;
        h = joinR(h->left, h->right);       
        free(tmp);
    }
    return h;
}
//将两棵子树的组合（根节点为右子树的最小项）代替被删除节点
Link joinR(Link leftChild, Link rightChild)
{
    if(rightChild == z)
        return leftChild;
    rightChild = partR(rightChild, 0);//旋转成左子树为空
    rightChild->left = leftChild; //原右子树全部大于左子树
    return rightChild;
}

其他的删除策略：
（1）当被删除节点的左链接为空，直接使右子树成为新的根节点；事实证明该方法和上述程序实现都有缺点：如果对此树进行大量的“删除-插入”操作，最终会倾向得到一棵稍微失去平衡的树。
（2）懒惰的删除策略：将被删除节点留在数据结构中但标记为“已删除”，但必须确保大量带标注的节点不会引起时间或空间的过度浪费：可以将标注删除的点重用于插入；可以周期性重建数据结构，删除带标注点

2.6 两棵BST的连接(join)

怎样将两棵BST连接成一棵BST？
（1）遍历其中一棵，将节点依次插入到另一棵BST上；每次插入线性，全部非线性
（2）将两棵BST的节点全部取出放入数组，构造一棵新的BST；占用额外空间，但时间线性
*（3）将其中一棵BST（t1）的根节点用根插入法插入到另一棵BST(t2)的根节点上:那么留下两棵大于t2根的子树，两棵小于t2根的子树（t1和t2的左右子树）。然后我们递归的连接BST左右子树。因为每个节点至多成为根一次，所以时间线性。以下为程序实现：

//==============BST的join操作===================
Link BSTreeJoin(Link a, Link b)
{
    if(a == z)
        return b;
    if(b == z)
        return a;
    //每个节点至多成为根一次，时间线性
    BSTreeInsertRoot(b, a->item);
    b->left = BSTreeJoin(b->left, a->left);
    b->right = BSTreeJoin(b->right, a->right);
    free(a);
    return b;
}

3. BST的优缺点

基本的BST操作search、insert 和 sort容易实现，且对大小适中的随机操作序列进行的很好，因而BST被广泛用于动态符号表中。
缺点：
（1）存储链接需要空间。常把链接和数据记录看做同样大小，即内存空间，链接占2/3, 关键字占1/3
（2）树的平衡性会变差，性能急剧降低

4.参考资料和所有代码

《算法：C语言实现》P318-342

// 注意递归终止条件和返回值。
#include <stdio.h>
#include <stdlib.h>
#define NULLItem '\0'
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define key(A) (A - 'a')
typedef char Item;
typedef int Key;
typedef struct BSTree* Link;
struct BSTree
 {
    Item item;
    Link left;
    Link right;
    int N; //引入计数，是为了实现select操作
 }; 
 static Link head, z;
//=====新建一个节点=====
Link NewItem(Item item, Link left, Link right, int N)
{
    Link x = (Link)malloc(sizeof(*x));
    x->item = item;
    x->left = left;
    x->right = right;
    x->N = N;
    return x;
}
// ====初始化=======
Link BSTreeInit()
{
    head = (z = NewItem(NULLItem, NULL, NULL, 0));
    if(head == NULL)
    {
        printf("内存不足，分配失败\n");
        exit(1);
    }
    return head;
}
// =============插入新项===========
Link InsertR(Item item, Link h)
{
    if(h == z)
    {
        return NewItem(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if(less(v, t))
        h->left = InsertR(item, h->left);
    else
        h->right = InsertR(item, h->right);
    (h->N)++;
    return h;
}
void BSTreeInsert(Item item)
{
    head = InsertR(item, head);
}
//===========搜索====================
Item SearchR(Key v, Link h)
{
    if(h == z)
        return NULLItem;
    Key t = key(h->item);
    if(eq(v, t))
        return h->item;
    else if(less(v, t))
        return SearchR(v, h->left);
    else
        return SearchR(v, h->right);
}
Item BSTreeSearch(Key v)
{
    return SearchR(v, head);
}
//=============排序===================
void visit(Link h)
{
    if(h != NULL)
        printf("%c\t", h->item);
}
void BSTreeSortR(Link h)
{
    if(h == z)
        return;
    BSTreeSortR(h->left);
    visit(h);
    BSTreeSortR(h->right);
}
void BSTreeSort()                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
{
    BSTreeSortR(head);
}
//=====BST中的旋转============
Link rotR(Link h)
{
    Link x = h->left;
    h->left = x->right;
    x->right = h;
    h->N -= (h->left->N + 1);
    x->N += (h->right->N + 1); 
    return x;
}
Link rotL(Link h)
{
    Link x = h->right;
    h->right = x->left;
    x->left = h;
    h->N -= (h->right->N + 1);
    x->N += (h->left->N + 1); 
    return x;
}
// ===========BST中的根的插入============
Link InsertRoot(Item item, Link h)
{
    if(h == z)
        return NewItem(item, z, z, 1);
    Key v = key(item);
    Key t = key(h->item);
    if(less(v, t))
    {
        h->left = InsertRoot(item, h->left);
        h = rotR(h);
    }
    else
    {
        h->right = InsertRoot(item, h->right);
        h = rotL(h);
    }
    return h;
}
Link BSTreeInsertRoot(Item item)
{
    head = InsertRoot(item, head);
}
// ========select-选择第k小的数据项，第0小是最小=========
Item SelectR(int k, Link h)
{
    if(h == z)
        return NULLItem;
    int t = ( (h->left == z) ? 0 : h->left->N );
    if(k < t)
        return SelectR(k, h->left);
    else if(k > t)
        return SelectR(k-t-1, h->right); //-1,减的是根节点
    else
        return h->item;
}
Item BSTreeSelect(int k)
{
    return SelectR(k, head);
}
// === 划分操作（select）=======
Link partR(Link h, int k)
{
    if(h == z)
        return z;
    int t = (h->left == z)?0:h->left->N;
    if(k < t)
    {
        partR(h->left, k);
        h = rotR(h);
    }
    else if(k > t)
    {
        partR(h->right, k-t-1);
        h = rotL(h);
    }
    return h;
}
// ==============删除给定关键字的节点=========
Link joinR(Link leftChild, Link rightChild)
{
    if(rightChild == z)
        return leftChild;
    rightChild = partR(rightChild, 0);//旋转成左子树为空
    rightChild->left = leftChild; //原右子树全部大于左子树
    return rightChild;
}
Link deleteR(Link h, Key v)
{   
    if(h == z)
        return z;
    Key t = key(h->item);
    if(less(v, t))
        h->left = deleteR(h->left, v);
    else if(less(t, v))
        h->right = deleteR(h->right, v);
    else
    {
        Link tmp = h;
        h = joinR(h->left, h->right);       
        free(tmp);
    }
    return h;
}
void BSTreeDelete(Key v)
{
    head = deleteR(head, v);
}
//==============BST的join操作===================
Link BSTreeJoin(Link a, Link b)
{
    if(a == z)
        return b;
    if(b == z)
        return a;
    //每个节点至多成为根一次，时间线性
//  BSTreeInsertRoot(b, a->item);
    b->left = BSTreeJoin(b->left, a->left);
    b->right = BSTreeJoin(b->right, a->right);
    free(a);
    return b;
} 
//============= 驱动函数 =============
int main()
{
    BSTreeInit();
    for(int i = 0; i < 20; i++)
    {
        char c = 'a' + (rand()%26);
        Key v = key(c);
        printf("%c, %d\n", c, v);
        BSTreeInsert(c);
    }
    printf("Root = %c\n", head->item);
    BSTreeInsertRoot('z');
    BSTreeInsertRoot('b');
    BSTreeInsert('b');
    printf("Root = %c\n", head->item);
    int k = 4;
    printf("第%d小的项是%c\n", k, BSTreeSelect(k));
    printf("\n");
    printf("\n搜索：\n");
    printf("%c\n", BSTreeSearch(4));
    printf("%c\n", BSTreeSearch(-1));
    printf("%c\n", BSTreeSearch(0));
    printf("%c\n", BSTreeSearch(100));
    printf("\n排序：\n");
    BSTreeSort();
    Key v = 3;
    printf("\n删除关键字为%d的节点:%c\n", v, BSTreeSearch(v));
    BSTreeDelete(v);
    printf("\n排序：\n");
    BSTreeSort();
}