======AVL and 2-4 Trees, Divide and Conquer Algorithms======
//Gtx CS1332x III Notes//
----
====AVLs====
===BST Review===
==BST Search==
  * 通过比较 root 来选择子树：
    * 小于选择左子树
    * 大于选择右子树
  * 终结条件：
    * 找到对应的节点
    * reach to an unkown node
  * 复杂度：$O(log(n))$，
    * 最坏：degenerated tree -> $O(n)$
    * 最好：$O(1)$
==BST Add==
  * 添加起始点：root
  * 进行与 Search 类似的比较
    * 如果存在相同的元素，则终止（BST 不允许重复元素）
    * 如果找不到，则根据与当前子树 root 的比较结果来决定添加元素的位置
    * 元素的位置必然处于某个 leaf node
   * 实现方式：
     * //looking ahead//：通过父节点检查子节点是否为空来判断是否添加元素
     * //Point reinforcement//：通过返回当前的节点来重新构建 BST
       * 如果遍历左部，那么返回的就是左子节点
       * 如果遍历右部，那么返回的就是右子节点
     * 将返回值通过 pointer 链接起来，形成结果 BST
==Add 的实现==
  * wrapper：接口，并**对返回的节点进行链接**
  * helper：搜索目标元素（递归形式）
    * 如果目标元素小于当前节点，则搜索左子树
    * 如果目标元素大于当前节点，则搜索右子树
    * 当前节点为空时，则找到了添加元素的位置，添加元素，并**返回**该节点用于链接
<code java>
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
</code>
<WRAP center round box 100%>
注意条件中并没有 ''==''，这种情况下，如果有重复的元素，那么会直接返回该重复的元素，并链接到其父节点上。这不会改变任何 BST 中已有的内容。
</WRAP>
==BST Remove==
参考[[cs:dsa:courses:gtx_1332x:ii_non_linear:start#removing_from_a_bst|这里]]
===Introduction to AVLs===
  * AVL 树属于 BST子集，特性继承 BST
  * AVL 属于自平衡（self-balancing）BST，通过自平衡避免 BST 最坏情况带来的 $O(n)$ 复杂度
  * AVL 通过 //balance factor(BF)// 来决定当前 BST 中的节点哪些是非平衡的（//unbalanced//）。该因子存储于 node 中
  * //BF// 的计算公式为：''height(leftChild) - height(rightChild)''，height 指<wrap em>子树高度</wrap>
    * 子节点不存在时的 height (''height(null)'')会被视作 ''-1''
  * 树的更新只会影响到从被改变节点到 root 路径上的所有节点
  * //BF// 的值对树节点的反应：
    * 父节点有左节点称为 //left-heavy//，有右节点称为 //right-heavy//
    * //BF// **大于** 0 时为 //left-heavy//, **小于** 0 时为 //right-heavy//
 
==Definition of Unbalanced==
  * Unbalanced：''|BF| > 1''
  * blalanced：''BF = -1, 0, 1''
===AVL Rotations===