算法学习笔记----二叉搜索树

一、算法描述

顾名思义，一颗二叉搜索树是以一颗二叉树来组织数据的。这样一棵树可以使用一个链表数据结构来表示，每一个节点都是一个对象。除了key和卫星数据之外，每个节点还包含属性left、right和p，它们分别指向节点的左孩子、右孩子和双亲。二叉搜索树不是一颗普通的二叉树，是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有节点都不大于它的根节点的值

2. 若它的右子树不空，则右子树上所有节点都不小于它的根节点的值

3. 它的左、右子树也分别为二叉搜索树

二叉搜索树上的基本操作（SEARCH、INSERT等）所花费的时间与这颗树的高度成正比。对于有n个节点的一颗完全二叉搜索树来说，这些操作的最坏运行时间为Θ(lgn)。如果这棵树是一条n个节点组陈过的线性链，那么同样的操作就要花费Θ(n)的最坏运行时间。

二叉搜索树的性质允许我们通过树的中序遍历算法按序输出二叉搜索树中的所有关键字。我们将中序遍历的过程定义为INORDER-TREE-WALK，如果x是一颗有n个结点子树的根，那么执行INORDER-TREE-WALK(x)所属的时间为Θ(n)。证明如下（选自《算法导论》）：

如果是一颗空树，INORDER-TREE-WALK需要耗费一个小的常熟时间（测试x≠NIL），因此对某个常熟c>0，有T(0)=c。

对n>0，假设调用INORDER-TREE-WALK作用在一个节点x上，x节点左子树有k个节点，则x节点右子树的节点数为n-k-1，则执行INORDER-TREE-WALK的时间有T(n)=T(k)+T(n-k+1)+d限界，其中常熟d>0.此式反映了执行INORDER-TREE-WALK(x)的一个时间上界，其中不包括递归调用所花的时间。

使用替换法，通过证明T(n)≤(c+d)n+c，可以证明T(n)=O(n)。对于n=0，有T(0)=c。对于n>0，有

T(n)≤T(k)+T(n-k+1)+d=((c+d)k+c)+((c+d)(n-k-1)+c)+d

=(c+d)n+c-(c+d)+c+d=(c+d)n+c

到此，完成了定理的证明。

二、基本操作

在介绍各个操作之前，先说明代码中用到的两个结构struct bst和struct bst_node，其中bst结构表示二叉搜索树，bst_node表示二叉搜索树的节点，定义如下：

static void bst_transplant(struct bst *t, struct bst_node *old, struct bst_node *new){    if (!old) {        return;    }        if (!old->parent) {        t->root = new;    } else if (old == old->parent->left) {        old->parent->left = new;    } else {        old->parent->right = new;    }        if (new) {        new->parent = old->parent;    }}static void bst_delete(struct bst *t, struct bst_node *z){    struct bst_node *y;        if (z->left == NULL) {        bst_transplant(t, z, z->right);        return;    } else if (z->right == NULL) {        bst_transplant(t, z, z->left);        return;    }        y = bst_minimum(z->right);    if (y->parent != z) {        bst_transplant(t, y, y->right);        y->right = z->right;        y->right->parent = y;    }        bst_transplant(t, z, y);    y->left = z->left;    y->left->parent = y;}
其中bst_transplant()是用来实现用另一颗子树替换一颗子树并成为其双亲的孩子节点。
同样，在一颗高度为h的树上，TREE-DELETE的运行时间为O(h)。