二叉搜索树¶

二叉搜索树介绍¶

二叉搜索树，也称二叉排序树

二叉搜索树的特点：

1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

二叉搜索树结构设计¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 定义树每一个节点结构
template<class T>
struct binarySearchTreeNode
{
    // key值
    T _key;
    // 左子树指针
    binarySearchTreeNode<T>* _left;
    // 右子树指针
    binarySearchTreeNode<T>* _right;

    //单个节点构造函数
    binarySearchTreeNode(T key)
        :_key(key)
        , _left(nullptr)
        , _right(nullptr)
    {}
};

二叉搜索树操作设计¶

以下面的数组进行分析

1

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

按顺序依次实现下面的功能：

1. 二叉搜索树的查找
2. 二叉搜索树的插入
3. 二叉搜索树的中序遍历
4. 二叉搜索树的删除

二叉搜索树的查找¶

设计二叉搜索树时，因为二叉搜索树需要满足key值不重复，所以在插入数值之前需要先实现查找，确保二叉搜索树中当前没有该值

因为二叉搜索树满足左子树的节点值比根节点的值小，右子树的节点值比根节点的值大，所以在查找时可以采用类似二分的思想，假设查找值设为target

1. 如果target > root->_key时，则target出现的位置只可能在右子树
2. 如果target < root->_key时，则target出现的位置只可能在左子树
3. 二者相等代表查找到target

设计思路：

因为查找只需要判断是否存在即可，所以返回值类型设计为bool类型，从根节点开始向下遍历树，如果根节点不为空，判断当前节点的值与target的大小，如果target > root->_key，则走向右子树，否则走左子树

 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

// 树查找
bool findNode(const T& target)
{
    node* cur = _root;
    while (cur)
    {
        if (target == cur->_key)
        {
            // 如果找到返回true
            return true;
        }
        else if (target > cur->_key)
        {
            // 目标值大走右子树
            cur = cur->_right;
        }
        else
        {
            // 目标值小走左子树
            cur = cur->_left;
        }
    }

    //循环走完时证明没找到，返回false
    return false;
}

二叉搜索树的插入¶

有了二叉搜索树的查找后，在插入前需要调用查找函数判断插入的数值不是树中已经存在的数值。如果不存在插入的数值，则可以正常插入。

插入的步骤如下：

1. 判断节点值是否存在树中，存在则返回false，否则接着插入操作
2. 通过new创建一个节点，传入需要的key值进行初始化
3. 判断根节点是否为空，根节点为空则新节点作为根节点，否则接着插入操作
4. 插入节点时，如果插入的key > root->_key，则走左子树，否则走右子树，直到走到叶子结点，在遍历的过程中，需要一个变量parent记录父亲节点，否则无法插入新的节点
5. 当循环走完后，parent记录的就是需要的父亲节点，但是需要判断插入位置，如果插入的key比parent节点的值小，则插入在parent的左子树，否则插入在其右子树
6. 插入完成后返回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
48
49
50
51

// 树插入
bool insertNode(const T& key)
{
    // 判断key是否已经存在
    if (findNode(key))
    {
        // 已经存在时插入失败
        return false;
    }
    // 创建node节点
    node* newNode = new node(key);
    // 判断根节点是否为空，为空则作为第一个节点
    if (_root == nullptr)
    {
        _root = newNode;
        return true;
    }
    // 根节点不为空时接着遍历插入
    node* cur = _root;
    // 定义父亲节点记录父亲的位置
    node* parent = _root;
    while (cur)
    {
        if (key > cur->_key)
        {
            // 大于根节点数据，插入在右子树，走到左子树的空位置
            parent = cur;
            cur = cur->_right;
        }
        else if (key < cur->_key)
        {
            // 小于根节点数据，插入在左子树，走到右子树的空位置
            parent = cur;
            cur = cur->_left;
        }
    }

    // 循环走完后当前cur为空，parent为叶子节点，链接新节点
    if (parent->_key < key)
    {
        // 如果是右子树，则插入在右子树
        parent->_right = newNode;
    }
    else
    {
        // 否则插入在左子树
        parent->_left = newNode;
    }

    return true;
}

插入过程如下：

二叉搜索树的中序遍历¶

二叉搜索树的遍历等同于二叉树的遍历，但是需要注意：如果中序遍历函数有形参root，则在类外无法传入创建的对象树中的_root，所以为了处理这个问题可以使用子函数，子函数放在类内，可以访问当前类成员_root

首先设计子函数为中序遍历执行函数，设计思路参考二叉树基础中的二叉树中序遍历

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 中序遍历——子函数
void _inOrder(const node* root)
{
    // 如果节点为空返回
    if (root == nullptr)
    {
        return;
    }

    // 中序遍历
    _inOrder(root->_left);
    cout << root->_key << " " ;
    _inOrder(root->_right);
}

