插入和删除对于顺序存储结构效率可以接受，但是这样的表由于无序造成的查找效率低。
如果查找的数据集是有序线性表，并且是顺序存储，查找可以用折半、插值、斐波那契等算法，但插入和删除操作上需要耗费大量的时间。
所以用到了二叉排序树，插入效率不错，且可以高效率实现查找。
二叉排序树（Binary Sort Tree）:又称为二叉查找树，或者是一棵空树，或者是具有下列性质的二叉树。
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值
（2）若它的右子树不空，则右子树上所有结点的值均大于等于它的根结点的值
（3）它的左、右子树也分别为二叉排序树
构造二叉排序树是为了提高查找和插入删除关键字的速度。
例如对于集合{62,88,58,47,35,73,51,99,37,93 }，其构成的二叉排序树如下（分清楚不同类型的结点对后续删除有用）：
二叉排序树
1.二叉排序树的插入即按照其特性进行插入即可，按照中序遍历后为递增序列
2.二叉排序树删除操作：二叉排序树删除某个结点后还需满足二叉排序树的特性，所以需要考虑多种情况。
（1）如果需要查找并删除蓝色的叶子结点，则直接删除即可，不影响二叉排序树整体结构。
（2）如果要删除的是橙色的只有右子树或者左子树，将其子树移动到删除结点的位置即可。
（3）如果要删除的结点既有左子树又有右子树，找到要删除结点p的直接前驱（左子树中最大的结点，不会有右子树）或者后继s（右子树中最小的结点，不会有左子树）来替换，然后再删除结点s。
代码示例：
BST.h
#pragma once
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef struct BiTNode
{
int data;
BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
//二叉排序树插入
void InsertBST(BiTree& T, int a);
//二叉排序树创建
void CreateBST(BiTree& T, int* a, int n);
//中序遍历
void InOrderTraverse(BiTree T);
//二叉排序树的查找
BiTNode* SearchBST(BiTree T, int key);
//二叉排序树删除
bool DeleteBST(BiTree& T, int key);
//从二叉排序树删除结点p，并重接它的左或者右子树
bool Delete(BiTree& p);
BST.cpp
#include "BST.h"
#include <iostream>
using namespace std;
//创建二叉排序树(添加结点，一定在叶子结点上)
void InsertBST(BiTree& T, int a)
{
if (T == NULL)
{
T = new BiTNode; //创建结点
T->data = a;
T->lchild = NULL;
T->rchild = NULL;
}
else
{
if (a > T->data)
{
InsertBST(T->rchild, a); //放在右子树
}
else
{
InsertBST(T->lchild, a); //放在左子树
}
}
}
//二叉排序树创建
void CreateBST(BiTree& T, int* a, int n)
{
for (int i = 0; i < n; i++)
{
InsertBST(T, a[i]);
}
}
//中序遍历
void InOrderTraverse(BiTree T)
{
if (T == NULL)
{
return;
}
else
{
InOrderTraverse(T->lchild);
cout << T->data << " ";
InOrderTraverse(T->rchild);
}
}
//二叉排序树的查找
BiTNode* SearchBST(BiTree T, int key)
{
if (T == NULL)
{
return NULL;
}
if (key == T->data)
{
return T;
}
else if (key > T->data)
{
return SearchBST(T->rchild, key); //在右子树中查找
}
else
{
return SearchBST(T->lchild, key); //在左子树中查找
}
}
//二叉排序树删除
bool DeleteBST(BiTree& T, int key)
{
if (T == NULL)
{
return false;
}
if (key == T->data)
{
return Delete(T); //对当前结点执行删除操作
}
else if (key > T->data)
{
return DeleteBST(T->rchild, key);
}
else
{
return DeleteBST(T->lchild, key);
}
}
//从二叉排序树删除结点p，并重接它的左或者右子树
bool Delete(BiTree& p)
{
BiTNode* q, * s;
if (p->lchild == NULL) //左子树为空或者两个子树都为空(重接它的右子树)
{
q = p;
p = p->rchild;
delete q;
}
else if (p->rchild == NULL) //右子树为空（重接它的左子树）
{
q = p;
p = p->lchild;
delete q;
}
else //左右子树都不为空
{
q = p;
s = p->lchild;
while (s->rchild)
{
q = s; //q为s的父结点
s = s->rchild; //找到要删除结点p的前驱结点（即左子树中最大的结点，该结点没有右子树）
}
p->data = s->data; //
//删除s结点，让其左子树连接到二叉排序树中
if (q != p) //s结点有右子树的情况
{
q->rchild = s->lchild; //
}
else //s结点没有右子树的情况,s为p的左子树，q=p
{
q->lchild = s->lchild;
}
delete s; //删除前驱结点
}
return true;
}
main.cpp
#include "BST.h"
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
BiTree T = NULL;
int a[10] = { 62,88,58,47,35,73,51,99,37,93 };
CreateBST(T, a, 10);
InOrderTraverse(T); //中序遍历二叉排序树
cout << endl;
BiTNode* node = SearchBST(T, 35);
if (node)
{
cout << "node->data=" << node->data << endl;
}
/*DeleteBST(T, 47); //删除既有左子树又有右子树的结点
InOrderTraverse(T);
cout << endl;*/
DeleteBST(T, 93); //删除叶子结点
InOrderTraverse(T);
cout << endl;
return 0;
}
二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入删除操作时不用移动元素的优点。
对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况下，最少为1次，最多不会超出树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状，但是其形状是不确定的。
对于集合{35,37,47,51,58,62,73,88,93,99 }，元素按照从小到大排序，其构成的二叉排序树如下，成了极端的右斜树，查找复杂度变为O(n),等同于顺序查找。
因此，如果我们希望一个集合按照二叉排序树查找，最好是把它构建成一棵平衡二叉排序树，其深度与完全二叉树相同。那么如何让二叉排序树平衡呢？
极端情况下的二叉排序树
网友评论