二叉排序树

二叉排序树(BST)

定义

  二叉排序树又称二叉查找树。二叉排序树或是一棵空树，或是一棵具有下列特性的非空二叉树：

  1）若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值。

  2）若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值。

  3）左、右子树本身也分别是一棵二叉排序树

  左子树结点值 < 根结点值 < 右子树结点值，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

查找

  二叉排序树的查找是从根结点开始，沿某个分支逐层向下进行比较的过程。若二叉树非空，则将给定值与根结点的关键字比较；若相等，则查找成功；若不等，则当前结点的关键字值大于给定关键字值时，在根节点的左子树查找，否则在根节点的右子树中查找。这是一个递归的过程。

  二叉排序树的递归查找算法：

BSTNode* BST_Search(BitTree T, ElemType key){
    if(T == NULL){
        return NULL;
    }
    if( T->data == key){
        return T;
    }else if( T->data > key){
        return BST_Search(T->lchild, key);
    }else if( T->data < key){
        return BST_Search(T->rchild, key);
    }
}

  二叉排序树的非递归查找算法：

BSTNode* BST_Search(BitTree T, ElemType key, BSTNode* &p){
    p = NULL;
    while( T != NULL && key != T->data ){
        p = T;
        if( key < T->data ){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}

插入

  二叉排序树是一种动态几何，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时在进行插入的。

  由于二叉排序树是递归定义的，因此插入结点的过程如下：若二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点关键字，则插入左子树，若关键字大于根结点关键字，则插入右子树。

bool BST_Insert(BitTree& T, ElemType k){
    if( T == NULL){
        T = (BitTree*)malloc(sizeof(BitTree));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return true;
    }else if( T->data == k){    //树中存在相同关键字的结点
        return false;        
    }else if( k < T->key ){
        return BST_Insert(T->lchild, k);
    }else if( k > T->data ){
        return BST_Insert(T->rchild, k);
    }
    return true;
}

二叉排序树的构造

  构造一棵二叉树就是依次输入数据元素，并将它们插入二叉排序树中适当位置上的过程。具体过程：每读入一个元素，就建立一个结点，若二叉排序树非空，则将新结点的值与根结点的值作比较，若小于根结点的值，则插入左子树，否则插入右子树；若二叉排序树为空，则将新结点作为二叉排序树的根结点。

void BST_Create(BitTree& T, ElemType str[]){
    int sz = sizeof(str)/sizeof(str[0]);
    T = NULL;
    int i = 0;
    while( i < sz ){
        Create_BST(T,str[i]);
        i++;
    }
}

删除（难点）

  在二叉排序树中删除一个结点时，不能把以结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。

  删除操作按三种情况来处理：

1. 若被删除结点 x 是叶结点，则直接删除，不会破坏二叉排序树的性质

2. 若结点 x 只有一棵左子树或右子树，则让 x 的子树成为 x 父节点 的子树，替代 x 的位置

3. 若结点 x 有左、右两棵子树，则令 x 的直接后继（或直接前驱）替代 x ，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

//中序遍历序列的下一个节点，即比当前节点大的最小节点，简称后继节点。
int successor(BSTTree* p){
    p = p->rchild;
    while(p->lchild != NULL){
        p = p->left;
    }
    return p->data;
}
//中序遍历序列的前一个节点，即比当前节点小的最大节点，简称前驱节点。 
int predecessor(BSTTree* p){
    p = p->lchild;
    while(p->rchild != NULL){
        p = p->rchild;
    } 
    return p->data;
}

BSTNode* BST_Delete(BSTTree& T, ElemType x){
    if( T == NULL){
        return NULL;
    }else{
        if( x < T->data ){    //要删除的在左边
            T->lchild = BST_Delete(T->lchild, x);
        }else if( x > T->data ){    //要删除的在右边
            T->rchild = BST_Delete(T->rchild, x);
        }else{
            if( T->lchild == NULL && T->rchild == NULL){//叶子结点
                T = NULL;
            }else if( T->rchild != NULL){
            //如果该节点不是叶子节点且有右节点，则用它的后继结点的值替代，然后删除后继结点               
                T->data = successor(T);
                T->rchild = BST_Delete(T->rchild, T->data);
            }else {
            //如果该节点不是叶子节点且只有左节点，则用它的前驱节点的值替代，然后删除前驱节点               
                T->data = predecessor(T);
                T->lchild = BST_Delete(T->lchild, T->data);                
            }
        }
    }
    return T;
}

二叉排序树的查找效率

  对于高度为h的二叉排序树，插入和删除操作的运行时间都是O(h)。但在最坏情况下，构造二叉排序树的输入序列是有序的，则会形成一个倾斜的单支树，此时二叉排序树的性能新竹变坏，树的高度也增加为元素个数n。

  二叉排序树的查找算法平均查找长度，主要取决于树的高度，即与二叉树的形态有关。若退化成链表，则为O（n）;若为平衡二叉树，则为O（log2n)。

  相同的关键字其插入顺序不同可能生成不同的二叉排序树。