二叉搜索树

插入和删除对于顺序存储结构效率可以接受，但是这样的表由于无序造成的查找效率低。
如果查找的数据集是有序线性表，并且是顺序存储，查找可以用折半、插值、斐波那契等算法，但插入和删除操作上需要耗费大量的时间。
所以用到了二叉排序树，插入效率不错，且可以高效率实现查找。
二叉排序树（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),等同于顺序查找。
因此，如果我们希望一个集合按照二叉排序树查找，最好是把它构建成一棵平衡二叉排序树，其深度与完全二叉树相同。那么如何让二叉排序树平衡呢？

极端情况下的二叉排序树