数据结构

Radix Tree，又称基数树、压缩前缀树（Compact Trie）或 Patricia Tree (Practical Algorithm to Retrieve Information Coded in Alphanumeric)，是一种优化的 Trie (前缀树) 数据结构。它通过压缩那些只有一个子节点的路径，显著减少了节点数量和存储空间，尤其是在处理具有长公共前缀的键集合时。Radix Tree 在保持 Trie 快速前缀匹配和字典序遍历能力的同时，提高了空间效率和某些操作的时间效率。 核心概念： 前缀树 (Trie)： 一种用于存储字符串集合的树形数据结构，每个节点代表一个字符，路径代表一个前缀。 路径压缩： Radix Tree 的核心优化，将 Trie 中单分支（只有一个子节点）的路径上的节点合并成一个节点，其边（edge）上存储的不再是单个字符，而是一个字符串片段。 基数 (Radix)： 指树分支的最大数量，通常为 2 (二进制) 或 256 (字节)。 一、为什么需要 Radix Tree？与 Trie 的对比1.1 Trie (前缀树) 的...

时间复杂度 (Time Complexity) 是衡量一个算法运行时间长短的度量标准，它描述了算法的运行时间随着输入规模的增长而变化的趋势。通常使用大 O 符号 (Big O Notation) 来表示时间复杂度，因为它关注的是算法运行时间增长的“数量级”或“增长率”，忽略了常数因子和低阶项，从而能够抽象地比较不同算法的效率。理解时间复杂度对于设计高效算法、选择合适的算法解决问题以及评估程序性能至关重要。 核心思想： 衡量标准：评估算法运行时间的增长趋势，而非实际运行时间。 输入规模 n：算法处理数据量的抽象表示。 大 O 符号 O(f(n))：表示算法运行时间的上界，即最坏情况下的增长率。 关注数量级：忽略常数和低阶项，如 $O(2n+5)$ 简化为 $O(n)$。 分析代码：通过统计基本操作的执行次数来推导。 识别瓶颈：找出代码中最耗时的部分。 一、为什么需要时间复杂度？实际的程序运行时间受到多种因素的影响，包括： 硬件性能：CPU 速度、内存大小。 编程语言：Python 通常比 C++ 慢。 编译器优化：不同的优化级别。 操作系统负载：同时运行的其他进程。...

压缩字典树 (Compressed Trie)，也常被称为 基数树 (Radix Trie) 或 Patricia Trie (Practical Algorithm to Retrieve Information Coded in Alphanumeric)，是一种经过优化的字典树 (Trie) 数据结构。它在标准字典树的基础上，通过合并那些路径上只有一个子节点的节点，显著提高了空间效率，尤其适用于存储具有长公共前缀的字符串集合。 核心思想：标准字典树的每个节点通常只存储一个字符。当路径上出现连续的单子节点时，这些节点可以被合并成一个节点，该节点存储一个字符串片段。这样既能保持字典树的快速前缀查找能力，又能大幅减少节点数量和内存占用。 一、标准字典树 (Trie) 概述及其局限性在深入压缩字典树之前，我们先回顾一下标准字典树 (Trie) 的基本概念。 1.1 标准字典树 (Trie) 定义：Trie 是一种树形数据结构，用于存储字符串集合。它的名称来源于 “retrieval”，意为检索。 结构： 根节点通常为空字符串。 每个节点表示一个字符。 从根节点到任意节点的路...

