暑假已经过去一半了，你的作业写的怎么样了？

不八八这些没啥用的了，本篇博客让我们来认识一下搜索二叉树以及KVL树，也为后续学习map和set打下基础。

在之前，我写过一篇用C语言实现的二叉树博客。如果你想了解二叉树的基本定义，可以看看👉 【传送门】

前言

树是我们生活中非常常见的玩意，其特点便是从下而上有非常多的分叉

数据结构中的树便是以该特点命名的，每一个节点会有左右两个分叉来链接左右子树，从而构成一种数据结构。

1.搜索二叉树

所谓搜索二叉树（二叉查找树），便是致力于方便搜索的一种数据结构，其具有一下特点：

• 比该节点大的数存放在右边
• 比该节点小的数存放在左边

这样当我们去遍历一颗搜索二叉树的时候，就可以很方便的通过大小比较找到其内部是否包含我们需要搜索的节点。这样在理想状态下，搜索的时间复杂度能控制在O(logN)，还是非常快的一个搜索算法！

因为搜索二叉树主要用于搜索而不是存储数据，所以一般情况下的搜索二叉树是不允许数据冗余的。即相同的值只会存储一次

• 同时，搜索二叉树可作为排序算法的一种。当我们用中序遍历搜索二叉树，得到的结果是有序的

---

1.1 基本构建

想要构建一个搜索二叉树，首先我们需要一个树的节点的结构

template<class K>
struct BSTreeNode
{
public:
	BSTreeNode* _left;
	BSTreeNode* _right;
	K _key;//元素

