What & How & Why

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录前一修订版
后一修订版		前一修订版
cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/14 14:05] – [BST Add] codingharecs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/25 11:27] (当前版本) – [Introduction to AVLs] codinghare
行 31: 行 31:
     * 如果目标元素小于当前节点，则搜索左子树     * 如果目标元素小于当前节点，则搜索左子树
     * 如果目标元素大于当前节点，则搜索右子树     * 如果目标元素大于当前节点，则搜索右子树
-    * 当前节点为空时，则找到了添加元素的位置+    * 当前节点为空时，则找到了添加元素的位置，添加元素，并**返回**该节点用于链接
 <code java> <code java>
 public void add(T data): public void add(T data):
     root <- rAdd(root, data)     root <- rAdd(root, data)
 private Node rAdd(Node curr, T data): private Node rAdd(Node curr, T data):
 +    //base case
     if curr == null:     if curr == null:
         size++         size++
行 45: 行 46:
     return curr     return curr
 </code> </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 14:05
  • ©2022 YGwiki.com