二叉树

  首先我们要说明一下二叉树。二叉树是指所有节点的子节点数量均小于等于2的树，其还可以细分为：有根二叉树（rooted binary tree）、完整二叉树（full/proper binary tree）、完全二叉树（complete binary tree）三类。大多数情况下，“二叉树”一词均指“有根二叉树”。

注：Proper binary tree 的汉译名称不固定，且完全二叉树和满二叉树的定义在不同教材中定义不同，遇到的时候需根据上下文加以判断。

  在本文中，我们不区分二叉树的分类，全部统称为“二叉树”。

二叉搜索树

  顾名思义，二叉搜索树是基于二叉树实现的，所以它需要满足二叉树的定义。同时，它还需要满足如下条件：

  1. 任意一个节点的左子树（如果有的话）中所有节点的权值要小于当前节点的权值
  2. 任意一个节点的右子树（如果有的话）中所有节点的权值要大于当前节点的权值

  额外的，我们规定一颗空树（没有节点的树）也是二叉搜索树。

  根据上面的条件，我们还能得出一个推论：一个二叉搜索树的子树也是二叉搜索树。

  如下图，便是一颗二叉搜索树：

二叉搜索树示例

代码约定

  我们用如下的结构体存储树（左右子树为nullptr表示没有子树）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//二叉树节点
struct node {

    //当前节点的权值
    int value;
    //父节点
    node* fat = nullptr;
    //左子树
    node* left = nullptr;
    //右子树
    node* right = nullptr;
    
    node(int value, node* father): value(value), fat(father) {}
    
    inline bool operator<(int _value) const {
        return value < _value;
    }
    
};

inline bool operator<(int value, const node& that) {
    return value < that.value;
}
1
2
3
4
5
6
7
//二叉搜索树
struct bst {
    
    //根节点
    node* root = nullptr;
    
}

下文再次出现struct bst或struct node表明对该声明的补充

查找

  首先，我们来看最简单的查找操作。例如，我们要从上面给出的树中查找到5这个数字，我们应当如何查找呢？

  让我们用一个动图展示搜索过程：

二叉树搜索

