1.二叉搜索树

1.1 定义

二叉搜索树：

  • 一棵非空的二叉搜索树每个元素都有一个关键字，并且任意两个元素的关键字不同，所有关键字都是唯一的
  • 根节点的左子树小于根节点的关键字
  • 根节点的右子树大于根节点的关键字
  • 左右子树也是二叉搜索树

索引二叉搜索树：

　　源于普通的二叉搜索树，在每个节点中添加一个 leftSize 字段，用来保存该节点左子树的元素个数。

1.2 二叉搜索树的操作和实现

1.2.1 搜索

根据搜索元素的 theKey 对应向左孩子或右孩子移动寻找即可，时间复杂度为O(height)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<class K, class E>
pair<const K, E>* binarySearchTree<K, E>::find(const K& theKey) const
{// 返回关键字时K的元素指针
   // 从根节点 p 开始搜索，寻找关键字为 theKey 的元素
    binaryTreeNode<pair<const K, E> >* p = root;
    while (p != NULL)
        // 检查元素
        if (theKey < p->element.first)
            p = p->leftChild;
        else
            if (theKey > p->element.first)
                p = p->rightChild;
            else // 找到匹配的元素
                return &p->element;

    // 未找到匹配的元素
    return NULL;
}

1.2.2 插入

　　使用 pp 指针记录 p 指针的双亲节点，p 指针不断查找应该插入的位置

  • p 指针指向空时，说明该插入到该位置。判断插入元素 theKey 和 pp 指针的大小关系插入该元素
  • p 指针找到相同的 theKey 时，更新该节点的 value
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
template<class K, class E>
void binarySearchTree<K, E>::insert(const pair<const K, E>& thePair)
{// 插入thePair节点，如果存在相同的Key则覆盖元素
    binaryTreeNode<pair<const K, E> >* p = root;
    binaryTreeNode<pair<const K, E> >* pp = NULL;

    // 如果循环结束未找到该元素, 则pp元素就是该元素的父节点
    while (p != NULL)
    {// 检查元素p
        pp = p;
        // 将p移动到它的孩子节点
        if (thePair.first < p->element.first)
            p = p->leftChild;
        else
            if (thePair.first > p->element.first)
                p = p->rightChild;
            else
            {// 如果有相同的key, 覆盖旧的值
                p->element.second = thePair.second;
                return;
            }
    }

    // 为thePair创建一个节点, 然后与pp连接
    binaryTreeNode<pair<const K, E> >* newNode = new binaryTreeNode<pair<const K, E> >(thePair);
    if (root != NULL) // 判断树是否是空
        if (thePair.first < pp->element.first)
            pp->leftChild = newNode;
        else
            pp->rightChild = newNode;
    else
        root = newNode; // 直接将节点作为根节点
    treeSize++;
}

1.2.3 删除

　　删除分三种情况

  • 要删除的节点没有孩子节点：如左图所示，这种情况只需要找到该节点释放内存空间，并将双亲节点的右孩子指针置为空即可
  • 要删除的节点只有一个孩子节点：如右图所示，这种情况只需要将该节点内存空间释放，并且将 元素15 的左孩子连接到 元素12 的孩子节点即可
  • 要删除的节点有两个孩子节点，且要更换位置的节点没有孩子节点。我们需要在要删除的节点的左孩子中，向右寻找到最大的元素做替换，将 元素14 重新连接 元素12 和 元素18 构建一个新的树，并重新连接到 元素20 的左孩子位置，最后释放元素14的内存（这种情况实际上转换为构建一棵树，然后删除14，且14没有孩子节点）
  • 要删除的节点有两个孩子节点，且要更换位置的节点有一个孩子节点。我们需要在要删除的节点的左孩子中，向右寻找到最大的元素做替换，将 元素14 重新连接 元素12 和 元素18 构建一个新的树，并重新连接到 元素20 的左孩子的位置，然后把 元素14 的孩子连接到 元素14 的双亲节点处，释放 元素14 的内存空间（这种情况实际上转换为构建一棵树，然后删除14，且14有一个孩子节点）
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
template<class K, class E>
void binarySearchTree<K, E>::erase(const K& theKey)
{// 删除关键字为 theKey 的节点

    // 查找关键字为 theKey 的节点
    binaryTreeNode<pair<const K, E> >* p = root;    // p 是要删除的节点
    binaryTreeNode<pair<const K, E> >* pp = NULL;   // pp 是 p 的双亲
    while (p != NULL && p->element.first != theKey)
    {// p移动到它的孩子节点
        pp = p;
        if (theKey < p->element.first)
            p = p->leftChild;
        else
            p = p->rightChild;
    }
    if (p == NULL)
        return; // 未找到则直接结束

    // 找到一个 s 元素替换要删除的元素 p, 然后用元素 s 构建一棵树
    // 接下来转换为删除元素 s 的操作, s 只有左孩子或者没有孩子
    if (p->leftChild != NULL && p->rightChild != NULL)
    {
        binaryTreeNode<pair<const K, E>>* s = p->leftChild; // s: 在 p 的左孩子中找到最大的元素
        binaryTreeNode<pair<const K, E>>* ps = p;           // ps: s 的双亲
        while (s->rightChild != NULL)
        {
            ps = s;
            s = s->rightChild;
        }

        // 用元素 s 构建一棵树, 替代元素 p 的位置
        binaryTreeNode<pair<const K, E> >* q = new binaryTreeNode<pair<const K, E>> (s->element, p->leftChild, p->rightChild);

        // 如果要删除的没有双亲, 根节点就是 q, 否则把孩子节点更换为 q
        if (pp == NULL) { root = q; }
        else if (p == pp->leftChild) { pp->leftChild = q; }
        else { pp->rightChild = q; }

        // 如果 s 恰好是要删除元素 p 的下一个节点, 单独处理一下
        if (ps == p) { pp = q; }
        else { pp = ps; }

        // 释放元素 p 的空间, 把 p 的指针指向 s, 接下来的工作是删除 s
        delete p;
        p = s;
    }

    // 下面的情况: 元素 p 只有一个孩子或者没有孩子
    // 指针 c 指向了元素 p 的孩子或者 NULL
    binaryTreeNode<pair<const K, E> >* c;
    if (p->leftChild != NULL) { c = p->leftChild; }
    else if (p->leftChild != NULL) { c = p->rightChild; }
    else { c = NULL; }

    // 如果要删除的 p 是根节点
    if (p == root)
        root = c;
    else
    {// 否则将 pp 的孩子置为 p
        if (p == pp->leftChild)
            pp->leftChild = c;
        else pp->rightChild = c;
    }
    treeSize--;
    delete p;
}