【数据结构】二叉搜索树--BST，Binary Search Tree

---

二叉搜索树

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可以是一颗空树，或者是一个满足如下性质的二叉树：

• 如果左子树不为空，左子树上所有节点的值都小于根节点；
• 如果右子树不为空，右子树上所有节点的值都大于根节点；

且它的左右子树，也满足上述性质。

举个栗子吧，以6为根节点的BST树结构：

template<class K>
struct bstree_node
{
    bstree_node<K>(K key)
        : _left(nullptr), _right(nullptr), _key(key)
    {}

    bstree_node<K>* _left;
    bstree_node<K>* _right;
    K _key;
};

template<class K>
class bstree
{
public:
  typedef bstree_node<K> node;
private:
    node* _root = nullptr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

两个又相同数组构成的二叉树，但是却形成了两个不同树结构。二叉搜索树最大的问题是会退化，比如右单枝，顺序插入时就会退化成一个链表。

搜索二叉树的效率体现在搜索上，最坏情况搜索高度次。所以树的高度越低，性能越好。所以一般不会使用单纯的搜索二叉树，而是使用升级版的AVL 树（平衡二叉搜索树）和红黑树

大概了解一下
AVL 树（平衡二叉搜索树）：

红黑树

 

2. 二叉搜索树的接口

2.1 查找

若根节点不为空：

• 如果节点值等于 $key$，返回 $true$，
• 如果节点值小于 $key$，到其右子树中查找，
• 如果节点值大于 $key$，到其左子树中查找，

走到空树还没找到，则返回 $false$。

非递归查找

bool find(const K& key)
{
    // 从根节点开始查找
    node* cur = _root;

    // 循环遍历树，直到当前节点为空（即没有找到）
    while (cur)
    {
        // 如果查找的键值小于当前节点的键值
        if (key < cur->_key)
        {
            // 移动到当前节点的左子节点，因为左子节点的键值更小
            cur = cur->_left;
        }
        // 如果查找的键值大于当前节点的键值
        else if (key > cur->_key)
        {
            // 移动到当前节点的右子节点，因为右子节点的键值更大
            cur = cur->_right;
        }
        // 如果查找的键值等于当前节点的键值
        else
        {
            return true;
        }
    }

    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二叉搜索树的查找非常的迅速，在二叉树相对平衡的情况下，时间复杂度高度次 $O(logN)$。最差是线性状态，为 $O(N)$。

递归查找

递归函数 find_r 会沿着树的结构向下搜索，每次比较 key 和当前节点的键值，决定向左或向右移动。这种递归调用会一直持续到找到匹配的键值或者遍历完整个树。

基本情况（终止条件）：
如果 root 是 nullptr，表示已经到达了树的末端，没有找到匹配的键值，因此返回 false。

递归调用：
如果 key 小于 root->_key，说明要查找的键值可能在左子树中，因此递归调用 _find_r(root->_left, key)。
如果 key 大于 root->_key，说明要查找的键值可能在右子树中，因此递归调用 _find_r(root->_right, key)。

找到匹配键值：
如果 key 等于 root->_key，表示找到了匹配的键值，立即返回 true。

bool find_r(const K& key)
{
    return _find_r(_root, key);
}

bool _find_r(node* root, const K& key)
{
    if (root == nullptr)
        return false;

    if (key < root->_key)
        return _find_r(root->_left, key);
    else if (key > root->_key)
        return _find_r(root->_right, key);
    else
        return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2 中序遍历

二叉搜索树的中序遍历结果，就是树中元素排成升序的结果。

void inorder()
{
    _inorder(_root);
    std::cout << std::endl;
}

void _inorder(node* root)
{
    if (root == nullptr)
        return;

    _inorder(root->_left);
    std::cout << root->_key << " ";
    _inorder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

一般成员函数在类外调用时，无法直接传入成员变量作参数。故可以将主体逻辑包装成子函数，再由成员函数去调用即可。

void TestBSTree() 
{
    BSTree<int> t;
    int a[] = { 7,1,3,6,4,8,7,9,3,2,5 }; //排序数组
    for (auto e : a) {
        t.Insert(e); //插入二叉搜索树
    }
    t.Inorder(); //中序遍历
}
1
2
3
4
5
6
7
8
9

如上代码，相当于利用二叉搜索树排序数组，而二叉搜索树结构天然具有排序加去重的功能。

2.3 插入

二叉搜索树的插入也很简单，共分两种情况：

1. 树为空，则直接插入，
2. 树不为空，则按性质查找到插入位置，再插入新节点。

cur指针进行比较并向下移动的同时，父指针parent始终指向cur的父节点。当cur走到空的时候，就创建新节点并链接到父节点的指针上。

1. 插入的值比当前节点的值小，则插入到左子树中，
2. 反之，比当前节点的值大，则插入到右子树中。

非递归插入

非递归插入方法通过迭代遍历二叉搜索树来找到新节点的插入位置。首先检查树是否为空，如果是，则直接将新节点设为根节点。如果树不为空，则从根节点开始，使用一个当前节点指针 cur 和一个父节点指针 parent 来跟踪遍历过程。在遍历过程中，根据新键值与当前节点键值的比较结果，决定向左子树还是右子树移动。如果新键值小于当前节点键值，则移动到左子节点；如果大于，则移动到右子节点。如果遇到相同键值的节点，则插入失败并返回 false。当 cur 为空时，表示已经到达了插入位置，此时根据新键值与 parent 节点键值的比较结果，在父节点的左或右子节点位置插入新节点。这种方法直观且易于理解，不需要额外的栈空间，适用于大多数情况下的树操作。

bool insert(const K& key)
{
    // 如果根节点为空，直接将新节点作为根节点
    if (_root == nullptr)
    {
        _root = new node(key);
        return true;
    }

    node* cur = _root;
    node* parent = nullptr;

    // 循环找到合适的插入位置
    while (cur)
    {
        if (key < cur->_key)
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (key > cur->_key)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
            return false; // 如果存在相同键值的节点，不插入
    }

    // 根据键值大小插入新节点
    if (key < parent->_key)
        parent->_left = new node(key);
    else
        parent->_right = new node(key);

    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

可见，二叉搜索树的每次插入都是把节点放在叶节点的位置上。

递归插入

递归插入方法通过递归调用函数自身来遍历二叉搜索树，并找到新节点的插入位置。递归函数 _insert_r 接受当前节点指针的引用和要插入的键值作为参数。如果当前节点为空，表示到达了插入位置，此时创建一个新节点并将其赋值给当前节点指针，然后返回 true 表示插入成功。如果新键值小于当前节点键值，则递归调用函数在左子树中继续查找插入位置；如果新键值大于当前节点键值，则递归调用函数在右子树中查找。如果遇到相同键值的节点，则返回 false 表示插入失败。递归插入方法简洁优雅，代码量少，但可能会因为递归调用导致栈空间的使用增加，对于大型树结构可能存在性能问题。然而，对于小型或中型树结构，递归插入是一种高效且易于实现的方法。

bool insert_r(const K& key)
{
    return _insert_r(_root, key);
}

bool _insert_r(node*& root, const K& key)
{
    // 如果当前节点为空，创建新节点并返回true
    if (root == nullptr)
    {
        root = new node(key);
        return true;
    }

    // 根据键值大小递归插入左子树或右子树
    if (key < root->_key)
        return _insert_r(root->_left, key);
    else if (key > root->_key)
        return _insert_r(root->_right, key);
    else
        return false; // 如果存在相同键值的节点，不插入
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

参数类型是节点指针的引用，使得root不仅是节点指针，还是其父节点的左或右孩子指针，修改root也就修改了父节点的左右孩子。

2.4 删除

二叉搜索树的难点在于删除，因为节删除节点需要维护剩余节点的链接关系。

删除叶节点很容易，释放节点并置空父节点的指针即可。删除非叶结点，可以将子树中满足条件的节点替换上来。

如果节点不存在先返回 $false$，如果存在，则分以下几种情况：
1.直接删除：

2.替换删除：

1. 先将左树最大节点的左孩子托，或是右树最小节点的右孩子托付给父节点。
2. 再将左树最大节点覆盖待删除的节点。

非递归删除

bool erase(const K& key)
{
    node* parent = nullptr; // 父节点指针初始化为nullptr
    node* cur = _root; // 当前节点指针指向根节点

    while (cur) // 循环遍历直到当前节点为空
    {
        if (key < cur->_key) // 如果搜索键小于当前节点键值
        {
            parent = cur; // 更新父节点指针为当前节点
            cur = cur->_left; // 移动到左子节点
        }
        else if (key > cur->_key) // 如果搜索键大于当前节点键值
        {
            parent = cur; // 更新父节点指针为当前节点
            cur = cur->_right; // 移动到右子节点
        }
        else // 如果搜到到匹配的键值
        {
            if (!cur->_left) // 如果当前节点没有左子节点
            {
                if (parent == nullptr)
                    _root = _root->_right;
                else if (cur == parent->_left)
                    parent->_left = cur->_right;
                else
                    parent->_right = cur->_right;
                delete cur; // 删除当前节点
            }
            else if (!cur->_right) // 如果当前节点没有右子节点
            {
                if (parent == nullptr)
                    _root = _root->_left;
                else if (cur == parent->_left)
                    parent->_left = cur->_left;
                else
                    parent->_right = cur->_left;
                delete cur; // 删除当前节点
            }
            else // 如果当前节点有左右子节点
            {
#ifdef 方式1 // 采用方式1删除节点--直接删除
                node* min = cur->_right; // 当前节点的右子树中找到最小节点
                while (min->_left)
                    min = min->_left;
                
                K minkey = min->_key;
                erase(min->_key);
                cur->_key = minkey;
#endif
                
#ifdef 方式2 // 采用方式2删除节点--替换删除
                node* min_parent = cur; // 最小节点的父节点
                node* min = cur->_right; // 当前节点的右子树中找到最小节点

                while (min->_left)
                {
                    min_parent = min;
                    min = min->_left;
                }

                cur->_key = min->_key; // 更新当前节点的键值为最小节点的键值

                if (min == min_parent->_left)
                    min_parent->_left = min->_right;
                else
                    min_parent->_right = min->_right;
                delete min; // 删除最小节点
#endif
            }
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

递归删除

bool erase_r(const K& key)
{
    // 调用递归删除函数，传入根节点指针和搜索键值
    return _erase_r(_root, key);
}

bool _erase_r(node*& root, const K& key)
{
    // 如果当前子树根节点为空，返回false
    if (root == nullptr)
        return false;

    // 根据搜索键值与当前节点键值的比较，决定进入左子树或右子树进行递归删除
    if (key < root->_key)
        return _erase_r(root->_left, key);
    else if (key > root->_key)
        return _erase_r(root->_right, key);
    else
    {
        // 保存当前节点指针
        node* del = root;
        
        // 如果当前节点没有左子节点，将右子节点替换当前节点
        if (!root->_left)
            root = root->_right;
        // 如果当前节点没有右子节点，将左子节点替换当前节点
        else if (!root->_right)
            root = root->_left;
        else
        {
            // 寻找右子树中的最小节点
            node* min = root->_right;
            while(min->_left)
                min = min->_left;

            root->_key = min->_key; // 更新当前节点键值为最小节点键值
            // 递归删除最小节点，并返回结果
            return _erase_r(root->_right, min->_key);
        }

        // 释放删除节点
        delete del;
        return true; // 返回删除成功
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

 

3. 二叉搜索树的应用

搜索树有两种应用，key搜索模型和key/value搜索模型。此外，二叉搜索树插入重复值会失败，所以自带去重功能。

key搜索模型

key搜索模型查找返回真假，只能用来判断数据是否存在。应用场景如存储车牌号判断是否放行等。

kv搜索模型

通过key查找对应value，两个值是强相关的映射关系。 应用场景如中英互译，身份绑定等。

cpp

Copy code
// 结构体定义包括键值对节点和左右子节点指针
template<class K, class V>
struct bstree_node
{
    bstree_node<K, V>* _left;
    bstree_node<K, V>* _right;
    K _key;
    V _val;

    // 构造函数初始化键、值和左右子节点指针
    bstree_node<K, V>(const K& key, const V& val)
        : _key(key), _val(val), _left(nullptr), _right(nullptr)
    {}
};

// 二叉搜索树类
template<class K, class V>
class bstree
{
    typedef bstree_node<K, V> node; // 节点类型定义为树节点结构体
public:
    // 插入节点函数，传入键值和值，返回插入是否成功
    bool insert(const K& key, const V& val)
    {
        if (_root == nullptr) // 如果根节点为空
        {
            _root = new node(key, val); // 创建新节点作为根节点
            return true;
        }

        node* parent = nullptr; // 父指针初始化为空
        node* cur = _root; // 当前节点指针指向根节点

        while (cur) // 循环查找插入位置
        {
            if (key < cur->_key) // 如果插入键值小于当前节点键值
            {
                parent = cur; // 更新父指针为当前节点
                cur = cur->_left; // 移动到左子节点
            }
            else if (key > cur->_key) // 如果插入键值大于当前节点键值
            {
                parent = cur; // 更新父指针为当前节点
                cur = cur->_right; // 移动到右子节点
            }
            else
                return false; // 如果键值相等，返回失败
        }

        if (key < parent->_key) // 根据父节点键值判断位置插入左子节点或右子节点
            parent->_left = new node(key, val); // 创建新节点作为左子节点
        else if (key > parent->_key)
            parent->_right = new node(key, val); // 创建新节点作为右子节点

        return true; // 返回插入成功
    }

    // 查找键值对应节点，返回找到的节点指针，如果不存在返回空指针
    node* find(const K& key)
    {
        node* cur = _root; // 当前节点指针指向根节点

        while (cur) // 循环查找节点
        {
            if (key < cur->_key) // 如果搜索键值小于当前节点键值
                cur = cur->_left; // 移动到左子节点
            else if (key > cur->_key) // 如果搜索键值大于当前节点键值
                cur = cur->_right; // 移动到右子节点
            else
                return cur; // 找到匹配键值时返回当前节点
        }
        return nullptr; // 没找到返回空指针
    }

    // 删除节点函数，传入键值，返回删除是否成功
    bool erase(const K& key)
    {
        node* parent = nullptr; // 父节点指针初始化为空
        node* cur = _root; // 当前节点指针指向根节点

        while (cur) // 循环查找删除节点
        {
            if (key < cur->_key) // 如果键值小于当前节点键值
            {
                parent = cur; // 更新父节点指针为当前节点
                cur = cur->_left; // 移动到左子节点
            }
            else if (key > cur->_key) // 如果键值大于当前节点键值
            {
                parent = cur; // 更新父节点指针为当前节点
                cur = cur->_right; // 移动到右子节点
            }
            else // 找到匹配键值的节点
            {
                if (!cur->_left) // 如果当前节点没有左子节点
                {
                    if (!parent) // 如果父节点为空，说明当前节点为根节点
                        _root = _root->_right; // 将根节点替换为右子节点
                    else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
                        parent->_left = cur->_right; // 将父节点的左子节点替换为当前节点的右子节点
                    else
                        parent->_right = cur->_right; // 将父节点的右子节点替换为当前节点的右子节点
                    delete cur; // 删除当前节点
                }
                else if (!cur->_right) // 如果当前节点没有右子节点
                {
                    if (!parent) // 如果父节点为空，说明当前节点为根节点
                        _root = _root->_left; // 将根节点替换为左子节点
                    else if (cur == parent->_left) // 如果当前节点是父节点的左子节点
                        parent->_left = cur->_left; // 将父节点的左子节点替换为当前节点的左子节点
                    else
                        parent->_right = cur->_left; // 将父节点的右子节点替换为当前节点的左子节点
                    delete cur; // 删除当前节点
                }
                else // 如果当前节点有左右子节点
                {
                    node* min_parent = cur; // 最小节点的父节点初始化为当前节点
                    node* min = cur->_right; // 最小节点指针初始化为当前节点的右子节点

                    while (min->_left) // 寻找右子树中的最小节点
                    {
                        min_parent = min;
                        min = min->_left;
                    }

                    cur->_key = min->_key; // 更新当前节点键值为最小节点键值
                    cur->_val = min->_val; // 更新当前节点值为最小节点值

                    if (min == min_parent->_left) // 将最小节点的父节点指向最小节点右子节点
                        min_parent->_left = min->_right;
                    else
                        min_parent->_right = min->_right;
                    delete min; // 删除最小节点
                }

                return true; // 返回删除成功
            }
        }
        return false; // 未找到匹配键值，返回删除失败
    }

    // 中序遍历函数，输出键值对
    void inorder()
    {
        _inorder(_root); // 调用内部中序遍历函数
        cout << endl; // 换行
    }

    // 中序遍历辅助函数
    void _inorder(node* root)
    {
        if (!root) // 如果当前节点为空，返回
            return;

        _inorder(root->_left); // 递归遍历左子树
        cout << root->_key << "-" << root->_val << endl; // 输出当前节点键值对
        _inorder(root->_right); // 递归遍历右子树
    }

private:
    node* _root = nullptr; // 根节点指针初始化为空
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165

 

5. oj题