共计 1002 个字符,预计需要花费 3 分钟才能阅读完成。
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 节点左旋
更多材料私信哦,瑞思拜