接着设计主调函数，设计主调函数则不需要设计形参，只需要传入一个类成员_root给子函数即可，此时的_root为this->_root，this指针中为调用对象的地址

1
2
3
4
5
6
7

// 中序遍历——主函数
void inOrder()
{
    // 调用子函数
    _inOrder(_root);
    cout << endl;
}

二叉搜索树的删除¶

二叉搜索树的节点删除有三种情况：

1. 节点为叶子结点，直接删除，例如图中的1,4,7,13：

   

2. 节点有一个孩子节点，删除节点时需要先找到该节点的父亲节点，由该父亲节点链接其孩子节点，例如图中的14节点

   

3. 节点有两个孩子节点，因为删除该节点后仍需要满足左子树的节点值比根节点的值小，右子树的节点值比根节点的值大，所以考虑在删除节点的左孩子节点的最右孩子节点或者删除节点的右孩子节点的最左孩子节点中选一个节点，将其值覆盖需要删除的父亲节点的值，再删除选择的孩子节点，例如删除图中的3节点

   

因为初始化时，将新创建的节点的左右指针置为空，所以如果删除叶子结点，也可以相当于用其父亲节点链接到空节点nullptr，所以对于第一种情况可以归类到第二种情况，总共两种情况需要考虑

删除步骤：

1. 判断根节点是否为空，如果根节点为空不执行删除，否则继续执行删除
2. 查找待删除节点是否存在，如果删除节点存在不存在不执行删除，否则继续执行删除
3. 查找节点的位置，如果找到了节点就开始删除：
   1. 考虑第一种情况（没有孩子节点和只有一个孩子节点），根据前面的分析，只需要将待删除节点的父亲节点链接其孩子节点即可。首先确定待删除的节点是左孩子为空还是右孩子为空，以左孩子为空为例，如果待删除节点的左孩子为空，则链接时，需要将待删除节点的父亲节点链接到待删除节点的右孩子，链接完成后删除节点，跳出循环即可
   2. 考虑第二种情况（有两个孩子节点），根据前面的分析，可以找一个节点覆盖待删除的节点的值，再删除该替换节点。所以就会出现既存在待删除节点的左子树的最右侧值（左子树的最大值），也存在待删除节点的右子树的最左侧值（右子树的最小值）。此时是否需要既考虑使用左子树的最右节点，又考虑使用右子树的最左节点呢？实际上，只需要考虑一种情况，例如选择待删除节点的右子树的最左节点，在二叉搜索树中，这个右子树最左节点一定存在。因为既然待删除的节点有两个孩子，那么右子树的这个孩子就也会有上面的三种情况：如果是第一种情况，那么待删除节点的右子树根节点就是最左节点；如果是第二种情况且右子树没有左孩子，那么待删除节点的右子树根节点就是最左节点；如果是第三种情况，那么待删除的节点的右孩子一定存在左孩子，以此类推，找到左孩子的最左节点即可。接着设计思路：因为在遍历过程中需要找到最左节点，所以用replaceNode来代表，因为最后删除的代替节点可能还存在孩子节点，所以依旧需要使用到第一种情况的思路，此时需要一个replaceNodeP记录替代节点的父亲节点的位置，找到replaceNode节点后将其值覆盖给删除的节点即可（也可以使用交换，但是没有必要），再进行第一种情况的步骤，最后删除替代节点即可
   3. 考虑完上述两种情况后，还有一种情况，如果只有一个根节点时，只考虑上面两种情况会导致程序崩溃，只有一个根节点时，此时根节点的左右子树均为空，属于第一种情况，删除之前需要让根指向其左孩子或者右孩子

在算法：二叉树基础练习篇也有对应的题目

 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

