二叉搜索树

二叉搜索树 (Binary Search tree)

查找问题

查找问题是计算机中非常重要的基础问题.

二分查找法

首先需要注意的是, 对于有序数列, 才能使用二分查找法.

基本思想

image

选取数组中间的元素 v, 与我们想要查找的元素 item 相比较, 有三种情况:

• 如果 v == item, 那么结束查找, 返回 v 的位置.
• 如果 item > v, 那么在右半区域内查找.
• 如果 item < v, 那么在左半区域内查找.

代码实现

// 二分查找法, 在有序数组 arr 中, 查找 target
// 如果找到 target, 返回相应的索引 index
// 如果没有找到 target, 返回 -1
template<typename T>
int binarySearch(T arr[], int n, T target) {
    // 在 arr[l...r] 之间查找 target
    int l = 0, r = n - 1;
    while (l <= r) {
        // 可能会有溢出 bug
        // int mid = (l + r) / 2;
        int mid = l + (r - l) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (target < arr[mid]) {
            // 这里需要注意, 是 mid - 1, 而不是 mid.
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    // 如果结束循环还没有找到 target, 则返回 -1.
    return -1;
}

floor 和 ceil

对于一个在数组中存在相同元素的情况, 上面的二分查找不一定能保证我们查找到的元素在数组中出现的位置.

• floor 函数查找数组中第一次出现的元素.
• ceil 函数查找数组中最后一次出现的元素.

image

同时, 在实现时, 如果查找的元素不存在, 返回值应该是如下情况, 如果查找 42, floor 函数返回最后一个 41 元素, ceil 函数返回第一个 43 的位置.

image

二分搜索树

二分搜索树用于实现字典数据结构, 通过 key 查找到对应的 value 值. 可以高效的实现查找, 插入, 删除等操作.

二分搜索树的定义

• 二叉树
• 每个节点的键值大于左孩子
• 每个节点的键值小于右孩子
• 以左右孩子为根的两个子树仍为二分搜索树

注意:

• 二分搜索树不一定是完全二叉树
• 因此不能直接用数组来表示二分搜索树

二分搜索树可以缩写为 (Binary Search Tree, BST)

二分搜索树的基本框架实现

Node 节点的实现

一个二分搜索树的基本单元不再使用简单的数据类型, 可以使用一个结构体来实现.

// Key and Value are generic type
struct Node {
    Key key;
    Value value;
    Node *left;
    Node *right;
    
    Node(Key key, Value value) {
        this->key = key;
        this->value = value;
        this->left = NULL;
        this->right = NULL;
    }
}

BST 类的基本框架

使用上面 Node 节点的构建, 我们构建一个基本的 BST 类.

template<typename Key, typename Value>
class BST {
private:
    struct Node {
        Key key;
        Value value;
        Node *left;
        Node *right;

        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = NULL;
            this->right = NULL;
        }
    };

    Node *root;
    int count;

public:
    BST() {
        root = NULL;
        count = 0;
    }

    ~BST() {
        // TODO: ~BST()
    }

    int size() {
        return count;
    }

    bool isEmpty() {
        return count == 0;
    }
};

该类主要包含的私有成员为根节点以及元素个数 count, 是二叉搜索树的基本架构.

插入新的节点

image

根据二分搜索树的定义可以很容易的得出插入一个新元素的方法.

• 一开始将带插入的元素与根节点的元素进行比较
  • 如果小于该元素, 则将该元素插入以左孩子为根节点的子树中.
  • 如果大于该元素, 则将该元素插入以右孩子为根节点的子树中.
  • 如果等于该元素, 则将该元素的 value 更新.
• 如果对应的子树为空, 则将该元素插入此位置.

是一个简单的递归的思想. 对于树中已经存在了该元素的情况, 只需要更新该元素的值即可.

代码实现

递归实现:

public:
    // 向二叉搜索树中插入新的元素
    void insert(Key key, Value value) {
        root = insert(root, key, value);
    }
private:
    // 向以 node 为根的二叉搜索树中插入节点
    // 返回插入新节点后的二叉搜索树的根
    Node *insert(Node node, Key key, Value value) {
        if (node == NULL) {
            count++;
            return new Node(key, value);
        }
        if (key == node->key) {
            node->value = value;
        } else if (key < node->key) {
            node->left = insert(node->left, key, value);
        } else {
            node->right = insert(node->right, key, value);
        }
        return node;
    }

递归插入过程中, 需要注意的有两点:

• 递归过程中, 被调用的递归函数需要返回一个子树在插入完成后, 新的根, 来作为其父节点的新的孩子节点.
• 递归结束条件为孩子节点为空, 这时我们需要新创建一个 Node, 并注意将 count++.

非递归实现:

// 插入的非递归实现
void insert2(Key key, Value value) {
    if (root == NULL) {
        root = new Node(key, value);
        return;
    }
    Node *node = root;
    while (true) {
        if (node->key == key) {
            // 如果键值已经存在于树中, 更新 value
            // 然后返回
            node->value = value;
            return;
        } else if (key < node->key) {
            // 在左子树中寻找
            if (node->left != NULL) {
                node = node->left;
            } else {
                // 左子树为 NULL
                // 插入元素并返回
                node->left = new Node(key, value);
                return;
            }

        } else if (key > node->key) {
            // 在右子树中寻找
            if (node->right != NULL) {
                node = node->right;
            } else {
                // 右子树为 NULL
                // 插入元素并返回
                node->right = new Node(key, value);
                return;
            }
        }
    }
}

查找节点

查找是否包含 key 的元素

// 查找以 node 为根的子树中是否包含 Key
bool contain(Node *node, Key key) {
    if (node == NULL) {
    return false;
    }
    if (key == node->key) {
    return true;
    } else if (key < node->key) {
    contain(node->left, key);
    } else {
    contain(node->right, key);
    }
}

查找 key 对应的 value 值

对于 search 方法的构建, 对于其返回值, 有以下几种方式:

• Node*: 需要将 Node 实现为 public, 缺点是用户需要了解内部 Node 的实现, 破坏了封装性.
• Value: 直接返回 Value 值, 缺点是无法表示 key 不存在的情况, 用户需要提前进行判断, 可以使用 assert.
• Value*: 返回 Value 的指针.

// 在以 node 为根的子树中查找 key
Value *search(Node *node, Key key) {
    if (node == NULL) {
        return NULL;
    }
    if (key == node->key) {
        return &(node->value);
    } else if (key < node->key) {
        return search(node->left, key);
    } else {
        return search(node->right, key);
    }
}

Demo 测试

下面的代码用于统计一个文件中, 每个单词出现的频次, 存储在一个二分搜索树中.

int main() {
    string filename = "communist.txt";
    vector<string> words;
    if (FileOps::readFile(filename, words)) {
        cout << "There are totally " << words.size() << " words in " << filename << endl;
        cout << endl;
    }

    time_t startTime = clock();
    BST<string, int> bst = BST<string, int>();
    for (string &word : words) {
        int *res = bst.search(word);
        if (res == NULL) {
            bst.insert2(word, 1);
        } else {
            (*res)++;
        }
    }

    // 我们查看unite一词的词频
    string word = "unite";
    if (bst.contain(word))
        cout << word << ": " << *bst.search(word) << endl;
    else
        cout << "No word " << word << " in " + filename << endl;
    time_t endTime = clock();

    cout << "BST , time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " s." << endl;
    cout << endl;

    return 0;
}

二分搜索树的遍历

树的遍历可以分为深度优先遍历和广度优先遍历, 深度优先遍历有前序遍历, 中序遍历和后序遍历三种.

深度优先遍历

• 前序遍历: 先访问当前节点, 再依次递归访问左右子树.
• 中序遍历: 先递归访问左子树, 再访问自身, 再访问自身, 再递归访问右子树.
• 后续遍历: 先递归访问左右子树, 再访问自身节点.

前序遍历

// 对以 node 为根的二叉搜送树进行前序遍历
void preOrder(Node *node) {
    if (node != NULL) {
    cout << node->key << endl;
    preOrder(node->left);
    preOrder(node->right);
    }
}

中序遍历

中序遍历可以用来顺序输出 key.

// 对以 node 为根的二叉搜送树进行前序遍历
void preOrder(Node *node) {
    if (node != NULL) {
        cout << node->key << endl;
        preOrder(node->left);
        preOrder(node->right);
    }
}

后序遍历

在析构函数释放资源时, 可以使用后续遍历的方式.

// 对以 node 为根的二叉搜索树进行中序遍历
void inOrder(Node *node) {
    if (node != NULL) {
        inOrder(node->left);
        cout << node->key << endl;
        inOrder(node->right);
    }
}

广度优先遍历

广度优先遍历可以使用队列的数据结构来完成. 队列的先进先出的性质保证了树是从上层到下层的层序遍历.

1. 将根节点入队.
2. 只要队列不为空, 则出队一个节点, 同时将该节点的孩子节点入队
3. 直到队列为空.

// 层序遍历
void levelOrder() {
    queue<Node *> q;
    q.push(root);
    while (!q.empty()) {
        Node *node = q.front();
        q.pop();
        cout << node->key << endl;
        if (node->left) {
            q.push(node->left);
        }
        if (node->right) {
            q.push(node->right);
        }
    }
}

删除节点

找到最大节点和最小节点

根据二分搜索树的定义, 整棵树的最小节点的寻找方法是从根节点开始, 一直沿着左孩子找, 找到的最后一个节点就是最小节点.

同理, 最大节点是从根节点开始, 沿着右孩子查找, 一直找到最后一个节点就是最大节点.

递归实现:

// 在以 node 为根的二叉搜索树中, 返回最小键值的节点
Node *minimum(Node *node) {
    if (node->left == NULL) {
        return node;
    }
    return minimum(node->left);
}

// 在以 node 为根的二叉搜索树中, 返回最大键值的节点
Node *maximum(Node *node) {
    if (node->right == NULL) {
        return node;
    }
    return minimum(node->right);
}

删除二分搜索树的最小值和最大值

image

以删除最大节点为例, 找到最大节点后, 删除 58, 然后因为其还有左子树, 根据二分搜索树的定义 (左子树仍然是二分搜索树, 并且该子树的元素一定大于 41), 只需要将 58 的左孩子 50 这个节点放在 58 的位置即可.

// 删除以 node 为根的二分搜索树的最小节点
// 返回删除节点后新的二分搜索树的根
Node *removeMin(Node *node) {
    if (node->left == NULL) {
        Node *rightNode = node->right;
        delete node;
        count--;
        return rightNode;
    }
    removeMin(node->left);
}

二分搜索树删除任意节点

上述删除最小节点和最大节点时, 被删除的节点最多只有一个孩子, 在删除之后, 只需要将子树替代自身即可.

如果待删除的节点既有左孩子, 又有右孩子, 我们还是需要找一个节点来代替待删除节点, 这个节点既不是左孩子, 也不是右孩子, 这个节点应该是右子树中的最小值.

image

代码实现:

// 删除掉以 node 为根的二分搜索树中键值为 key 的节点
// 返回删除节点后新的二分搜索树的根
Node *remove(Node *node, Key key) {
    if (node == NULL) {
        return NULL;
    }

    if (key < node->key) {
        node->left = remove(node->left, key);
        return node;
    } else if (key > node->key) {
        node->right = remove(node->right, key);
        return node;
    } else { // key == node->key
        if (node->left == NULL) {
            Node *rightNode = node->right;
            delete node;
            count--;
            return rightNode;
        }
        if (node->right == NULL) {
            Node *leftNode = node->left;
            delete node;
            count--;
            return leftNode;
        }

        // node->left != NULL && node->right != NULL
        Node *successor = new Node(minimum(node->right));
        count++;

        successor->right = removeMin(node->right);
        successor->left = node->left;

        delete node;
        count--;

        return successor;
    }
}

二分搜索树的其他问题

• ceil 和 floor
• rank 和 select
• 平衡二叉树 (红黑树)
• treap
• trie

树形问题

• 归并排序
• 递归问题
• 搜索问题
• 决策树 (递归求解)