What & How & Why

您在这里: start » cs » dsa » courses » gtx_1332x » iii_avl

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/14 13:49] – [BST Review] codingharecs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/25 11:27] (当前版本) – [Introduction to AVLs] codinghare
行 12: 行 12:
     * reach to an unkown node     * reach to an unkown node
   * 复杂度：$O(log(n))$，   * 复杂度：$O(log(n))$，
-    * 最坏：degernated tree -> $O(n)$+    * 最坏：degenerated tree -> $O(n)$
     * 最好：$O(1)$     * 最好：$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===
  • 最后更改: 2024/04/14 13:49
  • ©2022 YGwiki.com