二叉搜索树#

一种特殊的二叉树，这里单独进行讨论

一个二叉搜索树，有如下性质：

对于树内的任何节点，左子节点 < 父节点 < 右子节点
树内元素不重复

为了方便讨论，我们定义如下结构，并定义测试数据：

1
struct TreeNode {
2
    int val = 0;
3
    TreeNode* left = nullptr;
4
    TreeNode* right = nullptr;
5

6
    TreeNode()=default;
7
    TreeNode(int v): val(v) {}
8

9
    void print() {
10
        if (left == nullptr && right == nullptr)
11
            std::cout <<"("<< val <<")";
12
        else
13
            std::cout << val << ":{" ;
14

15
        if (left)
16
            left->print();
17
        if (right)
18
            right->print();
19

20
        if (!(left == nullptr && right == nullptr)) {
21
            std::cout << "}";
22
        }
23
    }
24
};
25

26
class BSTree {
27
    TreeNode* root;
28

29
public:
30
    BSTree()=default;
31
};

下面，我们将对 BSTree 类进行扩写，同时，这蕴含着二叉搜索树里面的一些知识

插入操作#

得益于二叉树自身的特殊性质，插入时，我们只需按照下面的原则进行就行：

对要插入的元素与当前节点进行检查，如果要插入元素大于当前节点元素，则在右边进行插入，否则在左边进行

代码：

1
void insert(int element, TreeNode* current = nullptr) {
2
    if (!current) {
3
        // Is root
4
        if (element >= root->val) {
5
            if (root->right != nullptr) {
6
                insert(element, root->right);
7
            }
8
            else {
9
                root->right = new TreeNode(element);
10
            }
11
        }
12
        else {
13
            if (root->left != nullptr) {
14
                insert(element, root->left);
15
            }
16
            else {
17
                root->left = new TreeNode(element);
18
            }
19
        }
20
    }
21
    else {
22
        if (element >= current->val) {
23
            if (current->right != nullptr) {
24
                insert(element, current->right);
25
            }
26
            else {
27
                current->right = new TreeNode(element);
28
            }
29
        }
30
        else {
31
            if (current->left != nullptr) {
32
                insert(element, current->left);
33
            }
34
            else {
35
                current->left = new TreeNode(element);
36
            }
37
        }
38
    }
39
}

删除操作#

比较麻烦的是删除操作，需要对目标的**度（D）**进行讨论，统共分三种情况：

$D = 1$
$D = 2$
$D = 0$

$D = 0$ 的情况#

$D = 0$ 的情况是最好解决的，因为这个时候直接把这个节点删除即可，删除之后，不会对原有树造成影响

$D = 1$ 的情况#

当 $D = 1$ 时，需要将该节点下的子节点接上当前节点的父节点，从而达到当前节点被删除的目的

$D = 2$ 的情况#

当 $D = 2$ 时，情况复杂许多，不能像 $D = 0$ 那样直接删除；也不能像 $D = 1$ 进行简单的变换

因此，必须对当前的节点进行一定的替换的操作；换言之，用某一个符合BST性质的节点来替换当前节点

事实上，这个节点可以是右子树的最小节点或左子树的最大节点，如下举例：

综上所述，我们可以把删除某个节点的代码如下写：

1
void del(int target) {
2
    if (root == nullptr)
3
        return;
4
    TreeNode *cur = root, *pre = nullptr;
5
    while (cur != nullptr) {
6
        if (cur->val == target)
7
            break;
8
        pre = cur;
9
        if (cur->val < target)
10
            cur = cur->right;
11
        else
12
            cur = cur->left;
13
    }
14
    if (cur == nullptr)
15
        return;
16
    if (cur->left == nullptr || cur->right == nullptr) {
17
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
18
        if (cur != root) {
19
            if (pre->left == cur)
20
                pre->left = child;
21
            else
22
                pre->right = child;
23
        } else {
24
            root = child;
25
        }
26
        delete cur;
27
    }
28
    else {
29
        TreeNode *tmp = cur->right;
30
        while (tmp->left != nullptr) {
31
            tmp = tmp->left;
32
        }
33
        int tmpVal = tmp->val;
34
        del(tmp->val);
35
        cur->val = tmpVal;
36
    }
37
}

查找操作#

查找二叉搜索树内的某个元素时，得益于BST自身的性质，我们可以很简单的进行操作：

对比目标元素与当前节点的元素，如果目标元素大于当前节点元素，在右侧进行比较，否则在左侧进行比较：

1
bool has(int target) {
2
    TreeNode *cur = root;
3
    while (cur != nullptr) {
4
        if (cur->val < target)
5
            cur = cur->right;
6
        else if (cur->val > target)
7
            cur = cur->left;
8
        else
9
            break;
10
    }
11
    return cur;
12
}

效率对比#

使用二叉搜索树和数组查找的方式如下表进行对比：

对比项	数组查找	BST
查找	$O(n)$	$O(log n)$
插入	$O(1)$	$O(log n)$
删除	$O(n)$	$O(log n)$

由上表不难看出，BST相比于数组方式更加稳定；但即便如此，数组在高频添加、低频查找删除数据的情景下效率比BST要高

参考#

Hello algo - 7.4 二叉搜索树