BST,AVL树,红黑树

HASHMAP或者TREEMAP 使用红黑树原因

用红黑树不BST    BST极限会退化为链表

不用AVL树  条件太严格   红黑树的跑平衡条件宽松&＃xff0c;节点操作变动比较小&＃xff0c;写性能比较高

BST

AVL树

AVL树调整平衡

红黑树 

红黑树 O(logn)

1&＃xff09;每个结点要么是红的&＃xff0c;要么是黑的。
2&＃xff09;根结点是黑的。
3&＃xff09;每个叶结点&＃xff0c;即空结点&＃xff08;NIL&＃xff09;是黑的。
4&＃xff09;如果一个结点是红的&＃xff0c;那么它的俩个儿子都是黑的。
5&＃xff09;对每个结点&＃xff0c;从该结点到其子孙结点的所有路径上包含相同数目的黑结点。