二叉排序树

动态查找表

    动态查找表除了支持查找操作，还支持插入、删除等改变表中数据的操作。

    动态查找表的表结构是在查找过程中动态生成的，即对于给定的key值，若表中存在其关键字等于key的记录，则查找成功；否则插入关键字等于key的记录。

    为了方便插入和删除操作，通常采用链表、树等存储结构来表示动态查找表。

1.1 二叉排序树（binary sort tree，BST）是一棵空树，或满足如下性质的二叉树：

(1) 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；

(2) 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；

(3) 左右子树本身也分别是一棵二叉树。

由二叉树的性质可得知：

(1) 二叉排序树中任一结点x，其左子树中任一结点y的关键字必小于x的关键字，右子树亦然；

(2) 二叉排序树中，各结点关键字是唯一的；

(3) 按中序遍历该树得到的中序序列是一个递增有序序列。

二叉排序树的运算包括插入、删除、生成和查找等，因此常用二叉链表作为二叉排序树的存储结构，定义如下：

 

typedef int keytype;
typedef struct node{
    keytype key;
    struct node *lchild,*rchild;//左右子树指针
}BSTNode;

typedef BSTNode *BSTree;//定义二叉排序树类型的指针

a) 二叉排序树的插入

在二叉排序树中插入新结点，要保证插入后仍满足BST的性质，过程如下：

(1) 若二叉排序树T为空，则为待插入的关键字key申请一个新结点，并令其为根；

(2) 若二叉排序树T不为空，则将key和根的关键字比较；

(3) 若两者相等，则说明树中已有此关键字key，无需插入；

(4) 若key<T->key，则将key插入到根的左子树；

(5) 若key>T->key，则将key插入到根的右子树。

算法描述如下：

 

void insertBST(BSTree *bst,keytype key){
    //若二叉排序树*bst中没有关键字为key，则插入
    BSTNode *p = *bst;
    while(p){
        if(p->key == key) return;//已存在，不需要插入
        p = (key < p->key) ? p->lchild:p->rchild;
        //在左右子树中查找
    }
    
    BSTNode *f = (BSTNode *)malloc(sizeof(BSTNode));//新分配一个结点空间
    //生成新结点f
    f->key = key;
    f->lchild = f->rchild = NULL;
    if(*bst == NULL) *bst = f;//原树为空
    else
        if(key<p->key) p->lchild = f;
        else p->rchild = f;
}//insertBST

b) 二叉排序树的生成

BSTree createBST(){
    //输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
    BSTree T = NULL;
    keytype key;
    scanf("%d",&key);
    while(key != '0'){
        insertBST(&T,key);
        scanf("%d",&key);//读入下一个关键字
    }
    return T;
}

c) 二叉排序树的删除

在二叉排序树中删除一个结点时，必须将因删除而断开的二叉链表重新连接起来，同时保持二叉排序树的性质不变。

假设二叉排序树上被删除结点为*p，其父节点为*parent，可设p是parent的左指针。

可分下面3中情况讨论：

(1) 若*p结点为叶子结点，只需要将*parent中指向*p的指针域置为NULL即可；

(2) 若*p结点只有左子树或右子树，只需要将*p的左或右子树直接连接到*parent即可。

(3) 若*p结点的左右子树均不空，中序遍历该树，得到*p的直接后继是*s，*s结点是*p结点的右子树的最左下的结点，且*s结点无左子树，降被删除的结点*p用*s代替，同时将*s结点的右子树作为*s结点的父结点的左子树。

程序描述如下：

void delBSTNode(BSTree *bst,keytype key){
	if(!bst) return;//如果二叉排序树为空，则直接返回
	BSTNode *parent = NULL,*p = *bst,*child,*s;
	while(p){//从根开始查找关键字为key的待删结点
		if(p->key == key) break;//找到，跳出循环
		parent = p;//父结点为*p的双亲
		p = (key < p->key) ? p->lchild : p->rchild;
	}
	if(!p) return; //找不到待删记录，返回
	if(!parent){//只有一个根节点，删除之后就什么都没了
		bst = NULL;
	}
	//处理情况1,*p为叶子结点，修改*p的父结点*parent指向*p的指针域为空即可
	if(!p->lchild && !p->rchild){
		child = parent->lchild ? parent - >lchild : parent ->rchild;
		child = NULL;
	}
	//处理情况2，*p只有左子树或右子树，只需要将左子树或右子树与parent直接关联即可
	if(!p->lchild || !p->rchild){
		child = parent->lchild ? parent - >lchild : parent ->rchild;
		child = p->lchild ? p->lchild : p->rchild; 
	}
	//处理情况3，*p有左右子树，需要找到*p右子树的最左下结点*s，p被s代替，且s的右子树为s父结点的左子树
	if(p->lchild && p-> rchild){
		parent = p;
		s = p->rchild;
		while(!s->lchild){
			parent = s;
			s = s->lchild;
		}
		p->key = s->key;//替换数据，这样就不用替换其他关系了
		parent->lchild = s->rchild;//s的右子树为s父结点的左子树
		p = s;
	}
	free(p);
}

d) 二叉排序树的查找

过程如下：

(1) 从根结点开始，沿某一个分支逐层向下比较判断，相等，则成功返回。

(2) 若查找值小于根节点的值，从根节点的左子树查找，否则，从右子树查找。

(3) 若查找到最后，左子树或右子树为空，则查询失败。

算法描述如下：

BSTNode *searchBST(BSTree *bst,keytype key){
    if(bst == NULL || bst->key == key){//递归查询终止条件
        return bst;//bst为空，则查找失败，成功则返回结点位置
    }
    return key < bst->key?searchBST(T->lchild,key) : searchBST(T->rchild,key)
}

e) 二叉排序树的查找分析

二叉排序树查找时，与关键字比较的次数不超过树的深度。

查找时的平均查找长度与二叉排序树的形态有关。

    最坏的情况为n个关键字已基本有序，得到一个深度为n的单枝树，此时平均查找长度为(n+1)/2。

    最好的情况，二叉排序树左右形态比较平衡，其平均查找长度为[log(2)n]+1