红黑树 红黑树规则红黑树和平衡二叉树一样，都是一种自平衡的二叉树，且红黑树有它自己的规则： 每个节点都有颜色，红色或黑色 根节点是黑色 叶子节点是黑色，且是NIL 两个红色节点不能相连 每个节点到叶子节点(NIL)的路径上，黑色节点的数量都一样 数据结构与算法 数据结构 红黑树 平衡二叉树(AVL) 平衡二叉树平衡二叉树英文叫Balanced Binary Tree，简称AVL，是为了解决二叉树搜索树极端情况下退化为线性结构的问题。 如何解决呢？ 在插入或删除元素时，重新调整节点的排列顺序，使每个节点的左右两棵子树的高度相差不超过1 例 数据结构与算法 数据结构 平衡二叉树 二叉搜索树(BST) 二叉树二叉树是最简单的一种树形结构，每个节点最多有两个分支 二叉搜索树（Binary Search Tree）二叉搜索树，又叫二叉排序树，是一种有序的二叉树，每个节点的左边所有节点的值都比它小，右边所有的值都比它大 二叉搜索树即有链表快速 数据结构与算法 数据结构 二叉搜索树 栈 栈的数据结构与队列几乎一致，但栈的出栈方向和入栈方向是一致的。 可以把栈想象成一个羽毛球桶，先存入的羽毛球，取的时候肯定是最后取出 数据结构与算法 数据结构 栈 队列 队列可以简单理解为一个排队用的线性结构，内部可以使用数组实现，也可以使用链表结构。 队列的特点是FIFO（先进先出） 队列取数据只能从出口一头取，这个过程叫出队 存放数据只能从另一头存入，这个过程叫入队 数据结构与算法 数据结构 队列 跳表 跳表原理在单向链表上，要查询一个数据，只能从头开始遍历，时间复杂度为O(n)，那么有办法提高链表的查询速度吗？有，那就是跳表。 使用跳表有个前提，就是单链表本身是有序的 跳表的原理就是在原链表的基础上，每2个节点，创建一个索引，称之为一级索 数据结构与算法 数据结构 跳表 链表 单向链表链表是一种线性结构，每个节点都有一个指针指向下一个节点，多个节点串起来形成了一个链表 单向链表中，查询某个数据时，必须从第一个节点向后遍历，因此查询效率不高。 新增数据时，先找到目标位置，然后修改指针 删除数据也一样，先找到目标 数据结构与算法 数据结构 链表 基数排序 基数排序也是用了桶排序的思想，使用元素的每一位数字来决定桶的位置，排序过程如下： 代码示例： public class Radix { public static void main(String[] args) { 数据结构与算法 算法 排序 基数排序 桶排序 桶排序流程： 桶排序是将数列拆分放到n个桶中，然后每个桶再对自己内部的元素进行排序（使用其他排序算法），然后再把每个桶内的有序数列合并起来 比如数组[4,2,5,6,1,2,5,6,7]，把13放到第一个桶里，46放到一个桶里，7放到一个桶 数据结构与算法 算法 排序 桶排序 计数排序 计数排序是桶排序思想的一种，适合以下场景： 数值范围小，但数量大，例如给1w个学生的考试成绩进行排序 流程比较简单：用一个计数数组记录每一个数字出现的次数，然后遍历计数数组，按顺序一一填充到新数组中。 举个最简单的例子： 原数组：[0 数据结构与算法 算法 排序 计数排序 快速排序 快速排序的基本步骤： 找出一个基准数（一般选数组第一位即可） 将数组中比基准数大的数移动到它右边 将数组中比基准数小的数移动到它左边 以基准数为界，左右两边的子数组递归执行上述步骤 举一个简单的例子（使用_表示一个空位）： 假设数组有 数据结构与算法 算法 排序 快速排序 归并排序 归并排序流程： 归并排序的基本思想是先将数组拆分后排序，再进行合并 例如一个数组[5,2,3,9]，拆分后示意图如下： 然后再进行合并，并且合并的过程中进行了排序： 所以，拆分与合并很好理解，关键在于合并的过程中，如何进行排序。 例如2 数据结构与算法 算法 排序 归并排序 插入排序 插入排序是将数据插入到已经排好序的数列中 插入排序流程： 先看动画： 流程如下： 初始状态，数组第一位就是一个排好序的数列 遍历后面的元素，一一插入到前面已经排好序的队列中 代码示例： public class Insert { 数据结构与算法 算法 排序 插入排序 选择排序 选择排序流程： 先看动画示意： 流程如下： 假设数组长度n，从左开始遍历数组，找出数组中的最小值与其下标 第一轮遍历完，就找出了数组的最小值，将其与数组第一位互换位置 数组的最小值就移动到了第一位 第二轮，从数组第二位开始遍历，重复上述 数据结构与算法 算法 排序 选择排序 冒泡排序 冒泡排序流程： 先看动画示意： 流程如下： 假设数组长度n，从左开始遍历数组，每两个进行比大小 例如array[0]和array[1]比大小，如果array[0]大，则和array[1]交换位置 同理依次比较array[1]和array 数据结构与算法 冒泡排序 算法 排序 MySQL主从复制 主从复制原理MySQL利用binlog实现主从复制，大致流程如下： 主节点每一次执行SQL都会写binlog日志 从节点IO线程与主节点建立起长连接，不断的从主节点读取binlog IO线程将读到的binlog写到replay log中 MySQL全解 MySQL MySQL中的RedoLog和Binlog MySQL通过redolog保证崩溃时数据不丢失，使用binlog归档数据 MySQL全解 MySQL MySQL数据与索引 MySQL数据相信很多人一定很好奇MySQL中，数据到底是怎么存储的，为什么查询可以这么快？ 这里我先给出一个结论： MySQL InnoDB中，表数据是以索引的形式存储的 没错，表数据是以索引的形式存储到硬盘上的，当你新建了一张表，即 MySQL全解 MySQL MySQL事务如何回滚 MySQL事务可以保证所有操作要么都成功，要么都失败，那么失败时，事务是如何回滚的呢？ MySQL全解 MySQL MySQL事务 事务是数据库知识体系中极为重要的一环 MySQL全解 MySQL