标签：BST zag 二叉 失衡 zig 搜索 logn
- 任一节点均不小于/不大于其左/右后代
- BST的中序遍历序列，必然单调非降
- BST的查找：减而治之 O（h）。
- BST的插入：O（h）。
- BST的删除：O（h）。
- BST的等价转化都可以视作是一系列的旋转而成 zig/zag 顺时针/逆时针
- 适度平衡 任一节点 左子树右子树高度绝对值之差 小于 2
- height(AVL) = O(logn)。
- 失衡 ：加入某个节点可能会导致很多祖先失衡，摘除一个节点只可能会导致父节点失衡，删除失衡恢复较为复杂。
- 插入恢复O(1)：单旋 （zig-zig zag-zag）；双旋（zig-zag zag-zig）。
- 删除恢复：局部恢复，更高祖先仍可能失衡，存在失衡传播现象，可能需要做O(logn)次调整。单旋或双旋调整。
- 旋转调整只是方便理解，实际调整可以直接拼接局部（类似拼接魔方），更加高效。“3+4”重构。
- 优点：AVL树无论查找，插入，删除，最坏情况下的复杂度均为O(logn)，O(n)的存储空间。
- 缺点：1 借助平衡因子，需要对元素结构做额外封装 2 实际复杂度与理论值尚有差异 3 单次动态调整后，全树拓扑结构的变化量可能高达 omiga(logn)。
标签：BST,
zag,
二叉,
失衡,
zig,
搜索,
logn
From： https://www.cnblogs.com/wuyun--wy/p/17237836.html