二叉排序树（BST） – Qiuqiの小窝

定义

二叉排序树（Binary Search Tree，BST），又称二叉搜索树，是一种特殊的二叉树数据结构，要么为空树，要么为具有下面特性的二叉树

对于树中的任意节点：

若左子树非空，左子树中所有节点的值都小于该节点的值
若右子树非空，右子树中所有节点的值都大于该节点的值
左右子树也都是二叉排序树

根据二叉排序树的定义，左子树节点值<根节点值<右子树节点值，因此对二叉排序树进行中序遍历，将得到一个递增有序序列，如下图，进行中序遍历将得到序列：8,10,11,12,13,15,16,17,18,19,22,25

定义一个二叉排序树结构：

typedef int DataType;
typedef struct BST_Node {
    DataType data;
    struct BST_Node *lchild, *rchild;
}BST_T, *BST_P;

二叉排序树的构造

代码实现：

void CreateBST(BST_P *T, int a[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        Insert_BST(T, a[i]);
    }
}

二叉排序树的查找

二叉排序树的查找从根节点开始，利用BST的有序性质，进行递归查找：

如果目标值等于当前节点值，找到目标
如果目标值小于当前节点值，在左子树查找
如果目标值大于当前节点值，在右子树查找

时间复杂度：平均O(log₂n)，最坏情况查找的值在最右下方，复杂度为O(n)

递归实现：

BST_P Search_BST(BST_P root, DataType key)
{
    if (root == NULL)
        return NULL;
    if (key > root->data) //查找右子树  
        return Search_BST(root->rchild, key);
    else if (key < root->data) //查找左子树  
        return Search_BST(root->lchild, key);
    else
        return root;
}

非递归：

BST_P Search_BST(BST_P root, DataType key)
{
    while (root != NULL && root->data != key) 若树空或等于根节点值，退出循环
    {       
       if(key < T->data)  T = T->lchild; //小于，查找左子树
       else T = T->rchild; //大于，查找右子树
    }
    return NULL;
}

二叉排序树的插入

插入新节点时，从根节点开始比较：

若当前节点为空，直接插入
如果新值小于当前节点值，向左子树递归
如果新值大于当前节点值，向右子树递归
找到空位置后插入新节点

时间复杂度：平均O(log₂n)，最坏O(n)

代码实现：

int BST_Insert(BST_P T, DataType key){
    if(T == NULL){      // 原树为空，插入的值为空节点
        T = (BST_P)malloc(sizeof(BST_Node));
        T->data = key;
        T->lchild = T->rchild = NULL;
        return 1;     // 返回，插入成功
    }
    else if(key == T->data)
        return 0;   // 当前节点的值与要插入的值相同，插入失败
    else if(key < T->data)  // 插入左子树
        return BST_Insert(T->lchild, key);
    else  // 插入右子树
        return BST_Insert(T->rchild, key);
}

二叉排序树的删除

删除是最复杂的操作，需要考虑三种情况：

情况1：删除叶子节点 直接删除，将父节点对应的指针设为空。
情况2：删除只有一个子节点的节点 用该节点的子节点替换该节点。
情况3：删除有两个子节点的节点 找到该节点的中序后继（右子树中的最小值）或中序前驱（左子树中的最大值），用后继/前驱的值替换要删除节点的值，然后删除后继/前驱节点。

代码实现（考的概率很小）:

void DeleteBSTNode(BST_P *root, DataType data)
{
    BST_P p = *root, parent = NULL, s = NULL;

    if (!p) return;

    if (p->data == data) //找到要删除的节点了
    {
        /* It's a leaf node */
        if (!p->rchild && !p->lchild) 
            *root = NULL;

        // 只有一个左节点
        else if (!p->rchild&&p->lchild) 
            *root = p->lchild;

        // 只有一个右节点
        else if (!p->lchild&&p->rchild) 
            *root = p->rchild;

        //左右节点都不空
        else 
        {
            s = p->rchild;
            /* the s without left child */
            if (!s->lchild)
                s->lchild = p->lchild;
            /* the s have left child */
            else 
            {
                /* find the smallest node in the left subtree of s */
                while (s->lchild) 
                {
                    /* record the parent node of s */
                    parent = s;
                    s = s->lchild;
                }
                parent->lchild = s->rchild;
                s->lchild = p->lchild;
                s->rchild = p->rchild;
            }
            *root = s;
        }
        free(p);
    }
    else if (data > p->data) //向右找
        DeleteBSTNode(&(p->rchild), data);
    else if (data < p->data) //向左找
        DeleteBSTNode(&(p->lchild), data);
}

复杂度分析

操作	平均情况	最坏情况
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

遍历操作

中序遍历：左→根→右，得到有序序列
前序遍历：根→左→右，用于复制树结构
后序遍历：左→右→根，用于删除树

二叉排序树的查找效率

二叉排序树的查找效率主要取决于树的高度，最优情况下，当左右子树高度之差绝对值不超过1时（即平衡二叉树），平均查找长度与O(log₂n)，最坏情况，退化为链表，即当插入的元素有序时，形成一个只有右孩子的单枝数，平均查找长度为(n+1)/2

文字可能略显抽象，不妨看看视频：https://www.bilibili.com/video/BV1uK421x7JJ/

定义