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节点左旋
更多材料私信哦，瑞思拜