平衡二叉树

平衡二叉树

定义

  1. 左右子树的高度之差的绝对值不超过1
  2. 左右子树都是平衡二叉树

可以自平衡的二叉搜索树,使得每次查找一个值的复杂度都是$O(log_2n)$

具体实现有: 红黑树, AVL, Treap, Splay, SBT, kd-tree.

Zig

顺时针旋转

Zag

逆时针旋转

AVL

平衡因子(balance factor):当前节点左子树高度与右子树高度的差

限制条件: 其中各节点平衡因子的绝对值均不超过1

一般规定:空树高度取-1,单节点子树(叶节点)高度取0.

###

Thank you for your support!