B树与B+树 B树B树也叫B-树，与二叉树相比，B树其实就是多叉树。 二叉树上，每个节点中只有1个元素，2个子节点，而一棵N阶的B树中，每个节点最多N-1个元素，N个子节点，且B树每条路径的高度是一样的，最底层的节点称之为叶子节点 如下图就是一个4阶的B 2021-05-25 红黑树 红黑树规则红黑树和平衡二叉树一样，都是一种自平衡的二叉树，且红黑树有它自己的规则： 每个节点都有颜色，红色或黑色 根节点是黑色 叶子节点是黑色，且是NIL 两个红色节点不能相连 每个节点到叶子节点(NIL)的路径上，黑色节点的数量都一样 2021-05-24 平衡二叉树(AVL) 平衡二叉树平衡二叉树英文叫Balanced Binary Tree，简称AVL，是为了解决二叉树搜索树极端情况下退化为线性结构的问题。 如何解决呢？ 在插入或删除元素时，重新调整节点的排列顺序，使每个节点的左右两棵子树的高度相差不超过1 例 2021-05-22 二叉搜索树(BST) 二叉树二叉树是最简单的一种树形结构，每个节点最多有两个分支 二叉搜索树（Binary Search Tree）二叉搜索树，又叫二叉排序树，是一种有序的二叉树，每个节点的左边所有节点的值都比它小，右边所有的值都比它大 二叉搜索树即有链表快速 2021-05-22 栈 栈的数据结构与队列几乎一致，但栈的出栈方向和入栈方向是一致的。 可以把栈想象成一个羽毛球桶，先存入的羽毛球，取的时候肯定是最后取出 2021-05-20 队列 队列可以简单理解为一个排队用的线性结构，内部可以使用数组实现，也可以使用链表结构。 队列的特点是FIFO（先进先出） 队列取数据只能从出口一头取，这个过程叫出队 存放数据只能从另一头存入，这个过程叫入队 2021-05-20 链表 单向链表链表是一种线性结构，每个节点都有一个指针指向下一个节点，多个节点串起来形成了一个链表 单向链表中，查询某个数据时，必须从第一个节点向后遍历，因此查询效率不高。 新增数据时，先找到目标位置，然后修改指针 删除数据也一样，先找到目标 2021-05-20 跳表 跳表原理在单向链表上，要查询一个数据，只能从头开始遍历，时间复杂度为O(n)，那么有办法提高链表的查询速度吗？有，那就是跳表。 使用跳表有个前提，就是单链表本身是有序的 跳表的原理就是在原链表的基础上，每2个节点，创建一个索引，称之为一级索 2021-05-20 基数排序 基数排序也是用了桶排序的思想，使用元素的每一位数字来决定桶的位置，排序过程如下： 代码示例： public class Radix { public static void main(String[] args) { 2021-05-07 桶排序 桶排序流程： 桶排序是将数列拆分放到n个桶中，然后每个桶再对自己内部的元素进行排序（使用其他排序算法），然后再把每个桶内的有序数列合并起来 比如数组[4,2,5,6,1,2,5,6,7]，把13放到第一个桶里，46放到一个桶里，7放到一个桶 2021-04-26 计数排序 计数排序是桶排序思想的一种，适合以下场景： 数值范围小，但数量大，例如给1w个学生的考试成绩进行排序 流程比较简单：用一个计数数组记录每一个数字出现的次数，然后遍历计数数组，按顺序一一填充到新数组中。 举个最简单的例子： 原数组：[0 2021-04-25 快速排序 快速排序的基本步骤： 找出一个基准数（一般选数组第一位即可） 将数组中比基准数大的数移动到它右边 将数组中比基准数小的数移动到它左边 以基准数为界，左右两边的子数组递归执行上述步骤 举一个简单的例子（使用_表示一个空位）： 假设数组有 2021-04-23