数据结构

SPLAY树(伸展树)1985年美国学者Daniel Sleator和Robert Tarjan提出Splay树，其能保证运算的摊还代价是\(O(\lg{n})\)，但不保证每次运算的实际代价都是\(O(\lg{n})\)，所以其并非严格意义上的自平衡二叉树，但这也使其有更简单的定义和运算步骤。这里直接给出Splay树的定义，首先其运算功能和前文的BST一致，且运算开始前只需保证二叉树是BST，但运算步骤是被具体规定的，它们都必须基于伸展运算\(splay(x)\)，其功能是通过多次单旋转使\(x\)成为树根。下面给出Splay树运算的步骤，其包括\(splay(x)\)的步骤： 1) \(splay(x)\)：开始迭代过程，每轮迭代的步骤如下： 1.1) \(x\)无父亲：退出迭代； 1.2) \(x\)有父亲无祖父：对\(x\)的父亲执行1次单旋转使\(x\)取代其父亲的位置(见上图第1张)。退出迭代；… 阅读全文

TREAP树(树堆)1980年Jean Vuillemin在解决范围搜索的问题时提出笛卡尔树，其特点是节点包含2个关键字。之后Edward McCreight提出一种基于笛卡尔树的结构并称之为Treap树，这是Tree和Heap的合成词，所以Treap也译为树堆。1989年Raimund Seidel和Cecilia R. Aragon利用带随机化策略的Treap树实现了BST的功能，在此之后Treap树一般用于指代这种结构。Treap树不是严格意义的自平衡二叉树，但其相比BST能在更一般的条件下保证二叉树的期望高度是\(O(\lg{n})\)。这里直接给出Treap树的定义，首先Treap节点相比前文的BST节点要额外存储一个堆关键字\(hkey\)，Treap树的运算功能和前文的BST一致，但每次运算开始前后除了要保证二叉树是BST还要保证任意节点的\(hkey\)都不大于其所有后代的\(hkey\)，最后规定Treap树的运算为如下的步骤：… 阅读全文

B树(B-Tree)1970年德国学者R.Bayer提出B树，这是一种多路的自平衡树，其相比于红黑树等自平衡二叉树并没有更好的渐进代价，但在一些场景中其实际性能优于自平衡二叉树。B树包含一个称为最小度数(degree)的关键参数，该参数可以是大于1的任意整数，初始化B树时需同时给定该参数，之后该参数固定不变。最小度数为\(t\)的B树可通过如下几点来定义： 1) B树节点可包含多个关键字，非树根节点的关键字数目的取值范围是\([t-1,2t-1]\)，树根节点是\([0,2t-1]\)，树根节点的关键字数目等于0当且仅当B树中无关键字，关键字数目等于\(2t-1\)的节点被称为满节点。节点的关键字被非严格递增排序，任意节点\(x\)的第\(i\geq 0\)个关键字可计为\(x.keys[i]\)。需明确任何时刻都能得到任意节点\(x\)此时的关键字数目；… 阅读全文

堆(Heap)堆也是种基于树的数据结构，整体上分为小根堆(min-heap)和大根堆(max-heap)。如果一个树中的每个节点都包含一个关键字，并且每个节点的关键字都不大于其所有后代的关键字，则称该树是一个小根堆，反之如果每个节点的关键字都不小于其所有后代的关键字，则称该树是一个大根堆。上图给出了一个大根堆的例子。考虑到之后会讨论一些使用到小根堆的算法，并且小根堆和大根堆在各个方面都高度对称，所以之后主要讨论小根堆，并默认堆是指小根堆。 堆和平衡树一样存在很多不同的实现，堆的实现通常比平衡树简单，但也更灵活多变，不同的堆会用到不同的树的表示。事实上之前讨论过的Treap数据结构就使用到了堆，其在同一个二叉树中维护了一个BST和一个堆。   二叉堆(Binary Heap)1964年英国学者J.… 阅读全文

空节点路径长度(Null Path Length)定义二叉树节点\(x\)的空节点路径长度\(npl(x)\)等于从\(x\)到\(x\)子树中的空节点的最小距离。于是若\(x\)为空节点则\(npl(x)=0\)，否则若\(x\)有空孩子则\(npl(x)=1\)，否则\(npl(x)>1\)。需明确大部分教材规定\(npl\)始于-1。下面给出与之相关的重要性质： a1) 设\(x\)为二叉树中的非空节点，则\(x\)子树的前\(npl(x)\)层是完美二叉树，前\(npl(x)+1\)层不是完美二叉树； 证明：\(npl(x)=1\)时该命题易验证，只需考虑\(npl(x)>1\)的情况。首先\(x\)子树前\(npl(x)-1\)层的节点都必须有2个非空的孩子，否则会导致\(npl(x)\)小于当前值的矛盾，于是其前\(npl(x)\)层必然能被看作高度为\(npl(x)\)的完美二叉树。但在第\(npl(x)\)层必然存在有至少1个空孩子的节点，否则将导致\(npl(x)\)大于当前值的矛盾，于是其前\(npl(x)+1\)层不能被看作完美二叉树。… 阅读全文

