What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/19 07:19] – [Definition of Unbalanced] codingharecs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/25 11:27] (当前版本) – [Introduction to AVLs] codinghare
行 55: 行 55:
   * AVL 属于自平衡（self-balancing）BST，通过自平衡避免 BST 最坏情况带来的 $O(n)$ 复杂度   * AVL 属于自平衡（self-balancing）BST，通过自平衡避免 BST 最坏情况带来的 $O(n)$ 复杂度
   * AVL 通过 //balance factor(BF)// 来决定当前 BST 中的节点哪些是非平衡的（//unbalanced//）。该因子存储于 node 中   * AVL 通过 //balance factor(BF)// 来决定当前 BST 中的节点哪些是非平衡的（//unbalanced//）。该因子存储于 node 中
-  * //BF// 的计算公式为：''height(leftChild) - height(rightChild)''+  * //BF// 的计算公式为：''height(leftChild) - height(rightChild)''，height 指<wrap em>子树高度</wrap>
     * 子节点不存在时的 height (''height(null)'')会被视作 ''-1''     * 子节点不存在时的 height (''height(null)'')会被视作 ''-1''
   * 树的更新只会影响到从被改变节点到 root 路径上的所有节点   * 树的更新只会影响到从被改变节点到 root 路径上的所有节点
行 61: 行 61:
     * 父节点有左节点称为 //left-heavy//，有右节点称为 //right-heavy//     * 父节点有左节点称为 //left-heavy//，有右节点称为 //right-heavy//
     * //BF// **大于** 0 时为 //left-heavy//, **小于** 0 时为 //right-heavy//     * //BF// **大于** 0 时为 //left-heavy//, **小于** 0 时为 //right-heavy//
 + 
 ==Definition of Unbalanced== ==Definition of Unbalanced==
   * Unbalanced：''|BF| > 1''   * Unbalanced：''|BF| > 1''
   * blalanced：''BF = -1, 0, 1''   * blalanced：''BF = -1, 0, 1''
 ===AVL Rotations=== ===AVL Rotations===
  • 最后更改: 2024/04/25 11:27
  • ©2022 YGwiki.com