void eraseNode(const T& key)
{
    // 如果根节点为空，则不执行删除
    if (_root == nullptr)
        return;

    // 查找节点，如果节点不存在不执行删除
    if (findNode(key) == false)
        return;

    node* parent = nullptr;
    node* cur = _root;
    while (cur)
    {
        if (key > cur->_key)
        {
            // 大走右子树
            // 注意parent的位置要在if里面
            // 防止出现下一次cur为待删除的节点时，prev也变成了当前待删除的节点
            parent = cur;
            cur = cur->_right;
        }
        else if (key < cur->_key)
        {
            // 小走左子树
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            // 找到，删除
            if (cur->_right == nullptr)
            {
                // 考虑根节点的情况
                if (cur == _root)
                    _root = cur->_left;
                else
                {
                    if (parent->_right == cur)
                        parent->_right = cur->_left;
                    else if (parent->_left == cur)
                        parent->_left = cur->_left;
                }
                delete cur;
            }
            else if (cur->_left == nullptr)
            {
                // 考虑根节点的情况
                if (cur == _root)
                    _root = cur->_right;
                else
                {
                    // 找到孩子的位置后链接
                    if (parent->_left == cur)
                        parent->_left = cur->_right;
                    else if (parent->_right == cur)
                        parent->_right = cur->_right;
                }
                delete cur;
            }
            else
            {
                // 两个孩子节点
                // 找出适合的替代节点，选择右子树的最左孩子
                node* replaceNodeP = cur;
                node* replaceNode = cur->_right;

                // 一直向左子树走直到找到替代节点
                while (replaceNode->_left)
                {
                    replaceNodeP = replaceNode;
                    replaceNode = replaceNode->_left;
                }

                // 将replaceNode的值覆盖需要删除的节点
                cur->_key = replaceNode->_key;
                // 将replaceNode的父亲指向替换节点的孩子
                if (replaceNodeP->_left == replaceNode)
                    // 找的右子树的最左节点，一定没有左孩子
                    replaceNodeP->_left = replaceNode->_right;
                else
                    // replaceNodeP与待删除节点时同一个节点
                    replaceNodeP->_right = replaceNode->_right;
                delete replaceNode;
            }
            break;
        }
    }
}

二叉搜索树应用¶

1. K模型：在K模型中，只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索的值
2. KV模型：每一个关键码key都有对应的值value，称为<Key, Value>的键值对

对于前面实现的二叉搜索树来说，即为K模型，对前面的结构添加value值，构成<Key, Value>键值对模型

1. 修改单个节点结构

   C++
   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21	// 定义树每一个节点结构 template<class T, class V> struct binarySearchTreeNode { // key值 T _key; // value值 V _value; // 左子树指针 binarySearchTreeNode<T, V>* _left; // 右子树指针 binarySearchTreeNode<T, V>* _right; //单个节点构造函数 binarySearchTreeNode(const T& key, const V& value) :_key(key) ,_value(value) , _left(nullptr) , _right(nullptr) {} };

2. 修改查找函数返回值

   C++
   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	// 树查找 node* findNode(const T& target) { node* cur = _root; while (cur) { if (target == cur->_key) { // 如果找到返回节点 return cur; } else if (target > cur->_key) { // 目标值大走右子树 cur = cur->_right; } else { // 目标值小走左子树 cur = cur->_left; } } //循环走完时证明没找到，返回空指针 return nullptr; }

3. 修改插入函数

   C++

   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

   // 树插入 bool insertNode(const T& key, const V& value) { // 判断key是否已经存在 if (findNode(key)) { // 已经存在时插入失败 return false; } // 创建node节点 node* newNode = new node(key, value); // 判断根节点是否为空，为空则作为第一个节点 if (_root == nullptr) { _root = newNode; return true; } // 根节点不为空时接着遍历插入 node* cur = _root; // 定义父亲节点记录父亲的位置 node* parent = _root; while (cur) { if (key > cur->_key) { // 大于根节点数据，插入在右子树，走到左子树的空位置 parent = cur; cur = cur->_right; } else if (key < cur->_key) { // 小于根节点数据，插入在左子树，走到右子树的空位置 parent = cur; cur = cur->_left; } } // 循环走完后当前cur为空，parent为叶子节点，链接新节点 if (parent->_key < key) { // 如果是右子树，则插入在右子树 parent->_right = newNode; } else { // 否则插入在左子树 parent->_left = newNode; } return true; }

修改三处即可让原有的K模型变为KV模型

下面是常见的KV模型实际使用

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

void Test_dict()
{
    // 单词字典
    Key_Value::binarySearchTree<string, string> dict;
    dict.insertNode("string", "字符串");
    dict.insertNode("tree", "树");
    dict.insertNode("left", "左边、剩余");
    dict.insertNode("right", "右边");
    dict.insertNode("sort", "排序");
    // 读取输入判断是否存在于字典中
    string str;
    while (cin >> str)
    {
        Key_Value::binarySearchTreeNode<string, string>* ret = dict.findNode(str);
        if (ret)
        {
            cout << "->" << ret->_value << endl;
        }
        else
        {
            cout << "无此单词" << endl;
        }
    }
}

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

void Test_fruits_count()
{
    // 统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    Key_Value::binarySearchTree<string, int> fruitsCount;
    Key_Value::binarySearchTreeNode<string, int>* countNode;
    for (auto& str : arr)
    {
        countNode = fruitsCount.findNode(str);
        if (countNode == nullptr)
        {
            // 没出现过直接插入
            fruitsCount.insertNode(str, 1);
        }
        else
        {
            // 出现过改变出现次数
            countNode->_value++;
        }
    }

    // 遍历
    fruitsCount.inOrder();
}

二叉搜索树的效率¶

在上面的二叉搜索树中，一般情况下，时间复杂度为\(log_{2}{N}\)，但是最坏情况下会退化到\(O(N)\)（单支树）