Tag Archives: 树

Double-Array Trie举例

Posted on 2010/09/15 by admin

下面我先画一个图来说明字典的构成. 1.假设我们有词典如下

Posted in 算法与数据结构 | Tagged , , , , | 1 Comment

并查集（等价类）及其实现

Posted on 2010/09/03 by admin

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 进行快速规整。

Posted in 算法与数据结构 | Tagged , , , , | Comments Off

Prüfer编码与Cayley公式

Posted on 2010/08/29 by admin

Cayley公式是说一个完全图K_n有n^(n-2)棵生成树，换句话说n个节点的带标号的无根树有n^(n-2)个。 Prüfer编码是对带标号无根树的一种编码方式。给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。写下的编码即为Prüfer编码。

Posted in 算法与数据结构 | Tagged , , , , | Comments Off

Treap

Posted on 2010/08/21 by admin

如果一个二叉排序树节点插入的顺序是随机的，这样我们得到的二叉排序树大多数情况下是平衡的，Treap正是利用这一点来创建一棵相对平衡的二叉树。Treap是一棵二叉排序树，它的左子树和右子树分别是一个Treap。和一般的二叉排序树不同的是，Treap纪录一个额外的数据，就是优先级，通过对优先级的随机赋值可以达到上述目的。

Posted in 算法与数据结构 | Tagged , , , , | 1 Comment

树中最深的叶子节点必定在树的直径上

Posted on 2010/06/21 by admin

证明: 树中最深的叶子节点必定在树的直径上（当有多个最深叶子节点时至少包含其中一个）。 反正法： 假设存在树的一条直径L，其不包含树的最深节点d 记L为a-b-c，其中a和c是L两端的叶子节点，b是L中的根节点（即b是L中其它所有节点的祖先节点） 找到b和d的最深公共祖先节点p，则a-p-d或者c-p-d的长度均大于L

Posted in 算法与数据结构 | Tagged , , | Comments Off