平衡二叉树 AVL：用旋转维持查找效率
平衡二叉树 AVL：用旋转维持查找效率 普通 BST 的核心优点，是把“大小关系”嵌入到了树结构里，让查找、插入、删除都可以沿着一条比较路径进行。但它也有一个非常致命的问题：只要插入序列不理想，树就可能越长越歪，最后退化成链表。一旦退化，原...
二叉搜索树 BST：查找、插入与删除
二叉搜索树 BST：查找、插入与删除 在普通二叉树里，左右孩子的位置本身并不一定携带数值上的顺序信息。也就是说，虽然我们能遍历整棵树，但如果想高效查找某个值，普通二叉树未必比线性扫描好多少。二叉搜索树之所以重要，就是因为它在“树的层级结构”...
线索二叉树：让遍历更高效的思路
线索二叉树：让遍历更高效的思路 学二叉树遍历时，我们已经知道，前序、中序、后序遍历最自然的写法通常是递归。即使不用递归，也往往需要额外借助栈来保存访问状态。这说明一件事：普通二叉链表虽然能很好地表达父子关系，但当我们想按某种遍历顺序在树中前...
二叉树遍历：前序、中序、后序与层序
二叉树遍历：前序、中序、后序与层序 学完树的基本概念之后，二叉树里最先必须掌握的一件事，就是遍历。因为二叉树本身只是节点和左右孩子之间的组织关系，真正要做查找、统计、打印、构造、序列化时，第一步几乎总是“怎么把整棵树有顺序地访问一遍”。而不...
树的基本概念与存储结构
树的基本概念与存储结构 如果说前面的顺序表、链表、栈、队列都还属于“一条线上的世界”，那么从树开始，数据结构学习就正式进入了“层级世界”。树最大的不同在于，它不再只是简单地表示前后顺序，而是能够表示从属关系、层次关系和分支关系。现实里很多复...
稀疏数组、广义表与矩阵压缩存储
稀疏数组、广义表与矩阵压缩存储 在线性结构和字符串这些基础内容之后，数据结构学习很快就会碰到一个现实问题：并不是所有数据都适合“老老实实一个位置存一个值”这种最直白的方式。很多时候，原始数据虽然看起来规模很大，但真正有效的信息其实很少。如果...
串：字符串的存储与基础操作
串：字符串的存储与基础操作 在线性结构里，串看起来像是一个很熟悉、甚至有点“太常见以至于容易被忽略”的主题。因为无论是 C 里的字符数组，还是 Java、Go、Python 里的字符串对象，我们几乎每天都在用。但越是常用的东西，越容易只停留...
队列与双端队列：先进先出结构及其变体
队列与双端队列：先进先出结构及其变体 如果说栈代表的是“最近进入的内容最先处理”，那么队列代表的就是另一种同样高频、但完全不同的秩序：先进先出。最早进入队列的元素，应该最先离开；后来进入的元素，则排在后面等待处理。这个规则在现实里非常自然，...
栈：后进先出结构与典型应用
栈：后进先出结构与典型应用 学完顺序表和链表之后，一个很自然的问题就是：这些基础结构本身能不能进一步抽象成更有明确访问约束的模型？答案当然可以，而栈就是最经典的第一类。它不再允许你像线性表那样在任意位置自由访问和修改，而是主动收紧操作范围，...
链表：单链表、双链表与循环链表
链表：单链表、双链表与循环链表 学完顺序表之后，很多人会自然产生一个问题：既然数组按下标访问这么快，为什么还需要链表？答案就在顺序表最明显的短板里。顺序表依赖连续空间，访问位置很快，但一旦要在中间插入或删除元素，往往就需要整体搬移大量数据。...