上一篇 <<<ConcurrentHashMap在JDK1.8版本比1.7改进了什么
下一篇 >>>基于LinkedHashMap手写LRU淘汰策略
二叉树特点
1、以第一个节点作为根节点，所有小于根节点的数据放置在左边，所有大于等于根节点的数据放置在右边
2、所有左子树和右子树自身必须也是二叉搜索树
3、时间复杂度：2x=n>x=log2n=logn，查找效率：20亿个点 也就是查询231=21
缺点：
不平衡 和时间插入的顺序有关系，如果插入第一个是为0的情况下，最后成为了一条线。时间复杂度其实就是为树的深度，也就是变为O(n)
tips:数据结构连接可访问https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
红黑树与二叉搜索树的实现的区别
二叉搜索树是简单的二叉树，小于根节点的在左子树，大于根节点的在右子树，不会自动调整二叉树的层级，容易出现链表形式，导致查询效率低下。
红黑树属于平衡二叉树的子集，具有颜色，通过变色、左旋、右旋等方式调整二叉树的层级平衡，大大提高查询效率。
红黑树基本特征
1、每个节点的颜色不是红色就是黑色
2、根节点一定为黑色
3、新增节点默认颜色为红色
4、不允许两个红色节点连在一起
5、每个红色节点的两个子节点都必须是黑色
自我修复方式：【变色、左旋、右旋】
网友评论