二叉树与红黑树基本性质
二叉树与红黑树
1.何为二叉树
1.若任意结点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.若任意结点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.任意结点的左、右子树也分别为二叉查找树。
4.没有键值相等的结点（no duplicate nodes）。
何为红黑树
红黑树是二叉树的进阶，二叉树本来的排序最坏情况下的时间复杂度为O(lgn),但二叉树若退化成了一棵具有n个结点的线性链，那么这个时候最坏情况下他的时间复杂度变为了O(n),而红黑树就是为了让他最坏情况下的时间复杂度为O(lgn).
红黑树的性质
1，每个结点要么是红的，要么是黑的。
2，根结点是黑的。
3，每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。
4，如果一个结点是红的，那么它的俩个儿子都是黑的。
5，对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。