红黑树
- 自平衡的二叉查找树 （平衡二叉B树）
- O（logN）查找、增加、删除
- 保证最长路径不超过最短路径的两倍
- 满足以下特性
- 节点是红色或黑色
- 根是黑色
- 叶子节点全是黑色、
- 红色节点的子节点都是黑色
- 红色的父节点都是黑色
- 根节点到叶子节点的所有路径不能有两个连续的红色节点
- 从任一节点到叶子节点的所有路径都包含相同数目的黑色节点（红黑树的真正节点为空节点!）
红黑树的效率
- 时间复杂度O（logN）
- 插入效率比平衡二叉树搞
- 插入和删除效率稍低
红黑树的旋转操作
进程和线程的区别-
- 本质区别
- 进程是 资源分配 的基本单位
- 线程是 CPU调度 的基本单位
- 并发性 —— 切换效率
- 进程切换效率满， 线程的切换效率高
- 进程的上下文切换需要保存现场运行环境
- CPU 寄存器
- 程序计数器
- 用户空间的信息
- 内核空间 pcb
- 线程的切换
- 如果是不同进程的线程切换，则和进程切换一样
- 如果是相同进程的线程切换，只需保存CPU寄存器和程序计数器
- 内存
- 进程有独立的虚拟地址空间
- 线程没有独立的地址空间，但是有栈，PC，本地存储等独立空间
- 所属关系