Tree相关概念及特点总结

平衡：树的左右子树的高度差距在一个可控的范围内

1. B-TREE
   多路搜索树
2. AVL
   平衡二叉树:
   空树或它的左右两个子树的高度差的绝对值不超过 1，左右两个子树都是一颗平衡二叉树。
3. RB-TREE
   红黑树:
   红黑树属于平衡二叉树，但不是严格的平衡二叉树，相对接近平衡的二叉树，
   最大深度 <= 最小深度的两倍 (即没有一条路径比其他路径长出两倍)
4. BST
   二叉搜索树 (Binary Search Tree):
5. BBST
   平衡二叉排序树 (Balance Binary Sort Tree)

红黑树概念:

红黑树特点:

红黑树应用场景:

• TreeMap
  基于红黑树实现的排序 Map，默认按 key(实现 comparable 接口) 来比较排序。
  TreeMap 的增删查改以及统计操作的时间复杂度都为 O(logn)
• TreeSet
• JDK1.8 中
  HashMap 每个数组节点挂的元素个数超过 8
  ConcurrentHashMap 每个数组节点挂的元素个数超过 8

红黑树与 AVL 树对比:

• 红黑树的查询性能略逊色于 AVL 树
  红黑树放弃了追求完全平衡，追求大致平衡，
  红黑树的高度相对更高，因此
• 红黑树的插入和删除性能比 AVL 效率高