替罪羊树
替罪羊树（）是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平攤最壞時間複雜度是\text{O}(\log n)，搜索节点的最壞時間複雜度是\text{O}(\log n)。 在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足\max(size(son_L),size(son_R))>\alphasize(this)的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为…
标签：#树结构
共 39 篇文章
三叉搜索树
三叉搜索树（，縮寫：TST）在计算机科学中是trie树或前缀树的一种实现，树的各个节点之间的结构类似二叉搜索树。和其他的前缀树一样，三叉搜索树可以用于实现带前缀搜索功能的关联数组。三叉搜索树比标准的前缀树更节省空间，但是牺牲了部分查找速度。三叉搜索树常用于实现拼写检查和自动完成功能。 描述 三叉搜索树的每个节点存储了一个字符、一个值对象或值指针以及三个指向子节点的指针。这三个字节点常被称为等位子节点、低位子节点和高位子节点。 参考文献
斜堆
斜堆（）是左偏树的一个变种。斜堆是一棵保持堆有序的二叉树，但是它不满足左偏性质，或者说斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说，所有的左偏树都是斜堆，但反之不然。 定义 仅有一个节点的树为斜堆； 两个斜堆合并的结果仍为斜堆。 合并操作 斜堆合并操作的递归合并过程和左偏树完全一样。假设我们要合并 A 和 B两个斜堆,且 A 的根节点比 B 的根节点小,我们只需要把 A 的根节点作为合并后新斜堆的根节点…
左偏树
左偏树（），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。 不同于斜堆合并的,左偏堆的合并操作的为 O(log n)，而完全二叉堆为 O(n)，所以左偏堆适合基于合并操作的情形。 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。 定义 左偏树是…
树状数组
[[File:BITDemo.gif|200px|thumb|根据数组[1, 2, 3, 4, 5]来创建对应的树状数组]] 树状数组或二元索引树（，簡稱 BIT），又以其发明者命名为芬威克樹（），最早由彼得·M·芬威克（Peter M. Fenwick）于1994年以《A New Data Structure for Cumulative Frequency Tables》为题发表在SOFTWARE PRACTICE AND EXPE…
树 (数据结构)
在計算機科學中，樹（）是一种抽象数据类型（ADT）或是實作這種抽象数据类型的数据结构，用來模擬具有樹狀結構性質的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 每个节点都只有有限个子节点或無子節點； 没有父节点的节点称为根节点； 每一个非根节点有且只有一个父节点； 除了根节点外，每个子节点可以分为多个不相交的子树； 樹裡面沒…
最小生成树
和它的最小生成树。在该图中，边的长度正比于权值A。]] 最小生成树（，簡稱MST）是最小權重生成樹（）的簡稱，是一个连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即 (u, v)\in E），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集（即 T\subseteq E）且 (V, T) 為樹，使得： :w(T) = \sum_{(u,…
四叉树
四元樹（）是一種樹狀資料結構，在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 拉斐爾·芬克爾與喬恩·本特利在1974年發展出來。類似的資料分割方法也稱為 Q-tree。所有的四元樹法有共同之特點: 可分解成為各自的區塊 每个区块都有节点容量。当节点达到最大容量时，节点分裂 樹狀資料結構依造四元樹法加以區分 形態 四元樹可以用他們資…
后缀树
后缀树（）是一种数据结构，能快速解决很多关于字符串的问题。后缀樹的概念最早由Weiner於1973年提出，既而由McCreight在1976年和Ukkonen在1992年和1995年加以改進完善。 一个string S的后缀树是一个边（edge）被标记为字符串的树。因此每一个S的后缀都唯一对应一条从根节点到叶节点的路径。这样就形成了一个S的后缀的基数树（radix tree）。后缀树是前缀树（trie）里的一个特殊类型。
伸展树
伸展树（）是一种能够自我平衡的二叉查找树，它能在均摊O(\log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼爾·斯萊托和羅伯特·塔揚在1985年发明的。 在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行調整，把被查找的条目搬移到离树根近一些的地…
二叉堆
二叉堆（）是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足堆特性：父節点的键值总是保持固定的序关系于任何一个子节点的键值，且每个節点的左子树和右子树都是一个二叉堆。 当父節点的键值总是大于或等于任何一个子节点的键值时为「最大堆」。当父節点的键值总是小于或等于任何一个子节点的键值时为「最小堆」。 存储 二叉堆一般用数组来表示。如果根节点在数组中的位置是1，第n个位置的子节点分别在2n和 2n+1。因此，第1个位置的子节点…
树的遍历
在计算机科学裡，树的遍历（也称为-{zh-hant:樹的遍歷;zh-hans:树的走访;}-或树的搜索）是一种圖的遍歷，指的是按照某种规则，不重复地访问某种樹的所有节点的过程。具体的访问操作可能是检查节点的值、更新节点的值等。不同的遍历方式，其访问节点的顺序是不一样的。以下虽然描述的是二叉树的遍历算法，但它们也适用于其他树形结构。 遍历的种类 与那些基本上都有标准遍历方式（通常是按线性顺序）的线性数据结构（如链表、一维数组）所不同的是，…
Trie
在计算机科学中，trie，又称前缀树或字典樹，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie这个术语来自于retrieval。trie的发明者Edward Fredkin把它读作…
AVL树
AVL树（）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是 O(\log{n})。增加和删除元素的操作则可能需要藉由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和葉夫根尼·蘭迪斯，他们在1962年的论文《An algorithm for the organizati…
抽象語法樹
編程碼的抽象語法樹: ]] 在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现；而类似于 if-condition-then…
大綱
大綱或作階層式大綱是顯示層級關係和樹狀結構型態的一種清單，用於呈現句子之中的要點或者某個主題的條列要旨。當中的每個項目也許會劃分成更多的子項目。目前通用的主流寫作型態指南，建議其組織層級至少要有兩個子分類。這種結構可用於文書的草擬方法、作為文件內容的摘要或是整體理解的途徑。除了清單的形式，尚有多種類型選擇。 參見 摘要 概念圖 等級制度 心智圖 主題地圖 樹狀結構 注釋
矩形式树状结构绘图法
[[File:Heatmap_incito.png|thumb|280px|这幅矩形式树状结构图显示的是病人等候时间的变化。该图像由[https://web.archive.org/web/20090409041055/http://www.heatmaps.co.uk/cc/nhs_waiting.html Incito有限公司（Incito Ltd）]按照创作共用的方式所发布的。]] 矩形式树状结构绘图法，又称为矩形式树状结构图绘制…
隨機樹
在電腦科學和數學裡面，一個隨機樹是一個經由隨機過程建立的樹或者樹狀圖(arborescence)。 隨機樹有以下幾種類別： （Uniform spanning tree） 隨機最小生成樹（random minimal spanning tree） （Random recursive tree） Treap或者說隨機二元搜尋樹 （Rapidly-exploring random tree） （brownian tree） 隨機森林 *
分析树
分析树（parse tree），也称具体语法树（concrete syntax tree），是一个反映某种形式语言字符串的语法关系的有根有序树。分析树一般按照两种相反的法则生成，一种是,一种是短语结构语法。分析树和抽象語法樹是不同的。