来转存一波二叉搜索树

经验分享区
1

定义

二叉搜索树是一种二叉树的树形数据结构，其定义如下：

  1. 空树是二叉搜索树。
  2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
  3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
  4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 n 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(log \ n)，最坏为 O(n)。随机构造这样一棵二叉搜索树的期望高度为 O(log n)。

过程

二叉搜索树节点的定义

struct TreeNode {
  int key;
  TreeNode* left;
  TreeNode* right;
  // 维护其他信息，如高度，节点数量等
  int size;   // 当前节点为根的子树大小
  int count;  // 当前节点的重复数量

  TreeNode(int value)
      : key(value), size(1), count(1), left(nullptr), right(nullptr) {}
};

遍历二叉搜索树

由二叉搜索树的递归定义可得，二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为 O(n)。

遍历一棵二叉搜索树的代码如下：

void inorderTraversal(TreeNode* root) {
  if (root == nullptr) {
    return;
  }
  inorderTraversal(root->left);
  std::cout << root->key << " ";
  inorderTraversal(root->right);
}

查找最小/最大值

由二叉搜索树的性质可得，二叉搜索树上的最小值为二叉搜索树左链的顶点，最大值为二叉搜索树右链的顶点。时间复杂度为 O(h)。

搜索元素

在以 root 为根节点的二叉搜索树中搜索一个值为 value 的节点。

分类讨论如下：

  • 若 root 为空，返回 false。
  • 若 root 的权值等于 value，返回 true。
  • 若 root 的权值大于 value，在 root 的左子树中继续搜索。
  • 若 root 的权值小于 value，在 root 的右子树中继续搜索。

时间复杂度为 O(h)。

bool search(TreeNode* root, int target) {
  if (root == nullptr) {
    return false;
  }
  if (root->key == target) {
    return true;
  } else if (target < root->key) {
    return search(root->left, target);
  } else {
    return search(root->right, target);
  }
}

插入，删除，修改都需要先在二叉搜索树中进行搜索。

插入一个元素

在以 root 为根节点的二叉搜索树中插入一个值为 value 的节点。

分类讨论如下：

  • 若 root 为空，直接返回一个值为 value 的新节点。
  • 若 root 的权值等于 value，该节点的附加域该值出现的次数自增 [image]。
  • 若 root 的权值大于 value，在 root 的左子树中插入权值为 value 的节点。
  • 若 root 的权值小于 value，在 root 的右子树中插入权值为 value 的节点。

时间复杂度为 O(h)。

TreeNode* insert(TreeNode* root, int value) {
  if (root == nullptr) {
    return new TreeNode(value);
  }
  if (value < root->key) {
    root->left = insert(root->left, value);
  } else if (value > root->key) {
    root->right = insert(root->right, value);
  } else {
    root->count++;  // 节点值相等，增加重复数量
  }
  root->size = root->count + (root->left ? root->left->size : 0) +
               (root->right ? root->right->size : 0);  // 更新节点的子树大小
  return root;
}

删除一个元素

在以 root 为根节点的二叉搜索树中删除一个值为 value 的节点。

先在二叉搜索树中搜索权值为 value 的节点，分类讨论如下：

  • 若该节点的附加 count 大于 [image]，只需要减少 count。
  • 若该节点的附加 count 为 [image]：
    • 若 root 为叶子节点，直接删除该节点即可。
    • 若 root 为链节点，即只有一个儿子的节点，返回这个儿子。
    • 若 count 有两个非空子节点，一般是用它左子树的最大值（左子树最右的节点）或右子树的最小值（右子树最左的节点）代替它，然后将它删除。

时间复杂度 O(h)。

方法使用 root = remove(root, 1) 表示删除根节点为 root 树中值为 1 的节点，并返回新的根节点。

// 此处返回值为删除 value 后的新 root
TreeNode* remove(TreeNode* root, int value) {
  if (root == nullptr) {
    return root;
  }
  if (value < root->key) {
    root->left = remove(root->left, value);
  } else if (value > root->key) {
    root->right = remove(root->right, value);
  } else {
    if (root->count > 1) {
      root->count--;  // 节点重复数量大于1，减少重复数量
    } else {
      if (root->left == nullptr) {
        TreeNode* temp = root->right;
        delete root;
        return temp;
      } else if (root->right == nullptr) {
        TreeNode* temp = root->left;
        delete root;
        return temp;
      } else {
        TreeNode* successor = findMinNode(root->right);
        root->key = successor->key;
        root->count = successor->count;  // 更新重复数量
        // 当 successor->count > 1时，也应该删除该节点，否则
        // 后续的删除只会减少重复数量
        successor->count = 1;
        root->right = remove(root->right, successor->key);
      }
    }
  }
  // 继续维护size，不写成 --root->size;
  // 是因为value可能不在树中，从而可能未发生删除
  root->size = root->count + (root->left ? root->left->size : 0) +
               (root->right ? root->right->size : 0);
  return root;
}

// 此处以右子树的最小值为例
TreeNode* findMinNode(TreeNode* root) {
  while (root->left != nullptr) {
    root = root->left;
  }
  return root;
}

求元素的排名

排名定义为将数组元素升序排序后第一个相同元素之前的数的个数加一。

查找一个元素的排名，首先从根节点跳到这个元素，若向右跳，答案加上左儿子节点个数加当前节点重复的数个数，最后答案加上终点的左儿子子树大小加一。

时间复杂度 [image]。

查找排名为 k 的元素
在一棵子树中，根节点的排名取决于其左子树的大小。
若其左子树的大小大于等于 k，则该元素在左子树中；

若其左子树的大小在区间 [k-\textit{count},k-1] （count 为当前结点的值的出现次数）中，则该元素为子树的根节点；

若其左子树的大小小于 k-\textit{count}，则该元素在右子树中。

时间复杂度 O(h)。

int querykth(TreeNode* root, int k) {
  if (root == nullptr) return -1;  // 或者根据需求返回其他合适的值
  if (root->left) {
    if (root->left->size >= k) return querykth(root->left, k);
    if (root->left->size + root->count >= k) return root->key;
  } else {
    if (k == 1) return root->key;
  }
  return querykth(root->right,
                  k - (root->left ? root->left->size : 0) - root->count);
}

后记

原网页

仅为转存。