二叉排序树：查找、插入与删除

各位同学，今天我们来聊聊二叉排序树。说实话，这是我在实际项目中用得最多的数据结构之一。记得我刚入行那会儿，有个项目需要频繁地做动态数据查找，用数组吧，插入删除太慢；用链表吧，查找又成了O(n)。后来我师父跟我说：“试试二叉排序树。”嗯，这一试，就用了十几年。

什么是二叉排序树？

二叉排序树，也叫二叉搜索树。它本质上是一棵二叉树，但多了个排序规则：

• 左子树上所有节点的值，都小于根节点的值
• 右子树上所有节点的值，都大于根节点的值
• 左右子树本身也是二叉排序树

说白了，就是中序遍历一下，出来的结果就是从小到大排好序的。这个特性，让它在查找、插入、删除上都有不错的表现。

二叉排序树的查找

查找操作是二叉排序树最基础的操作。我习惯这么写：

// 递归查找
BSTNode* search(BSTNode* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

// 非递归查找（我个人更推荐这个，避免栈溢出）
BSTNode* search_iter(BSTNode* root, int key) {
    BSTNode* p = root;
    while (p != NULL && p->data != key) {
        if (key < p->data) {
            p = p->left;
        } else {
            p = p->right;
        }
    }
    return p;
}

查找的效率取决于树的高度。理想情况下是O(log n)，但最坏情况会退化成O(n)。为什么会这样？你想想看，如果插入的数据本身就是有序的，比如1,2,3,4,5...那树就变成了一条斜线，跟链表没区别了。

二叉排序树的插入

插入操作其实就是在查找的基础上，找到合适的位置挂上去。我见过很多新手会纠结“插入后要不要调整树的结构”，其实不用，二叉排序树的插入就是纯粹的叶子节点插入。

BSTNode* insert(BSTNode* root, int key) {
    if (root == NULL) {
        BSTNode* newNode = (BSTNode*)malloc(sizeof(BSTNode));
        newNode->data = key;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    
    if (key < root->data) {
        root->left = insert(root->left, key);
    } else if (key > root->data) {
        root->right = insert(root->right, key);
    }
    // 如果相等，一般不做处理，或者根据需求覆盖
    return root;
}

这里有个细节：如果插入的值已经存在，我一般选择忽略。但在某些场景下，比如你要统计词频，那就要做累加处理。嗯，具体看业务需求。

二叉排序树的删除

删除操作是二叉排序树里最复杂的。我把它分成三种情况来记：

情况	描述	处理方式
情况一	删除叶子节点	直接删除，父节点对应指针置空
情况二	删除只有左子树或只有右子树的节点	用子节点替换被删除节点
情况三	删除既有左子树又有右子树的节点	找前驱或后继节点替换，然后删除前驱/后继

第三种情况最麻烦。我习惯找右子树的最小节点（也就是中序遍历的后继）来替换。为什么？因为右子树的最小节点一定没有左子树，删除它的时候最多是情况二，好处理。

BSTNode* deleteNode(BSTNode* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        // 找到要删除的节点了
        // 情况一和二：只有一个子节点或没有子节点
        if (root->left == NULL) {
            BSTNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            BSTNode* temp = root->left;
            free(root);
            return temp;
        }
        
        // 情况三：有两个子节点
        // 找右子树的最小节点
        BSTNode* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

BSTNode* findMin(BSTNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

二叉排序树的查找性能分析

查找性能说白了就一句话：取决于树的高度。

• 最好情况：树是平衡的，高度为log₂n，查找时间复杂度O(log n)
• 最坏情况：树退化成单链表，高度为n，查找时间复杂度O(n)
• 平均情况：随机插入的情况下，平均查找长度约为1.38log₂n

我给大家画个图，直观感受一下二叉排序树的知识体系：

从这张图可以看出来，二叉排序树的核心就是围绕“左小右大”这个规则展开的。查找、插入、删除都依赖这个规则。而性能分析告诉我们，树的高度决定了效率，所以实际工程中我们往往需要引入平衡机制。

好了，今天就讲到这里。代码我建议你亲手敲一遍，尤其是删除操作，多跑几个测试用例。我在项目里吃过亏，所以特别强调这一点。