Gtx CS1332x III Notes

• 通过比较 root 来选择子树：
  • 小于选择左子树
  • 大于选择右子树
• 终结条件：
  • 找到对应的节点
  • reach to an unkown node
• 复杂度：$O(log(n))$，
  • 最坏：degenerated tree → $O(n)$
  • 最好：$O(1)$

• 添加起始点：root
• 进行与 Search 类似的比较
  • 如果存在相同的元素，则终止（BST 不允许重复元素）
  • 如果找不到，则根据与当前子树 root 的比较结果来决定添加元素的位置
  • 元素的位置必然处于某个 leaf node
• 实现方式：
  • looking ahead：通过父节点检查子节点是否为空来判断是否添加元素
  • Point reinforcement：通过返回当前的节点来重新构建 BST
    • 如果遍历左部，那么返回的就是左子节点
    • 如果遍历右部，那么返回的就是右子节点
  • 将返回值通过 pointer 链接起来，形成结果 BST

• wrapper：接口，并对返回的节点进行链接
• helper：搜索目标元素（递归形式）
  • 如果目标元素小于当前节点，则搜索左子树
  • 如果目标元素大于当前节点，则搜索右子树
  • 当前节点为空时，则找到了添加元素的位置，添加元素，并返回该节点用于链接

public void add(T data):
    root <- rAdd(root, data)
private Node rAdd(Node curr, T data):
    //base case
    if curr == null:
        size++
        return new Node(data)
    else if data < curr.data:
        curr.left <- rAAdd(curr.left, data)
    else if data > curr.data:
        curr.right <- rAdd(curr.right, data)
    return curr

参考cs:dsa:courses:gtx_1332x:ii_non_linear#removing_from_a_bst|这里