共计 468 个字符，预计需要花费 2 分钟才能阅读完成。
平衡：树的左右子树的高度差距在一个可控的范围内
- B-TREE
多路搜索树 - AVL
平衡二叉树:
空树或它的左右两个子树的高度差的绝对值不超过 1，左右两个子树都是一颗平衡二叉树。 - RB-TREE
红黑树:
红黑树属于平衡二叉树，但不是严格的平衡二叉树，相对接近平衡的二叉树，
最大深度 <= 最小深度的两倍 (即没有一条路径比其他路径长出两倍) - BST
二叉搜索树 (Binary Search Tree): - BBST
平衡二叉排序树 (Balance Binary Sort Tree)
红黑树概念:
红黑树特点:
红黑树应用场景:
- TreeMap
基于红黑树实现的排序 Map，默认按 key(实现 comparable 接口) 来比较排序。
TreeMap 的增删查改以及统计操作的时间复杂度都为 O(logn) - TreeSet
- JDK1.8 中
HashMap 每个数组节点挂的元素个数超过 8
ConcurrentHashMap 每个数组节点挂的元素个数超过 8
红黑树与 AVL 树对比:
- 红黑树的查询性能略逊色于 AVL 树
红黑树放弃了追求完全平衡，追求大致平衡，
红黑树的高度相对更高，因此 - 红黑树的插入和删除性能比 AVL 效率高
正文完
