树结构第二部分

二分查找树（Binary Search Tree）

• 无重复元素
• 从左到右依次增大

寻找操作（Find）

核心想法是一直比较左右节点，然后向下查找，或赋值或递归

• 找最小

  BinaryNode<Comparable>* findMin(BinaryNode<Comparable>* t) const {
    if (t == nullptr)
        return nullptr;
    if (t->left == nullptr)
        return t;
    return findMin(t->left);
  }
  

• 找最大
• 找任意一个

  bool contains(const Comparable& x, BinaryNode<Comparable>* t) const
  {
    if (t == nullptr) return false;
    else if (x < t->element)
        return contains(x, t->left);
    else if (t->element < x)
        return contains(x, t->right);
    else
        return true;
  }
  

  时间复杂度都是 $O(h)$ 。

插入（Insert）

插入节点只插在叶子节点后

void insert(const Comparable& x, BinaryNode<Comparable>*& t) { if (t == nullptr) t = new BinaryNode<Comparable>(x, nullptr, nullptr); else if (x < t->element) insert(x, t->left); else if (t->element < x) insert(x, t->right); else ; }

移除（Erase）

分为三种情况：

• 叶子节点 delete 然后其父节点的相应子节点设为 nullptr
• 该节点有一个子节点 子节点接到父节点，删除该节点
• 该节点有两个子节点（Full Node） 选左子树最大/右子树最小，替换该节点，删除该节点（可能会用到前两种情况）

要对原树进行操作，需要传入引用

void remove(const Comparable& x, BinaryNode<Comparable>*& t) {
    if (t == nullptr)
        return; // Item not found; do nothing
    if (x < t->element)
        remove(x, t->left);
    else if (t->element < x)
        remove(x, t->right);
    else if (t->left != nullptr && t->right != nullptr) // Two children
    {
        t->element = findMin(t->right)->element;
        remove(t->element, t->right);
    }
    else
    {
        BinaryNode<Comparable>* oldNode = t;
        t = (t->left != nullptr) ? t->left : t->right;
        delete oldNode;
    }
}

前一个小的/后一个大的（Previous Smaller/Next largest）

Next largest：

• 如果有右子树，那么就是右子树的最小值（一直往左找）
• 没有右子树？
• 找前一个？ 找到第k个元素，k从0开始，P66

时间复杂度分析

• 最坏的情况是 $O(n)$ ,这个BST变成一个链表
• 最好的情况，PerfectBST，$O(ln(n))$
• 我们的目标是让这个树的高度维持在 $\Theta(ln(n))$ .

71