本 Wiki 开启了 HTTPS。但由于同 IP 的 Blog 也开启了 HTTPS，因此本站必须要支持 SNI 的浏览器才能浏览。为了兼容一部分浏览器，本站保留了 HTTP 作为兼容。如果您的浏览器支持 SNI，请尽量通过 HTTPS 访问本站，谢谢！
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录前一修订版后一修订版 | 前一修订版 | ||
| cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/14 13:50] – [BST Search] codinghare | cs:dsa:courses:gtx_1332x:iii_avl:start [2024/04/25 11:27] (当前版本) – [Introduction to AVLs] codinghare | ||
|---|---|---|---|
| 行 15: | 行 15: | ||
| * 最好：$O(1)$ | * 最好：$O(1)$ | ||
| ==BST Add== | ==BST Add== | ||
| - | * 实现方式：// | + | * 添加起始点：root |
| + | * 进行与 Search 类似的比较 | ||
| + | * 如果存在相同的元素，则终止（BST 不允许重复元素） | ||
| + | * 如果找不到，则根据与当前子树 root 的比较结果来决定添加元素的位置 | ||
| + | * 元素的位置必然处于某个 leaf node | ||
| + | * 实现方式： | ||
| + | * //looking ahead// | ||
| + | | ||
| + | * 如果遍历左部，那么返回的就是左子节点 | ||
| + | * 如果遍历右部，那么返回的就是右子节点 | ||
| + | * 将返回值通过 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, | ||
| + | else if data > curr.data: | ||
| + | curr.right <- rAdd(curr.right, | ||
| + | return curr | ||
| + | </ | ||
| + | <WRAP center round box 100%> | ||
| + | 注意条件中并没有 '' | ||
| + | </ | ||
| + | ==BST Remove== | ||
| + | 参考[[cs: | ||
| + | ===Introduction to AVLs=== | ||
| + | * AVL 树属于 BST子集，特性继承 BST | ||
| + | * AVL 属于自平衡（self-balancing）BST，通过自平衡避免 BST 最坏情况带来的 $O(n)$ 复杂度 | ||
| + | * AVL 通过 //balance factor(BF)// | ||
| + | * //BF// 的计算公式为：'' | ||
| + | * 子节点不存在时的 height ('' | ||
| + | * 树的更新只会影响到从被改变节点到 root 路径上的所有节点 | ||
| + | * //BF// 的值对树节点的反应： | ||
| + | * 父节点有左节点称为 // | ||
| + | * //BF// **大于** 0 时为 // | ||
| + | |||
| + | ==Definition of Unbalanced== | ||
| + | * Unbalanced：'' | ||
| + | * blalanced：'' | ||
| + | ===AVL Rotations=== | ||