二叉排序树、平衡二叉树、红黑树概念
二叉排序树:
1、如果它左子树非空,则左子树上所有元素的值均小于根元素的值
2、如果它右子树非空,则右子树上所有元素的值均大于根元素的值
3、左,右子树本身又各是一棵二叉排序树
平衡二叉树:
一棵二叉树中每个结点的左、右子树的高度至多相差1,则此二叉树为平衡二叉树
(平衡因子:|左子树高度-右子树高度| <= 1 即平衡因子为1、0、-1 )
红黑树:
- 每个结点要么是红的要么是黑的。
- 根结点是黑的。
- 每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。
- 如果一个结点是红的,那么它的两个儿子都是黑的。
- 对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
红黑树的查找、插入、删除的时间复杂度最坏为O(log n)