AVL and 2-4 Trees, Divide and Conquer Algorithms

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

参考这里

• AVL 树属于 BST子集，特性继承 BST
• AVL 属于自平衡（self-balancing）BST，通过自平衡避免 BST 最坏情况带来的 $O(n)$ 复杂度
• AVL 通过 balance factor(BF) 来决定当前 BST 中的节点哪些是非平衡的（unbalanced）。该因子存储于 node 中
• BF 的计算公式为：height(leftChild) - height(rightChild)，height 指子树高度
  • 子节点不存在时的 height (height(null))会被视作 -1
• 树的更新只会影响到从被改变节点到 root 路径上的所有节点
• BF 的值对树节点的反应：
  • 父节点有左节点称为 left-heavy，有右节点称为 right-heavy
  • BF 大于 0 时为 left-heavy, 小于 0 时为 right-heavy

• Unbalanced：|BF| > 1
• blalanced：BF = -1, 0, 1