差别

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

--- cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/14 14:16] – [BST Remove] codinghare
+++ cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/25 11:27] (当前版本) – [Introduction to AVLs] codinghare
@@ 行 50: / 行 50: @@
 </WRAP>
 ==BST Remove==
-参考[[cs:dsa:courses:gtx_1332x:|cs:dsa:courses:gtx_1332x:ii_non_linear#removing_from_a_bst|这里]]
+参考[[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===

What & How & Why