0901（044天 集合框架08 树TreeMap）
0901（044天 集合框架08 树TreeMap）
每日一狗（旺名）
集合框架08 树TreeMap
文章目录
- 0901（044天 集合框架08 树TreeMap）
- 集合框架08 树TreeMap
- 1. 树
- 1.1 二叉搜索树
- 二叉树的特点
- 插入数据
- 平衡二叉树
- 1.2 红黑树：
- 问：特殊方法
- 问：HashMap和TreeMap的综合使用
- 1.3 总结：HashMap、TreeMap和Hashtable
- 不同点
- 1.4 二级标题
- 2. TreeMap
- 2.1 源码
- 2.2 二级标题
- 2.3 二级标题
- 2.4 二级标题
- 3. 一级标题
- 3.1 二级标题
- 3.2 二级标题
- 3.3 二级标题
- 3.4 二级标题
- 扩展小芝士
- 模板备份开始
- 4. 一级标题
- 4.1 二级标题
- 4.2 二级标题
- 4.3 二级标题
- 4.4 二级标题
- 模板备份结束
1. 树
满二叉树：全都满了，只有度为0/2的节点，2^k-1
完全二叉树：除了最后一层其它层是一个满二叉树，最后一层从左往右插入
1.1 二叉搜索树
二叉搜索树BST：
定义：一个二叉树中，任意节点的值要大于等于左子树所有节点的值（左节点最小）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AcaR3aLd-1662039594447)(assets/image-20220901160554728.png)]
引入原因：为了解决双向链表的递归检索问题。
二叉树的特点
- 左 小 右 大
- 左 > 根 > 右
插入数据
平衡二叉树
二叉树在极端情况下会退化为单向链表，在此之内引入了平衡树的概念，左右子树的高度差最大为1，然后左右子树也都是一个平衡二叉树。
使用左旋右旋算法解决二叉树的不平衡问题。
1.2 红黑树：
一种近似平衡的二叉树，插入删除插入都快。
为了减少左旋右旋的代价，提出了红黑树
问：红黑树的概念
- 节点不是红就是黑
- 根节点永远是黑的
- 叶子到根节点不能有连续两个红节点
- 补全的节点到根节点的黑节点数量相同
问：特殊方法
获取特殊节点的特殊方法
- 获取第一个节点
- 获取一个比指定key节点紧邻大一点的一个节点
- 获取一个比指定key节点紧邻小一点的一个节点
问：HashMap和TreeMap的综合使用
一般就直接先用HashMap，当你需要全局顺序时在转换成TreeMap进行使用。
1.3 总结：HashMap、TreeMap和Hashtable
不同点
- 元素特性：
- 顺序特性：
- 初始化和增长方式：
- 线程安全：
1.4 二级标题
2. TreeMap
根据红黑树进行实现，与哈希算法无关
2.1 源码
构造器中可以传入一个比较器，无参就没有比较器
2.2 二级标题
2.3 二级标题
2.4 二级标题
3. 一级标题
3.1 二级标题
3.2 二级标题
3.3 二级标题
3.4 二级标题
扩展小芝士
- 看源码的时候先看构造器，就可以找到一些比较重要的属性