问题：
有序的线性表采用：折半/二分、插值、斐波那契查找相比顺序查找效率得到提高，但是在插入和删除时效率低（为维持数据的有序性）
在高效实现查找操作时，如何提高插入和删除的效率？
在一些应用场景：在查找时需要插入和删除
解决方法：
二叉排序树
二叉排序树特点
1）若左子树不为空，左子树上所有结点的值均小于或等于它的根节点的值
2）若右子树不为空，右子树上所有结点的值均大于或等于它的根节点的值
3）左右子树也分别为二叉排序树
二叉排序算法的复杂度：
时间复杂度：二分查找的思想，查找次数为二叉查找树的高度，若树为平衡二叉树则为O(logn),否则最坏的情况为右斜树O(n)
二叉排序算法的缺点是：
二叉树的构建类型多种，不同的二叉树形状会导致查找的性能差异很大，例如普通的二叉树和一棵右斜树。
二叉排序树的查找：
1）查找数据key，判断key是否等于树的根节点数据
2）若待查数据key小于根结点数据则递归的在左子树查找
3）若待查数据key大于根结点数据则递归的在右子树查找
C伪代码：
//定义结点结构
typedef struct BiTNode
{
int data; //结点数据
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree
/递归查找二叉排序树T中是否存在key
//f指向T的双亲
//p获得查找到的结点位置
Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
{
//查找不成功
if(!T)//判断当前二叉树是否到叶子结点
{
*p=f;//指针p指向查找路径*问的最后一个结点并返回false
return False;
}
//查找成功
else if(key==T->data)
{
*p=T;
return True;
}
else if(key<T->data)//待查找元素小于结点数据
return SearchBST(T->lchild，key，T，p);//在左子树继续查找
else
return SearchBST(T->rchild，key，T，p);//在右子树继续查找
}
二叉排序树的插入操作：
1）在二叉排序树找不到待插入的数据key则执行2）步骤
2）待插数据初始化为结点s，若树为空则直接赋值结点s给树
3）待插入数据key小于根结点数据则插入为左孩子
4) 待插入数据key大于根结点数据则插入为右孩子
//定义结点结构
typedef struct BiTNode
{
int data; //结点数据
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree
//二叉树的数据插入
Status InsertBST(BiTree *T,int key)
{
BiTree p,s;//创建二叉树结点
//在二叉排序树中找不到key
if(!SearchBST(*T,key,NULL,&p))
{
//s结点的初始化
s=(BiTree)malloc(sizeof(BiTNode));
s->data=key;
s->lchild=s->rchild=NULL;
//若p结点为空
if(!p)
*T=s;
else if (key<p->data)//待插入的值key小于p结点指向的数据
p->lchild=s;//s插入为左孩子
else//待插入的值key大于p结点指向的数据
p->rchild=s;//s插入为右孩子
return True;
}
//树中已有关键字相同的结点，不再插入
else
return False;
}
构建一棵二叉排序树示例：
//生成一棵二叉树
int i;
int a[10]={62,88,58,47,35,73,51,99,37,93};
Bitree T=NULL;
for(i=0;i<10;i++）
{
InsertBST(&T,a[i]);
}
二叉排序树的删除操作：
删除结点的三种情况：
1）删除叶子结点
2）删除的结点只有左或右子树的
3）删除的结点有左右子树
//定义结点结构
typedef struct BiTNode
{
int data; //结点数据
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree
//删除元素等于key的数据结点
Status DeleteBST(BiTree *T,int key)
{
//不存在关键字等于key的数据元素
if(!*T)
return False;
else
{
if(key==(*T)->data) //找到关键字等于key的数据元素
return Delete(T);
else if(key<(*T)->data)//待删除的元素key小于查找到的元素---则在结点的左子树搜索
return DeleteBST(&(*T)->lchild,key);
else //待删除的元素key大于查找到的元素---则在结点的右子树搜索
return DeleteBST(&(*T)->rchild,key);
}
}
Status Delete(BiTree *p)
{
BiTree q,s;
//第一种情况，删除结点只有左子树或右子树
if((*p)->rchild==NULL)//只有左子树
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if((*p)->lchild==NULL)//只有右子树
{
q=*p;
*p=(*p)->rchild;
free(q);
}
//第二种情况：删除的结点有左子树和右子树
else
{
q=*p;//待删除的结点给临时变量q
s=(*p)->lchild;//待删除结点指向的左子树给临时变量s
while(s->rchild)//左子树s一直向右找，直到找到待删结点的前驱
{
q=s;
s=s->rchild;
}
(*p)->data=s->data;//s指向被删结点的直接前驱，将它的值直接赋值给要删除的结点*p
if(q!=*p)//被删结点的直接前驱p!=被删结点的直接前驱的根结点q
q->rchild=s->lchild;//根结点q的右孩子指针指向被删结点的直接前驱的左孩子
else
q->lchild=s->lchild;
free(s);
}
}
上述代码需注意：
1）q!=*p的情况：
2） q=*p的情况：
若上图的结构修改为：
没有结点37和36，s指向35。
p和q的指向相同都是47结点处，则将s->lchild指向的29赋值给q->lchild
后续：如何解决二叉排序树多次插入新结点而导致的不平衡？