跳表 (Skip List) 是一种概率性数据结构，由 William Pugh 于 1990 年发明。它是一种用于存储有序元素的数据结构，可以在平均 O(log N) 的时间复杂度内完成搜索、插入和删除操作。跳表的性能与平衡二叉树（如 AVL 树、红黑树）相当，但其实现更为简单，尤其是在并发环境下，它通常比平衡二叉树更容易实现高效的并发控制。跳表通过维护多层链表，并使用随机化方法来决定每个节点的高度，从而实现快速查找。 核心思想：在有序链表的基础上，增加多级索引（多层链表）。通过随机化算法决定每个节点在不同层级中出现的概率，使得大部分搜索可以跳过大量节点，从而达到对数级的查找速度。 一、为什么需要跳表？传统数据结构的局限性在计算机科学中，我们需要高效地存储和检索有序数据。常见的几种数据结构： 有序数组： 优势：查找（二分查找）O(log N)，按顺序遍历 O(N)。 劣势：插入和删除元素需要移动大量元素，时间复杂度 O(N)。 有序链表： 优势：插入和删除元素 O(1) (找到位置后)。 劣势：查找 O(N)，因为只能从头遍历。 平衡二叉搜索树 (如 AVL ...

B+ 树 (B+ Tree) 是一种多路搜索树 (M-way Search Tree)，它是 B 树 (B-Tree) 的一种变体，主要用于文件系统和数据库索引。B+ 树通过其独特的结构设计，能够有效减少磁盘 I/O 操作次数，并支持高效的范围查询。其核心特点是：所有数据都存储在叶子节点中，并且叶子节点之间通过指针连接形成一个有序链表，而非叶子节点（内部节点）只作为索引，存储键值，用于导航到正确的叶子节点。这使得 B+ 树在处理大量数据时，能够提供稳定且高效的查找、插入和删除性能。 核心思想：将索引和数据分离，所有实际数据存储在叶子节点，并使用多级索引（内部节点）加速查找。叶子节点构成有序链表，便于范围查询。这种结构特别优化了磁盘 I/O，因为大部分查询仅涉及少量磁盘块读取，且连续数据存储在磁盘上是连续的。 一、为什么需要 B+ 树？在计算机系统中，数据存储介质通常分为内存和磁盘。内存访问速度快（纳秒级），而磁盘访问速度慢（毫秒级）。当数据量非常大，无法完全加载到内存时，就需要从磁盘读取。传统的二叉搜索树（BST）、AVL 树、红黑树等，虽然在内存中表...

平衡二叉树 (Balanced Binary Search Tree, BBST) 是一类特殊的二叉搜索树 (Binary Search Tree, BST)。在标准的二叉搜索树中，如果数据插入顺序不当，可能会导致树变得非常“倾斜”，退化成链表，从而使得查找、插入和删除操作的平均时间复杂度从 $O(\log N)$ 恶化到 $O(N)$。平衡二叉树通过在每次插入或删除操作后，自动调整树的结构，以确保树的高度保持在对数级别，从而保证所有基本操作的时间复杂度始终为 $O(\log N)$。 核心思想：在二叉搜索树的基础上，通过引入“平衡因子”或“颜色”等额外属性，并在每次增删操作后自动进行结构调整（如旋转、变色），来限制树的高度，使其始终保持在对数级别，从而保证所有操作的高效性（O(log N)）。 一、为什么需要平衡二叉树？二叉搜索树的局限性二叉搜索树 (BST) 的核心特性是： 左子树中所有节点的值均小于根节点的值。 右子树中所有节点的值均大于根节点的值。 左右子树也分别是二叉搜索树。 BST 在理想情况下（树形平衡时）具有优秀的性能： 查找、插入、删除 的平均时间...

哈希表 (Hash Table) 是一种高效的数据结构，用于存储键值对 (key-value pairs)，提供快速的查找、插入和删除操作。它的核心思想是利用哈希函数 (Hash Function) 将键映射到数组的某个索引位置。然而，哈希表的性能高度依赖于负载因子 (Load Factor) 的管理，它在空间利用率、查找效率和再哈希 (Resizing/Rehashing) 成本之间扮演着关键的平衡角色。 核心思想：负载因子衡量了哈希表的“满”程度，是决定何时以及如何调整哈希表大小的关键指标，直接影响其性能和资源消耗。 一、哈希表简介与冲突在深入了解负载因子之前，我们先回顾哈希表的基本概念和冲突问题。 1.1 哈希表工作原理哈希表使用一个数组（通常称为桶数组或槽数组）来存储数据。当需要插入一个键值对时： 哈希函数：对键进行哈希计算，得到一个哈希值。 取模运算：将哈希值与桶数组的长度取模，得到一个数组索引。 存储：将键值对存储到该索引位置。 1.2 哈希冲突 (Hash Collision)不同的键经过哈希函数计算后，可能会得到相同的哈希值，进而映射到桶数组...

哈希表（Hash Table），又称散列表，是一种根据键（Key）直接访问存储位置的数据结构。它通过哈希函数将键映射到表中的一个位置来访问记录，从而实现平均 O(1) 时间复杂度的查找、插入和删除操作。哈希表是计算机科学中最重要的数据结构之一，广泛应用于数据库索引、缓存、符号表、唯一性检查等多种场景。 核心思想：哈希表通过哈希函数将任意大小的键映射到固定大小的数组索引，以实现快速的数据存取。 一、哈希表的基本概念哈希表的核心思想是键值映射。它将用户提供的键（key）通过一个特定的函数（哈希函数）转换成一个整数，这个整数就是数据在底层数组中的索引（下标）。 键 (Key): 唯一的标识符，用于查找、插入和删除数据。 值 (Value): 与键关联的数据。 哈希函数 (Hash Function): 将键映射到数组索引的函数。 哈希值 (Hash Value 或 Hash Code): 哈希函数计算出的整数值。 桶/槽 (Bucket/Slot): 底层数组中的一个位置，用于存储键值对。 示意图：哈希表基本概念 12345678910111213141...