问题：
有序的线性表采用：折半/二分、插值、斐波那契查找相比顺序查找效率得到提高，但是在插入和删除时效率低（为维持数据的有序性）
在高效实现查找操作时，如何提高插入和删除的效率？
在一些应用场景：在查找时需要插入和删除
解决方法：
二叉排序树
二叉排序树特点
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大于根结点数据则插入为右孩子
C伪代码：
//定义结点结构 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
后续：如何解决二叉排序树多次插入新结点而导致的不平衡？
