月守护的博客

数组 在golang中已经封装成了高级结构，array和slice 数组在内存中是一片连续的空间，每一个元素都有自己的索引对应 数组因为索引的存在，所以查找和更新的时间复杂度都是O（1）的 因为连续内存，中间不能断，所以增加和删除都可能涉及到所有元素的移动所以时间复杂度是O（n）的 数组常常和链表来比较，因为两者的优势是互补的，即链表元素的增加，删除是O（1）的，但查找是O（n）的。 链表 在golang中没有提供现成的高级结构 链表在内存中是随机存储的，可以有效利用零散的碎片空间，每一个节点通过指针相

思路一：借用新的单链表 新建一个新的单向链表，从头循环处理旧链表节点，依次插入到新单向链表的头节点，最后用新单向链表的头节点替换旧单向链表的头节点 package main import ( "fmt" ) // 链表 type LinkList struct { HeadNode *LinkNode } //单向链表节点 type LinkNode struct { Data int32 // 链表上的数据 Next *LinkNode // 指针指向下一个数据 } // 在头部添加数据,

上一篇博客讲了数组和链表，它们有一个很大的区别就是在内存中的存在方式是不同的。数组是连续的，链表是零散的。这种在内存中的存在形式又被称为物理结构。数组是顺序存储结构，链表是链式存储结构。除了物理结构之外，还有一个叫做逻辑结构，分为线性结构（顺序表，栈，队列）和非线性结构（树，图）。 之所以叫做逻辑结构是因为我们不关心它在内存的存储形式，可能是顺序存储，也可能是链式存储。我们只关心数据结构本身的特性 比如栈和队列的物理实现既可以用数组实现，也能用链表实现。 这里我们只关心栈和队形本身的逻辑特性，即栈是先进后出

package main import ( "errors" "fmt" "strconv" ) // 循环队列实现方法 type loopQueue struct { queues []interface{} front int //队首 tail int //队尾 length int //队伍长度 capacity int //队伍容量 } // 创建循环队列，可指定容量，默认为0 func NewLoopQueue(args ...int) *loopQu

哈希表，又叫做散列表，在golang中叫做Map。这种数据结构提供了键（key）和值（value）的映射关系。只要给出一个key，就可以高效查找到它所匹配的value，时间复杂度接近于O（1）。 首先golang的哈希表又称为map，这个数据结构的优势在于读写性能都是O（1）的。同时拥有数组和链表的优势。 哈希表是key-value形式，本质上是一个数组。在对key进行哈希函数处理后，得到一个整型索引，实现Key和数组下标的转换，从而和value对应。 实现哈希表的关键在于哈希函数的选择，很大程度上决定了哈

树和图是典型的非线性数据结构 树的定义： 树是n（n>=0）个节点的有限集。当n=0时，成为空树。在任意一个非空树中，有如下特点： 有且只有一个特定的节点成为根节点 当n>1时，其余节点可分为m（m>0）个互不相干的有限集，每个集合本身也是一个树，并成为根的子树。 树的最大层级数，称为树的高度或者深度 二叉树的定义： 二叉树的是指该树的每个节点最多有2个子节点，有可能时两个，也可能只有1个，或者是没有 二叉树的两种特殊形式： 满二叉树：一个二叉树的所有非叶子节点都存在左孩子和右孩子，

二叉树的遍历方式 从节点之间位置关系的角度： 前序遍历 中序遍历 后序遍历 层序遍历 从更宏观的角度： 深度优先遍历（前序遍历，中序遍历，后续遍历） 广度优先遍历（层序遍历） 深度优先遍历 前序遍历 二叉树的前序遍历，输出顺序是根节点，左子树，右子树（也叫做根左右） 中序遍历 二叉树的中序遍历，输出顺序是左子树，根节点，右子树（也叫做左根右） 后序遍历 二叉树的后序遍历，输出顺序是左子树，右子树，根节点（也叫做左右根） 递归实现 （值得注意的是遍历方法的对象是节点） package main im

二叉堆，本质上是一种完全二叉树。只是在完全二叉树地基础上有一些其他地特性 复习完全二叉树定义： 只要最后一个节点之前地所有非叶子节点都存在左孩子和右孩子，且所有叶子节点在同一层次上地二叉树就叫做完全二叉树。 二叉堆 最大堆（大顶堆） 最大堆地任何一个父结点的值。都大于或等于它左孩子或者右孩子地值 二叉堆的根节点叫做堆顶，最大堆的堆顶是整个堆中的最大元素 最小堆（小顶堆） 最大堆地任何一个父结点的值。都小于或等于它左孩子或者右孩子地值 二叉堆地根节点叫做堆顶，最小堆的堆顶是整个堆中的最小元素 二叉堆的gol

什么是队列 通过上面的链接，我们可以知道什么是一般的队列，它的特性就是先进先出 但这里的优先队列不再遵循先进先出的原则，而是分为两种情况： 最大优先队列：无论入队顺序如何，都是当前最大的元素优先出列 最小优化队列：无论入队顺序如何，都是当前最小的元素优先出列 这里用最大堆实现最大优先队列，如下： ...

在前面的系列文章中，我们讲过了二叉查找树的相关知识和实现（二叉树（一）–概述（附二叉搜索树实现））。在文章的最后，我们总结了二叉查找树的查找时间复杂度： 对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度是O（logn）,和树的深度是一样的。 但对于极端情况（每次插入数据大小都是增大的，或者减小的），外形上看就只有一半的树，查找时间复杂度就会退化成O（n）的 为了解决二叉查找树查找时间复杂度退化的问题，需要二叉数据的自平衡，也就是本节要讲的平衡二叉树。通过自身的平衡调整

引言 前面我们已经讲到很多的树，比如普通二叉树，二叉堆，二叉查找树，平衡二叉树等。那现在有一个问题，这么多的树都是用来干什么的？其实啊，任何事物都有着发展的必然性，都是为了解决问题。而随着问题规模和深度的不断加深，对应的解决方案也随之发展。这些树大多都是为了解决查找效率，或者是保证查找结果的有序性。实际场景中，无非读和写（删除和更新算是写的一种）。针对写操作，更看重的是稳定性，正确写是第一位的，写的速度是其次，因为生产数据的来源流量也肯定不是很大，多花时间来写是ok的。但是读就是持续追求效率的方向，历史数据

引言 在B-树详解（一）的部分，我们从数据库索引出现，比较了二叉查找树和B-Tree的查找效率，B-Tree通过建少磁盘IO提高查找效率。在第一部分我们对B-树的定义和整体有了一定的认识，下面就重点看看B-Tree查找，插入，和删除的具体过程。 定义 B树是一种平衡的多分树，通常我们说m阶的B树，它或者是空树，或者必须满足如下条件： 如果根不是叶节点，则根至少有两个子节点（不然的话就成单支了），有[1，m-1]个元素 每个中间节点（不是根节点和叶子节点）都包含[math.ceil（m/2）-1，m-1]个

简介 B+树是应文件系统所需而产生的B树的变形树，那么可能一定会想到，既然有了B树，又出一个B+树，那B+树必然是有很多优点的，其中最重要的一点就是有者比B-tree更高的查询性能 B+树的特征 和B-树相比较，具备一些新的特征： 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点； 所有的叶子结点中包含了全部元素的信息，及指向含有这些元素记录的指针，且叶子结点本身依元素的大小自小而大的顺序链接。 (而B树的叶子节点并没有包括全部需要查找的