文字描述

 首先我们从根节点开始搜索

 对于每一个搜索到的节点：

  如果当前节点的权值大于目标值，那么向向左子树方向继续搜索

  如果当前节点的权值小于目标值，那么向右子树方向继续搜索

  如果当前节点的权值等于目标值，说明找到了元素

 注：如果在拓展搜索的过程中出现需要向左（右）子树搜索但没有左（右）子树的情况就说明要搜索的元素在树中不存在。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct bst {
    
    //以当前节点为根节点，查找树中是否存在目标元素
    inline bool contain(int dist) const {
        return find(dist) != nullptr;
    }
    
    node* find(int dist) {
        if (root == nullptr) return nullptr;
        node* point = root;
        while (point != nullptr) {
            if (*point < dist) point = point->right;
            else if (dist < *point) point = point->left;
            else return point;
        }
        return nullptr;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
struct bst {

    inline bool contain(int dist) const {
        return find(dist) != nullptr;
    }

    node* find(dist) {
        if (root == nullptr) return nullptr;
        return root->find(dist);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node {

    //以当前节点为根节点，查找树中是否存在目标元素
    node* find(int dist) const {
        if (*this < dist) {
            if (right == nullptr) return nullptr;
            return right->find(dist);
        } else if (dist < *this) {
            if (left == nullptr) return nullptr;
            return left->find(dist);
        }
        return this;
    }
    
}

插入

  对于插入，其实也是一个搜索过程。假如我们要向以R为根节点的树中插入元素V：

  1. 如果R为nullptr，那么把R设置为V并退出，否则继续
  2. 如果R的权值与V相等，说明元素重复，不做操作（也可以进行计数）直接退出
  3. 如果R的权值小于V，那么将V插入到其右子树中
  4. 如果R的权值大于V，那么将V插入到其左子树中

  效果就是在不改变原有节点关系的情况下让要插入的节点成为树中某一个节点的子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct node {

    node* insert(int dist) {
        node** point = &root;
        node* fat = nullptr;
        while (*point != nullptr) {
            auto key = *point;
            if (dist < *key) point = &key->left;
            else if (*key < dist) point = &key->right;
            else return key;
            fat = *point;
        }
        return *point = new node(dist, fat);
    }

}
1
2
3
4
5
6
7
8
struct bst {

    node* insert(int dist) {
        if (root == nullptr) return root = new node(dist, nullptr);
        return root->insert(dist);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct node {

    node* insert(int dist) {
        if (dist < *this) {
            if (left == nullptr) return left = new node(dist, this);
            return left->insert(dist);
        } else if (*this < dist) {
            if (right == nullptr) return right = new node(dist, this);
            return right->insert(dist);
        }
        return this;
    }
    
}

删除

  删除节点的操作比插入复杂一点点，我们要分三种情况讨论：

  1. 如果要删除的节点是叶节点（没有子节点），那么直接删除它
  2. 如果要删除的节点有且只有一个子节点，那么让其子节点替换它当前位置并删除它
  3. 如果要删除的节点有两个节点，那么用它左子树的最大值（或右子树的最小值）替换它，然后将它删除

  前两种情况很好理解，最后一种情况是怎么回事呢？

  如果我们不这么做，那么当我们移除掉这个节点后，我们需要找一个合适的地方把多出来的两个子树插入进去，这是一个很复杂的操作。但是如果我们按照上面说的操作进行运算，我们会发现，删除掉这个节点后，新的树一定满足二叉搜索树的性质。

  我们来证明一下，假如我们要删除节点Del，其父节点为Fat，左右节点分别为Left、Right，其左子树的最大值为LM,右子树的最小值为RM。

  如果Del是Fat的左子树：

  1. LM < Del < Fat
  2. Right < Fat
  3. Left < Del < Right
  4. Left ≤ LM

易得：Left ≤ LM < Right < Fat
当LM = Left时表明Del的左子树只有一个节点

  如果Del是Fat的右子树：

  1. Fat < LM < Del
  2. Fat < Left
  3. Left < Del < Right
  4. Left ≤ LM

易得：Fat < Left ≤ LM < Right
当LM = Left时表明Del的左子树只有一个节点

  综上所述，当使用LM取代Del时其一定符合二叉搜索树的性质。

  如果Del是Fat的左子树：

  1. Del < RM < Fat
  2. Right < Fat
  3. Left < Del < Right
  4. RM ≤ Right

易得：Left < RM ≤ Right < Fat
当RM = Right时表明Del的右子树只有一个节点

  如果Del是Fat的右子树：

  1. Fat < Del < RM
  2. Fat < Left
  3. Left < Del < Right
  4. RM ≤ Right

易得：Fat < Left < RM ≤ Right
当RM = Right时表明Del的右子树只有一个节点

  综上所述，当使用RM取代Del时其一定符合二叉搜索树的性质。

温馨提示：删除的循环与递归的实现只有node中的代码不同

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
struct bst {

    //移除指定节点
    //返回值：是否成功移除
    bool erase(int dist) {
        node* delPtr = find(dist);
        if (delPtr == nullptr) return false;
        node& del = *delPtr;
        if (del.left == nullptr) {
            if (del.right == nullptr) {
                del.fat->removeNearly(delPtr);
            } else {
                del.fat->swapNearly(delPtr, del.right);
                del.right->fat = del.fat;
            }
        } else if (del.right == nullptr) {
            del.fat->swapNearly(delPtr, del.left);
            del.left-> fat = del.fat;
        } else {
            //也可以写成 del.left->findMaxValue()
            node* rm = del.right->findMinValue();
            rm->fat->removeNearly(rm);
            rm->fat = del.fat;
            del.fat->swapNearly(del, rm);
            del.right->fat = rm;
        }
        return true;
    }
    
}

struct node {

    //从当前节点开始寻找LM
    node* findMaxValue() {
        node* point = this;
        while (true) {
            if (point->right == nullptr) return point;
            point = point->right;
        }
    }

    //从当前节点开始寻找RM
    node* findMinValue() {
        node* point = this;
        while (true) {
            if (point->left == nullptr) return point;
            point = point->left;
        }
    }

    //将指定节点从该节点相邻的节点中移除
    //返回值：是否移除成功
    inline bool removeNearly(node* point) {
        return swapNearly(point, nullptr);
    }

    //将指定的相邻节点替换为另一个节点
    //返回值：是否替换成功
    inline bool swapNearly(node* src, node* dist) {
        if (left == src) left = dist;
        else if (right == src) right = dist;
        else if (fat == src) src = dist;
        else return false;
        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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct bst {

    //移除指定节点
    //返回值：是否成功移除
    bool erase(int dist) {
        node* delPtr = find(dist);
        if (delPtr == nullptr) return false;
        node& del = *delPtr;
        if (del.left == nullptr) {
            if (del.right == nullptr) {
                del.fat->removeNearly(delPtr);
            } else {
                del.fat->swapNearly(delPtr, del.right);
                del.right->fat = del.fat;
            }
        } else if (del.right == nullptr) {
            del.fat->swapNearly(delPtr, del.left);
            del.left-> fat = del.fat;
        } else {
            //也可以写成 del.left->findMaxValue()
            node* rm = del.right->findMinValue();
            rm->fat->removeNearly(rm);
            rm->fat = del.fat;
            del.fat->swapNearly(del, rm);
            del.right->fat = rm;
        }
        return true;
    }
    
}

struct node {

    //从当前节点开始寻找LM
    node* findMaxValue() {
        if (right == nullptr) return this;
        return right->findMaxValue();
    }

    //从当前节点开始寻找RM
    node* findMinValue() {
        if (left == nullptr) return this;
        return left->findMinValue();
    }

    //将指定节点从该节点相邻的节点中移除
    //返回值：是否移除成功
    inline bool removeNearly(node* point) {
        return swapNearly(point, nullptr);
    }

    //将指定的相邻节点替换为另一个节点
    //返回值：是否替换成功
    inline bool swapNearly(node* src, node* dist) {
        if (left == src) left = dist;
        else if (right == src) right = dist;
        else if (fat == src) src = dist;
        else return false;
        return true;
    }

}

退化

  上面的一切看起来都非常美好，但是在实际应用中，二叉搜索树非常容易出现退化现象，比如我们按照如下顺序插入节点：

1 -> 2 -> 3 -> 4 -> 5

  那么树就变成了下面这个样子：

二叉搜索树的机端情况

时间复杂度

  观察二叉搜索树查找节点的过程不难发现，二叉搜索树的性能与树的高度密切相关。其在最优情况下的时间复杂度为O(logN)，最坏时会退化为O(N)。

参考资料

  本文参考了一下资料（没有先后顺序）：