YangLei253

天下难事，必作于易；
天下大事，必作于细。

0%

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

概述

线段树 是一种用以维护区间信息 的数据结构，它可在 $O(log^N)$ 时间内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

阅读全文 »

发表于 分类于
本文字数： 3.1k 阅读时长 ≈ 3 分钟

概述

块状链表 是一种比较中庸的数据结构。它将 “分块思想” 应用于链表之中，从而整合了线性表与链表的优缺点，使得其上操作的时间复杂度均为 $O(\sqrt{N})$。

阅读全文 »

发表于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

概述

k-d 树 是在 $k$ 维欧几里德空间中组织点的一种数据结构。其可应用于多种场合，例如多维键值查询、范围查询、最近邻搜索。

阅读全文 »

发表于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

概述

Treap 树 是一个附加域满足堆性质的二叉查找树，其基本操作的期望时间复杂度为 $O(log^N)$。相比于 AVL、红黑树而言，其实现简单，且能基本实现随机平衡。

阅读全文 »

发表于 分类于
本文字数： 13k 阅读时长 ≈ 12 分钟

概述

红黑树 是一种自平衡的二叉查找树。通过为树中节点添加颜色属性并施以一定规则，红黑树可保证针对二叉查找树各种操作的最坏时间复杂度为 $O(log^N)$。

阅读全文 »

发表于 分类于
本文字数： 6.2k 阅读时长 ≈ 6 分钟

概述

伸展树 是一种自调整的二叉查找树。它没有 AVL 那样严格的平衡条件，通过施以某些调整可使得树上各种操作的平均时间复杂度为 $O(log^N)$。

阅读全文 »

发表于 分类于
本文字数： 6.6k 阅读时长 ≈ 6 分钟

概述

斐波那契堆 属于一种构建极为精妙的堆。它由二项队列改造而成，并将懒惰合并及左式堆的 decreaseKey() 实现方法融入其中，最终造就除删除操作外的所有操作的平均时间复杂度为 $O(1)$。

阅读全文 »