大数据教程

1、  简述 并查集（Disjoint set或是Union-find set）是一种树形的算法设计，常见于解决一些不交叉结合（Disjoint Sets）的合拼及查看难题。 2、  操作过程 并查集是一种比较简单的算法设计，它关键涉及到2个操作过程，各自为： A． 合拼2个不交叉结合 B． 分辨2个原素是不是归属于同一个结合 （1）       合拼2个不交叉结合（Union(x,y)） 合拼实际操作非常简单：先设 … 继续阅读“数据结构之并查集”

1、简述 树状数组(binary indexed tree)，是一种设计方案新奇的二维数组构造，它可以高效率地获得二维数组中持续n数量的和。归纳说，树状数组一般 用以处理下列难题：二维数组{a}中的原素很有可能持续的被改动，怎么才能迅速地获得持续好多个数的和？ 2、树状数组操作过程 传统式二维数组(共n个原素)的原素改动和持续原素求饶的复杂性各自为O(1)和O(n)。树状数组根据将线性结构转化成伪树形结构构造（线性结构只有逐一扫描仪原素，而树形结构构造能够完成跳跃性扫描仪），促使改动和求饶复杂性 … 继续阅读“数据结构之树状数组”

1、 简述 Trie树，又被称为字典树，英语单词搜索树或是前缀树，是一种用以迅速查找的多叉树形结构，如英语字母的字典树是一个26叉树，数据的字典树是一个10叉树。 Trie一词来源于retrieve，音标发音为/tri:/ “tree”，也有些人读为/traɪ/ “try”。 Trie树能够运用字符串数组的公共性作为前缀来节省储存空间。如下图所显示，该trie树用10个连接点储存了6个字符串数组tea，ten，to，in，inn，int： 在该trie树中，字符串数组in，inn和int的公共性 … 继续阅读“数据结构之Trie树”

1、简述 线段树，也叫区段树，是一个完全二叉树，它在每个连接点储存一条直线（即“子二维数组”），因此常见于处理数列维护保养难题，它基础能确保每一个实际操作的复杂性为O(lgN)。 2、线段树操作过程 线段树的操作过程关键包含结构线段树，区段查看和区段改动。 （1）    线段树结构 最先详细介绍结构线段树的方式：让根节点表明区段[0,N-1]，即全部N数量所构成的一个区段，随后，把区段分为两截，各自由上下子树表明。不会太难证实，那样的线段树的连接点数仅有2N-一个， … 继续阅读“数据结构之线段树”

1. 简述 同splay tree一样，treap也是一个平衡二叉树，但是Treap会纪录一个附加的数据信息，即优先。Treap在以关键码组成二叉搜索树的另外，还按优先来考虑堆的特性。因此，Treap=tree heap。这儿必须留意的是，Treap并并不是二叉堆，二叉堆务必是完全二叉树，而Treap能够并不一定是。 2. Treap操作过程 为了更好地使Treap 中的连接点另外考虑BST特性和最小堆特性，难以避免地要对其构造开展调节，调节方法被称作转动。在维护保养Treap 的全过程中，仅有 … 继续阅读“数据结构之Treap”

1. 简述 AVL树是最开始明确提出的自平衡二叉树，在AVL树中一切连接点的2个子树的高宽比较大 区别为一，因此它也被称作高宽比平衡树。AVL树而出名于它的发明人G.M. Adelson-Velsky和E.M. Landis。AVL树种搜索、插进和删掉在均值和最坏状况下全是O（log n），提升和删掉很有可能必须根据一次或数次树转动来再次均衡这一树。文中详细介绍了AVL树的设计方案观念和操作过程。 2. 基础专业术语 有四诸多状况很有可能造成二叉查找树不平衡，各自为： （1）LL：插进一个新连接 … 继续阅读“数据结构之AVL树”

1.  简述 位图文件（bitmap）是一种十分常见的构造，在数据库索引，数据编码等层面有广泛运用。文中详细介绍了位图文件的完成方式以及应用领域。 2. 位图文件完成 （1）自身完成 当政图上，每一个原素为“0”或“1”，表明其相匹配的原素不会有或是存有。 #define INT_BITS sizeof(int) #define SHIFT 5 // 2^5=32 #define MASK 0x1f // 2^5=32 #define MAX 1024*1024*1024 //max … 继续阅读“数据结构之位图”

1. 详细介绍 文中详细介绍了较为初中级的图优化算法，包含深度优先解析xml，深度广度优先选择解析xml和双重深度广度优先选择解析xml。 2. 深度优先解析xmlDFS 2.1 优化算法观念 从图上某一端点v逐渐，浏览此连接点，随后先后从v中未被浏览的临接点考虑深度优先解析xml图，直至图上上全部和v有途径互通的端点都被浏览；若这时图上还有端点未被浏览，则代选图上一个未被浏览端点做起始点，反复之上全过程，直至图上全部端点都被浏览截止。 深度优先检索解析xml类似树的先序遍历。假设给出图G的初态 … 继续阅读“算法之图搜索算法（一）”

1、 简述 在开展计算机算法时，大家常见的二种线形算法设计是二维数组和链表。他们都有优点和缺点。二维数组特性是原素在运行内存中紧挨着储存，因此优势是精准定位快（O(1)），缺陷是插进删掉慢（O(n)）；而链表则不一样，它根据表针将不一样部位的原素连接起來，因此优点和缺点与二维数组恰好反过来：精准定位慢（O(n)），插进删掉快（O(1)）。文中详细介绍一种新的算法设计：小块链表，它将二维数组和链表的优势融合来，各种各样实际操作的算法复杂度均为O(sqrt(n))。 2、 小块链表的操作过程 小块链 … 继续阅读“数据结构之块状链表”

1. 简述 后缀数组是一种处理字符串数组难题的强有力专用工具。对比于后缀树，它更便于完成且占有运行内存更少。在具体运用中，后缀数组常常用以处理字符串数组相关的繁杂难题。 文中绝大多数內容节选自参考文献[1][2]。 2. 后缀数组 2.1   好多个定义 （1）后缀数组SA 是一个一维数组，它储存1..n 的某一排序SA[1]，SA[2]，……，SA[n]，而且确保Suffix(SA[i]) < Suffix(SA[i 1])，1≤i<n。也就是将S 的n 个后缀 … 继续阅读“数据结构之后缀数组”