集合进阶——数据结构
栈
队列
数组（查询快，增删慢）
链表（增删快，查询慢，都需从头找）
树
二叉树——二叉查找树（二叉排序树/二叉搜索树）、二叉平衡树
红黑树（自平衡的二叉查找树），是一种特殊的二叉查找树，但是不是平衡二叉树
——>考虑到旋转机制的繁琐
ArrayList（数组）
LinkList（底层是双链表）
二叉查找树（一样的不存）
前中后序遍历
就是先左后右的基础上，当前结点的前中后
平衡二叉树
任意结点左右子树高度差不超过1
旋转机制
还有旋转两次：
树的演变
正常二叉树只能遍历寻找——> 二叉查找树/排序树/搜索树——>左右子树差异很大，也会降低效率——>平衡二叉树——>旋转效率太低——>红黑树
红黑树
红黑规则
1.根结点和叶结点都是黑
2.两个红色不能相连
3.任意结点到所有后代叶结点的简单路径，黑色结点数相同
默认添加的结点是红色——效率高