	BSTreeNode(K key)
		:_left(nullptr),
		_right(nullptr),
		_key(key)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 为何不直接把这个结构定义在二叉树的class里面？
• 因为那样会产生数据冗余而且非常不方便调用成员函数

在搜索二叉树的功能实现类中，我们只需要定义一个根部节点即可

template<class K>
class BSTree
{
typedef BSTreeNode<K> Node;//方便使用
private:
    //成员变量
	Node* _root=nullptr;
}
1
2
3
4
5
6
7
8

---

1.2 插入

有了基本结构以后，我们就可以写一个插入函数来进行最基本的操作了

• 当root为空的时候，需要给根节点开一个空间
• root不为空，定义prev和cur两个指针进行遍历，通过大小判断来找寻正确的插入位置（左边小，右边大）
• 找到正确位置后，构造新节点并进行插入操作

使用bool作为返回值是因为我们需要判断是否成功插入。如果成功插入了为true，没有成功插入代表该搜索二叉树内已经包含了相同键值的节点。

bool Insert(K key)
{
    if (_root == nullptr)
    {
        _root = new Node(key);//根为空，直接开空间插入
        return true;
    }

    Node* prev = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (key > cur->_key)
        {
            prev = cur;
            cur = cur->_right;
        }
        else if (key < cur->_key)
        {
            prev = cur;
            cur = cur->_left;
        }
        else
        {
            return false;//有相同元素不执行插入
        }
    }
	//创建节点进行插入
    cur = new Node(key);
    //保存prev指针就是为了操控它的父亲来链接节点
    if (key > prev->_key) {
        prev->_right = cur;
    }
    else{
        prev->_left = cur;
    }

    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

除了循环版本，我们还可以写一个递归版本

bool InsertR(const K& key)//实际调用的函数
{
    return _InsertR(_root, key);
}	

//使用引用，这时候的root就是上一个节点的左右子树的别名
//修改root的同时也会修改上一个子树的左右节点
//也可以用二级指针来完成这个操作，原理相同
bool _InsertR(Node*& root, const K& key)
{
    //空代表走到叶子了，执行插入
    if (root == nullptr) {
        Node* newNode = new Node(key);
        root = newNode;
        return true;
    }

    if (key > root->_key) {
        _InsertR(root->_right, key);
    }
    else if (key < root->_key) {
        _InsertR(root->_left, 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
23
24
25
26
27
28

此类二叉树的递归思路最好用画图来理清。需要明白每一个节点是怎么返回的

关于分支递归思想可以看看【链接】，这有助于你理解本文中的递归实现

上面的递归问题便是将原本利用循环进行左右寻找的操作化为往下调用下一课子树。简单来来说就是老师要班长、班长找小组长、小组长找组员这样分配工作。

只有走到最后的组员（空节点）我们才执行插入操作

1.3 中序打印

插入完成了，要怎样才能看到节点中的内容呢？来个中序遍历吧！

我们需要重写一个递归函数，因为在类外面无法访问到私有成员root，无法直接给该函数传参。如果想维持类的封装性，也可以把这个函数定义为private成员

    void InOrder()//中序遍历
    {
        _InOrder(_root);
    }
//private:
    void _InOrder(Node* root)
    { //递归打印
        if (root == nullptr)
            return ;

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

关于前中后序遍历的内容在之前C语言的博客中有过讲解，这里就不再赘述

---

1.4 查找

既然是搜索二叉树，那便必须要有查找函数。

其实在插入操作中，我们便已经把查找函数的思路写出来了（即判断是否是重复节点）

	//搜索二叉树一般不直接操作节点，不需要返回节点的指针
	//Node* Find(const K& key)
	bool Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (key > cur->_key)
			{
				cur = cur->_right;
			}
			else if (key < cur->_key)
			{
				cur = cur->_left;
			}
			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

同样，也可以写一个递归版本。当节点的值相等时返回true，如果走到空了代表这棵树里面没有这个节点，返回false

bool FindR(const K& key)//实际调用的函数
{
    return _FindR(_root, key);
}
//递归实现
bool _FindR(Node* root, const K& key)
{
    if (root == nullptr) {
        return false;
    }

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

1.5 删除(较难)

在搜索二叉树中删除节点并没有那么容易，因为我们需要保证删除节点后，树还满足搜索二叉树的特征。如果删除了之后破坏树的结构还不管他，那就是err了。

以下面的这棵树为例，它满足搜索二叉树的基本特征

假设我们需要删除节点4，这很容易，只需要让3的右子树为空，再delete掉4的节点即可。

但如果我们想删除6，事情就没那么简单了。我们需要找一个节点，来替补它的位置

• 那么，谁可以胜任这个新的位置呢？
• 答：左子树的最大节点or右子树的最小节点

在删除6的情况下，左子树的最大节点为4，右子树的最小节点为7。你会发现，将它们换上这个位置，的确满足搜索二叉树的特性

那么，怎么可以把这两个节点给替换上来呢？

这一套操作其实挺麻烦的

• 先找到需要删除的节点，会有下面3种情况：
  • 该节点只有左娃
  • 该节点只有右娃
  • 该节点左右都有
• 如果是前两种情况（包括没有孩子的情况），我们只需要删除这个节点之后，让它的父亲指向它的孩子就行了（托管）
  • 只有左娃，父节点托管左娃
  • 只有右娃，父节点托管右娃
• 左右都有孩子，需要找到左子树最大节点/右子树最小节点，进行交换

只是交换还远远不够，我们还需要链接这个最大/最小节点的孩子（比如上图中7的情况）再删除掉被交换过去的指定节点

//删除去找左子树的最大节点，或者右子树的最小节点
//与需要删除的树进行交换，交换之后删除叶子节点
bool Erase(const K& key)
{
    Node* prev = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (key > cur->_key)
        {
            prev = cur;
            cur = cur->_right;
        }
        else if (key < cur->_key)
        {
            prev = cur;
            cur = cur->_left;
        }
        else
        {
            if (cur->_left == nullptr)//只有右娃
            {
                if (cur == _root)
                {
                    _root = _root->_right;
                }
                else
                {
                    if (prev->_left == cur)
                    {
                        prev->_left = cur->_right;
                    }
                    else {
                        prev->_right = cur->_right;
                    }
                }
                delete cur;
            }
            else if (cur->_right == nullptr)//只有左娃
            {
                if (cur == _root)
                {
                    _root = _root->_left;
                }
                else
                {
                    if (prev->_left == cur)
                    {
                        prev->_left = cur->_left;
                    }
                    else {
                        prev->_right = cur->_left;
                    }
                }
                delete cur;
            }
            else //左右都有孩子
            {
                //将cur和右子树的最小值节点进行交换
                Node* minPrev = cur;
                Node* minRight = cur->_right;
                while (minRight->_left)
                {
                    minPrev = minRight;
                    minRight = minRight->_left;
                }

                swap(minRight->_key, cur->_key);
                if (minPrev->_left == minRight)
                {
                    minPrev->_left = minRight->_left;
                }
                else {
                    minPrev->_right = minRight->_left;
                }

                delete minRight;
            }
            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
76
77
78
79
80
81
82
83

执行之后可以看到，删除之后的树依旧是一个搜索二叉树，中序遍历结果呈有序

递归删除

写完了循环版本，再来个递归吧！

bool _EraseR(Node*& root, const K& key)
{
    //根直接为空，返回false
    if (root == nullptr) {
        return false;
    }

    if (key > root->_key) {
        _EraseR(root->_right, key);
    }
    else if (key < root->_key) {
        _EraseR(root->_left, key);
    }
    else 
    {
        Node* del = root;//保存变量用于删除

        if (root->_left == nullptr)//只有右娃
        {
            /*if (root == _root) {
					_root = _root->_left;
				}*/
            //这时候root是操作节点的别名，不需要单独对根节点进行处理
            root = root->_right;
        }
        else if (root->_right == nullptr)
        {
            root = root->_left;
        }
        else //左右都有孩子
        {
            //将cur和右子树的最小值节点进行交换
            Node* minRight = root->_right;
            //while (minRight) //err
            while (minRight->_left) //判断的是left，不然会走到空然后交换
            {
                minRight = minRight->_left;
            }

            swap(minRight->_key, root->_key);

            return _EraseR(root->_right, 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
46
47

在最后一个情况中，我们巧妙地将问题化为了在指定节点的右子再次执行一次删除操作

为什么在递归的操作中我们不需要单独处理minPrev呢？

注意看函数的接口。删除的递归操作需要才用一个很巧妙的做法，使用了引用参数，充分利用了函数传值时传引用的特点（别名）

bool _EraseR(Node*& root, const K& key)
1

这时候的节点root不仅是当前递归到的节点，同时也是上一个节点的左右节点的别名。对该节点的操作会直接改变上一个节点的左右子树，就省去了我们手动操作的步骤！

对root的修改会直接同步道上一个节点的孩子上

怎么样，是不是超级赞！

---

2.KVL树

2.1 概念

KV指代的是两个模板参数key和value。其实现和上面的搜索二叉树完全相同，只需要修改一下模板参数，以及所有操作key的位置都需要添加第二个参数value。

源码实现见我的代码仓库 链接

这么做的好处是，我们可以给一个key添加第二个绑定的参数了。一般把这种绑定关系称为键值对

KVL树的特点如下：

• 排序依据key来排序，而不是value
• key不可以修改，但是value可以修改
• 在保存键值关系的同时，去重+排序

通过这两个参数的绑定关系，我们可以实现类似字典、水果出现次数等等问题的查找操作，有点类似于数组映射，但这种方法更加便捷

---

2.2 示例

插入4个水果和其数量，中序遍历打印后，可以看到数据是以key为排序标准的。

这里说明的是，string也是可以比较大小的，所以同样适用于搜索二叉树

通过这种类似的绑定关系，我们甚至可以添加更多参数进入搜索二叉树。可以完成类似学生管理系统/车牌管理系统中学号车牌号和用户的绑定关系

2.3 允许数据冗余

我们可以简单修改一下插入函数，来达到允许数据冗余的目的。即插入相同key的时候，判断value，如果value也是相同则不插入，不同则插入。这样可以让kvl树中同一个key有多种对应关系，在字典多义词的时候有一定作用

//插入，通过传引用避免拷贝
bool _InsertR(Node*& root, const K& key, const V& value)
{
    if (root == nullptr)
    {
        root = new Node(key, value);
        return true;
    }

    if (root->_key < key)
        return _InsertR(root->_right, key, value);
    else if (root->_key > key)
        return _InsertR(root->_left, key, value);
    else{
        if (root->_value == value)
            return false;
        else{
            //将相同数据插入在右边
            return _InsertR(root->_right, key, value);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

插入了之后，我们删除也需要删除两次。

这时候我们EraseR返回值为bool的价值就体现出来了，我们可以直接写一个循环来删除掉多个冗余键值

---

结语

这两颗树的讲解到这里就结束啦，学习它们是为了后续学习map/set打基础哦！

有什么问题欢迎在评论区提出！