跳跃表（Skip List)

一、二分查找和AVL树查找 二分查找要求元素可以随机访问，所以决定了需要把元素存储在连续内存。这样查找确实很快，但是插入和删除元素的时候，为了保证元素的有序性，就需要大量的移动元素了。 如果需要的是一个能够进行二分查找，又能快速添加和删除元素的数据结构，首先就是二叉查找树，二叉查找树在最坏情况下可能 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 02 高级数据结构

有序表查找

1 折半查找(二分查找) 折半查找：又称为二分查找。在有序顺序存储的线性表中，取中间记录作为比较对象，若相等,则成功；若给小于，则在左半区继续查找；若给大于，则在右半区继续查找。 $mid = \frac{low+high}{2}= low+\frac{1}{2}(high-low)$ 适合有序，静 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

堆

堆（Heap）是一种特别的树状数据结构：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。分为最小堆和最大堆。 二叉堆 左倾堆 斜堆 二项堆 斐波那契堆 索引堆 Treap 树堆 1、二叉堆 二叉堆是完全二元树或者是近似完全二元树，按照数 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

图

一、图的基本概念 图：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G 表示一个图，V 是图 G 中顶点的集合。E 是图 G 中边的集合。 1、各种图定义 无向边：若顶点 $V_i$ 到 $V_j$，之间的边没有方向，则称这条边为无向边(Edge)。 用无序偶对 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

红黑树

1、红黑树定义 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。可以在 O(logn) 时间内做查找，插入和删除。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。 满足如下条件： 每 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

线性索引查找

索引：就是把一个关键字与它对应的记录相关联的过程。 索引按照结构可以分为线性索引、树形索引和多级索引。 线性索引：就是将索引项集合组织为线性结构，也称为索引表。 1 稠密索引 稠密索引：在线性索引中，将数据集中的每个记录对应一个索引项，索引项按照关键码有序排列。 但数据量大时，可能由于内存有限， ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

散列(Hash)表

1 散列表查找定义 散列技术：是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f (key)。 散列函数：对应关系 f 。又称为哈希 (Hash) 函数。 散列表：采用散列技术存储记录的一块连续的存储空间。又称为哈希表 (Hash table ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

多路查找树(B 树)

多路查找树：每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。 1、2-3 树 2-3 树：每一个结点都具有两个孩子 (2 结点) 或三个孩子 (3 结点) 的多路查找树 2 结点：包含一个元素和两个孩子(或没有孩子) ，左小右大。 3 结点：包含一小一大两个元素和三个孩子(或没有孩 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 03 查找

排序的基本概念与分类

1 排序的基本概念 假设含有 n 个记录的序列为{r1,r2,…,rn} ，其相应的关键字分别为{k1,k2,…,kn} ，需确定 1,2,…,n 的一种排列 p1,p2,…,pn，使其相应的关键字满足 kpl<=kp2<=…<=kpn (非递减或非递增) 关系，即使得序列成为一个 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序

插入排序

1 直接插入排序 直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序袭。 思路 如第 0 到 5 范围内的数从小到大排列，第六个数记为 temp，此时第 temp 比第 5 个数小，那么第 5 个 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 04 排序