T8 红黑树与平衡二叉树区别

• 关于高度
  • AVL 树：严格平衡，任意结点的左右子树高度差不超过 1。
  • 红黑树：相对平衡，任意结点的左右子树黑色高度相同，且不允许连续的红色结点。（一般更高）
• 关于查找效率
  • AVL 树一般比红黑树更好
• 合法性
  • 合法的红黑树不一定是合法的 AVL 树，但合法的 AVL 树一定是合法的红黑树。