斜堆(Skew Heap)1986年美国学者Daniel Sleator和Robert Tarjan提出斜堆，这是种“松散”的左偏堆，其能保证运算的摊还代价是\(O(\lg{n})\)，但不保证每次运算的实际代价都是\(O(\lg{n})\)。斜堆和左偏堆的运算功能一致并且仅\(merge\)运算的步骤存在区别，斜堆的\(merge\)运算仍以左偏堆的为基础，但其在每次回溯都必须交换节点的左右孩子。这里不妨直接给出斜堆的运算步骤如下： 1) \(merge(r_1, r_2)\)：具体步骤分情况如下： 1.1) \(r_1,r_2\)不都非空：若\(r_1\)为空则返回\(r_2\)，否则返回\(r_1\)； 1.2) \(r_1,r_2\)都非空且\(r_1.key \leq r_2.key\)：置\(r_1.right=merge(r_1.right,… 阅读全文

二项树(Binomial Tree)二项树的形态是递归定义的，通常用\(B_k\)表示每种二项树形态，其中\(B_0\)仅包含树根节点，\(B_k\)可通过连接2个\(B_{k-1}\)得到，连接方式是在2个\(B_{k-1}\)间额外加1条树边，使其中一个\(B_{k-1}\)成为另一个\(B_{k-1}\)的最左子树，具体可参考上图。注意到该定义表明二项树必须是有序树，另外二项树通常更适合用孩子兄弟表示法实现。下面给出关于二项树的重要性质： a1) \(B_k\)形态的二项树共包含\(2^k\)个节点； 证明：将二项树形态对应的节点数计为\(n(B_k)\)，则有\(n(B_k)=2n(B_{k-1})=…=2^kn(B_{0})=2^k\)。 a2) \(B_k\)形态的二项树的高度为\(k+1\)；… 阅读全文

斐波那契堆(Fibonacci Heap)F堆可以认为是“松散”版的二项堆，其也是基于“链表+树”的。F堆上的树无需是二项树，其仅松散的要求链表上的树根出度唯一(仅要求某些运算结构维护该性质)。并且注意到F堆使用“双向循环链表”的物理结构表示链表与树，这种链表不承载序信息，故F堆的链表与树都是无序的。相比二项堆用“孩子兄弟法”表示树，F堆在用“双向循环链表”表示树时，需把所有子节点都指向父节点，而父节点只需一个指向其任意子节点的指针。最后明确“双向循环链表”只有单节点时，该节点的左右指针都指向其自身。F堆用最小节点指针\(min\)实现二项堆的链表表头指针\(head\)的作用。 F堆的运算与二项堆相同，其除\(pop\)与\(delete\)的代价为\(O(lgn)\)，其他运算的代价为\(O(1)\)。所以F堆的理论代价非常的优秀，但由于其实际代价中隐含着“大系数”，故程序语言中的优先队列不用F堆，F堆只适用于需要大量执行其\(O(1)\)运算的场景(如MST/Dijkstra)，所以通常认为F堆只是一个理论上更高效的结构。… 阅读全文

并查集(Union-find Disjoint Sets) 首先定义不相交集合数据结构(Disjoint-Sets Data Structure)，其首先是一个集合\(S = \{S_1,S_2,…,S_n \}\)，\(S\)中的元素也是集合，并且对于\(S\)中的任意两个元素\(S_x,S_y\)，都满足\(S_x\cap S_y=\emptyset\)。并查集则是带有特定运算的不相交集合数据结构，主要用于解决查询与合并的问题，由于\(S_x\)是可修改的，所以也称它们为动态集合。并查集运算的定义如下： 1) \(MAKE(x)\)：创建1个仅含元素\(x\)的动态集合，并把该动态集合加入到并查集中；   是若干不相交动态集合组成的集合\(S = \{S_1,S_2,…S_n \}\)，不相交指任意两动态集合间无重复元素，从动态集合中任取一元素即可形成与该动态集合的单射。对并查集中的动态集合\(S_k\)而言，动态指\(S_k\)中的元素是从无到有通过\(S\)上定义的运算结构动态添加的，所以接下来讨论\(S\)上的运算结构：… 阅读全文