既要使插入、删除的效率高也要使查找的效率高,即实现高效率的动态查找表——引入二叉排序树
二叉排序树
- 定义:若左子树不为空,则左子树节点值均小于根节点值;若右子树不为空,则节点值均大于根节点值;左右子树均为二叉排序树。
QQ截图20140808163818.jpg - 二叉排序树的节点可以定义为如下形式
struct BNode
{
int data;
BNode *lhs,*rhs;
};
- 查找操作 可以采用递归的形式,其中T为指向根节点的指针,key为所寻找的值,p为找到后指向节点的指针,pT一直保持指向所要开始找的节点的父节点,若最终没有找到,则p=pT,表明最后搜索的位置,便于后续的插入操作。
//二叉排序树搜索
bool searchBST(BNode *T,int key, BNode *pT,BNode *p)
{
if(!T)
{
p = pT;
return false;
}
else if(key == T->data)
{
p = T;
return true;
}
else if(key<T->data)
return(T->lhs,key,T,p);
else if(key>T->data)
return(T->rhs,key,T,p);
}
- 插入操作 可以通过调用查找操作进行简化,插入总是插入称为叶子节点,利用指针操作,具有较高的效率
//插入
bool insertBST(BNode *T,int key)
{
BNode *p;
if(!searchBST(T,key,NULL,p))
{
BNode * s = new BNode();
s->data = key;
s->lhs = NULL;
s->rhs = NULL;
if(!p) //表明为根节点
p = s;
if(key>p->data)
p->rhs = s;
else
p->lhs = s;
return true;
}
else
return false;
}
- 创建二叉树 利用插入操作可以创建一颗二叉排序树
//建立一个二叉树
#include <ctime>
void createBTree(BNode * head)
{
srand(time(NULL));
int num = 10;
while (num--)
insertBST(head,rand()%100);
}
- 删除节点 相对复杂,需要考虑三种情况
1、删除节点为叶子节点,直接删除即可
2、删除节点只包含左子树或者只包含右子树,这时候将其子树续接后删除该节点即可
3、删除节点包含左、右子树,考虑用里该节点最近的节点进行替换,替换后删除替换的那个节点即可
- 其中最近的节点指中序遍历中其前后节点,获取方法有(1)从删除节点开始,先左拐,然后一直右拐;(2)从删除节点开始,先右拐,然后一直左拐;替换后需要删除的节点情形一定是1或者2,按照上述方法删除即可。详细代码如下
//删除二叉排序树的节点,采用递归的思想,和采用查找的时候一样
//分为叶子节点——直接删除即可
//删除节点只有左子树或者右子树——删除后把其子树替代原先的节点位置
//删除节点有两个子树
bool deleteNode(BNode *T)
{
if(T->lhs == NULL && T->rhs == NULL) //叶子节点
{
delete(T);
}else if(T->lhs == NULL) //只有右子树
{
BNode *q = T;
T->data = T->rhs->data;
T->lhs = T->rhs->lhs;
T->rhs = T->rhs->rhs;
delete(T->rhs);
}else if(T->rhs == NULL) //只有左子树
{
BNode *q = T;
T->data = T->rhs->data;
T->rhs = T->lhs->rhs;
T->lhs = T->lhs->lhs;
delete(T->lhs);
}else //有左右子树
{
BNode *q = T->lhs;
BNode *p = T;
while(q->rhs)
{
p = q;
q = q->rhs;
}
T->data = q->data;
if(q==p->lhs)
T->lhs = q->lhs;
else
p->rhs = q->lhs;
delete(q);
}
return true;
}
bool deleteBST(BNode *T,int key)
{
if(T == NULL)
return false;
if(T->data<key)
deleteBST(T->rhs,key);
else if(T->data>key)
deleteBST(T->lhs,key);
else
return deleteNode(T);
}
小结
- 以链式存储的二叉排序树,对于插入删除具有较高的效率
- 同时由于左右子树的树形结构,对于查找也是相当的便利,最大查找次数=树的深度\层数,如果二叉排序树完全平衡,则其深度为(向下取整)[logn]+1,那么其查找的复杂度为O(logn)。
reference
- 大话数据结构
网友评论