1、汇合中三大数据结构
1.1 数组
内存地址间断
能够通过下标的成员拜访，下标拜访的性能高
增删操作有较大的性能耗费（须要动静扩容）
1.2 链表（双向链表）
灵便的空间要求，存储空间不要求间断
不反对下标拜访，反对程序遍历搜寻
针对增删操作找到对应的节点扭转链表的头尾指针指向即可，无需挪动元数据存储地位
1.3 树（Java 中二叉树个性）
某节点的左子树节点仅蕴含小于该节点的值
某节点的右子树节点仅蕴含大于该节点的值
节点必须是二叉树
顺序排列
存在问题：树能够认为是介于数组和链表二者之间的一种数据结构，领有较快的查问速度同时领有较快的插入和删除速度。然而在树呈现极其或重大的不均衡状况下会导致效率低下
基于红黑树折中解决二叉树不均衡带来的效率低下问题
1.3.1 红黑树
红黑树，Red-Black Tree [RBT]是一个自均衡（不是相对均衡）的二叉查找树（BST）, 树上的每个节点须要遵循上面的规定
每个节点要么是彩色，要么是红色
根节点为彩色
每个叶子节点 (NIL) 是彩色
不能存在两个间断的红色节点（红色节点的两个子节点必须是彩色）
任一节点到叶子节点的门路蕴含雷同数量的黑节点
红黑树通过什么自均衡
左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左节点变为旋转节点的右子节点，左子节点放弃不变
右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点放弃不变
变色：节点的色彩由红色变为彩色或者彩色变为红色
红黑树插入场景
1、红黑树为空
1.1 插入节点作为根节点并把节点设置为彩色
2、插入节点的父节点为黑节点 \
2.1 直接插入
3、插入节点的父节点为红节点
3.1 叔叔节点存在且为红节点
1、P 节点和 S 节点设置为彩色
2、PP 节点设置为红色
3、PP 设置为以后插入节点
4、再次反复上述步骤
3.2 叔叔节点不存在或者叔叔节点为彩色
3.2.1 P 节点是 PP 节点的左节点
3.2.1.1 插入节点是 P 节点的左节点
1、P 设置为彩色
3、PP 节点右旋
3.2.1.2 插入节点是 P 节点的右节点
1、P 节点左旋
2、把 P 设置为插入节点（此时等于下面的场景）
3.2.2 P 节点是 PP 节点的右节点
3.2.2.1 插入节点是 P 节点的右节点
1、P 节点设置为彩色
3、PP 节点左旋
3.2.2.2 插入节点是 P 节点的左节点
1、P 节点右旋
2、将 P 设置为插入节点（此时等于下面场景）
PP 节点左旋
更多材料私信哦，瑞思拜