图（Graph）。和树比起来，这是一种更加复杂的非线性表结构，由顶点和连接每对顶点的边所构成的抽象网络就是图。 图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是顶点的集合，E是边的集合。 图中的元素叫做顶点（vertex）。顶点与其他顶点建立的连接关系叫做边（edge）。跟顶点相连接的边的条数叫做顶点的度（degree）。 如果图中任意两 …

阅读更多

堆的两点要求： 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做大顶堆。 对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做小顶堆。 完全二叉树：除最后一层外，其他层的节点都满；并且最后一层的节点从左到右是连续排列，中间没有断开，空位都在右边。 在构建完全二叉树的时候，新加入的节点在最后一层从 …

阅读更多

平衡二叉查找树其实有很多，比如，红黑树（Red-Black Tree，简称 R-B Tree）、伸展树（Splay Tree）、树堆（Treap）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树，它是一种不严格的平衡二叉查找树。 红黑树是一种含有红黑节点并能自平衡的二叉查找树。它必须满足下面性质： 每个节点要么是红色，要么是黑色； 根节点是黑色的； 每个叶子节点都是黑色的空节点（NIL），也就 …

阅读更多

AVL树（得名于发明者G. M. Adelson-Velsky 和 E. M. Landis）本质上是一棵带有平衡条件的二叉搜索树。 AVL树具有以下2个性质： 左子树和右子树的深度之差的绝对值不超过1； 左子树和右子树全都是 AVL树。 其中为了度量左右子树的深度之差，我们引入平衡因子(BF)的概念。 平衡因子： 某个节点的左子树的高度减去右子树的高度得到的差值。 对于一棵 AVL树，里面的所有 …

阅读更多

树：树是一种非线性的数据结构，一棵树是n（n>=0）个节点的集合。 用来连接相邻节点之间的关系，我们叫做“父子关系”。 我们把没有父节点的节点叫做根节点，节点的上一层节点是其父节点，下一层节点是其子节点，拥有相同父节点的子节点之间互称为兄弟节点。 树的三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。 节点的高度：节点到叶子节点的最长路径（边数） 节点的深度：根 …

阅读更多

哈希算法（Hash）又称摘要算法（Digest），它的作用是：对任意一组输入数据进行计算，得到一个固定长度的输出摘要。 哈希算法最重要的特点就是：相同的输入一定得到相同的输出；不同的输入大概率得到不同的输出。 哈希算法的目的就是为了验证原始数据是否被篡改。 // Java字符串的hashCode()就是一个哈希算法，它的输入是任意字符串，输出是固定的4字节int整数： …

阅读更多

散列表（Hash Table），也叫“哈希表”或者“Hash表”。是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。 通常，我们把这个关键字称为 Key，把对应的记录称为 Value，所以也可以说是通过 Key 访问一个映射表来得到 Value 的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫作散列表。 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实 …

阅读更多

跳表（Skip List）是一个动态数据结构（链表加多级索引），可以支持快速地插入、删除、查找操作的有序链表。 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

1. 跳表的演化 跳表的原始链表是一个有序单链表，如果要想在其中查找某个数据，只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。 从链表中每两个结点提取一个结点到上一级，我们把抽出来的那一级叫做索 …

阅读更多

栈（Stack）和队列（Queue），严格意义上来说，也属于线性表，是一种操作受限的线性表数据结构。 使用栈结构存储数据，讲究“先进后出”，即最先进栈的数据，最后出栈； 使用队列存储数据，讲究“先进先出”，即最先进队列的数据，也最先出队列。

1. 栈 栈（Stack）是一种只能从一端存取数据且遵循“先进后出”原则（First In Last Out，简称FILO）的线性存储结构。 通常，栈的开口端 …

阅读更多

线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。比如数组，链表、队列、栈等也是线性表结构。 而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

1. 数组 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。 数 …

阅读更多