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

这是本文档旧的修订版！

AVL and 2-4 Trees, Divide and Conquer Algorithms

Gtx CS1332x III Notes

AVLs

BST Review

BST Search

通过比较 root 来选择子树：
- 小于选择左子树
- 大于选择右子树
终结条件：
- 找到对应的节点
- reach to an unkown node
复杂度：$O(log(n))$，
- 最坏：degenerated tree → $O(n)$
- 最好：$O(1)$