Van Emde Boas樹
van Emde Boas樹（或稱vEB樹或van Emde Boas優先隊列）是一個在電腦科學中的資料結構，也是一種關聯陣列，也是一種樹，由荷蘭電腦科學家 Peter van Emde Boas領導的團隊於 1975 年發明，可以儲存鍵值範圍在 m 位以內的二進制整數，也就是 u= 2^m 是樹中可以儲存的最大數字時，它可以在 O(\log m) 時間內執行所有種類的基本操作（假設對 m 的位元操作可以在常數時間內執行），也就是 O(…
标签：#树结构
共 39 篇文章
系統發生樹
系统发育樹（），有時簡稱為系統樹，又稱種系發生樹、親緣關係樹，或演化樹（），是一種表示生物类群、個體、基因或其他对象之間演化關係假说的樹狀圖。研究演化歷史及親緣關係，並發展相應推斷方法和模型的學科稱為系統發生學（）。在生物学中，系统发育学与系统分類學密切相关，其方法和成果广泛应用于流行病學、生態學等领域。 組成 根 系统发育树可分为“有根树”与“无根树”两类。 有根树（）包含一个明确的根；在该树所表示的范围内，根节点代表所有末端单元的最…
AC自动机算法
在计算机科学中，艾侯-科拉希克算法（）是由阿尔佛雷德·艾侯和玛格丽特·J·科拉希克（Margaret J. Corasick）发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa…
B树
B树（），是一种在计算机科学自平衡的树，能够高效的存储与访问键值对数据，但要求键数据类型上存在一全序。這種資料結構能够在對數時間內完成查找數據、插入數據及刪除的操作，与此同时还可以提供对数据的有序遍历。B树，概括来说是一个一般化的二元搜尋樹，而每個節點可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。由于B树允许存在超过2个子节点，其…
2-3树
计算机科学中，2–3树（）是一种树型数据结构，由约翰·霍普克洛夫特于1970年发明。 2–3樹中的内部节点可以有2个子節點和1个数据元素、或有3个子節點和2个数据元素，叶子节点有1至2个数据元素。 File:2-3-4 tree 2-node.svg|2节点 File:2-3-4-tree 3-node.svg|3节点 2–3树和AA树是等距同构的，意味着它们是同一种数据结构。换句话说，对于每个2–3树，都至少存在1種AA树和它的元素排…
AA树
AA樹在電腦科學一種形式的自平衡二元搜尋樹用於高效存儲和檢索序數據。AA樹的名稱是由它的發明者阿爾尼·安德森（Arne Andersson）而來。 AA樹是紅黑樹的一種變種，是安德森教授1993年在他的論文《Balanced search trees made simple》中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA樹的紅節點只能作為右葉子，從而大大簡化了維護2-3樹的模擬。維護紅黑樹的平衡需要考慮7種不同的情…
哈希树
哈希树（；Merkle tree），在密码学及计算机科学中是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而除了叶节点以外的节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。 哈希树的概念由瑞夫·墨克于 1979 年申请专利，故亦称墨克树（）。 概述 哈希树中，哈希值的求取通常使用诸如SHA-2的加密哈希函数，但如果只是用于防止非故意的数据破坏，也可以使用不安全的校验和取…
平衡树
平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。]] 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。 ]] 基本操作 旋转（rotate）：几乎所有平衡树的操作都基于树旋转操作（也有部分基于重构，如替罪羊树），通过旋转操作可以使得树趋于平…
線段樹 (儲存區間)
線段樹（）是一種二元樹形資料結構，1977年由喬恩·本特利發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。 一個包含n個區間的線段樹，空間複雜度為O(n)，查詢的時間複雜度則為O(\log n+k)，其中k是符合條件的區間數量。 此資料結構亦可推廣到高維度。 結構 線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內…
顺序统计树
在计算机科学，顺序统计树（）是二叉搜索树的变种。除了插入、查询和删除，这种数据结构还支持以下两种操作： Select(i) — 在树中查询第i小的元素 Rank(x) – 查找元素x的排名 这两种操作的平均时间复杂度是O(\log n)。当所用数据结构是平衡二叉树时，这是最坏复杂度。 算法实现 对于树中的每个节点，需要额外维护以这个节点为根的子树大小（该节点下点的个数）。 size[x] = size[left[x]] + size[r…
樹狀結構
樹狀結構（）又称树形结构、树结构，是一種將階層式的構造性質，以圖像方式表現出來的方法。樹狀圖（）或树形图则是用具有分支和节点的树状结构，来表示层级结构的一种方式。 樹狀結構的名稱來自於以樹的象徵來表現出構造之間的關係，雖然在圖像的呈現上，它是一個上下顛倒的樹，其根部在上方，是資料的開頭，而下方的資料稱為葉子。 树形结构是一层次的嵌套结构。一个树形结构的外层和内层有相似的结构， 所以，这种结构多可以递归的表示。樹狀結構只是一個概念，可以用…
樹狀拓撲
树状拓扑结构（），又称为树状网络（Tree Network）；树状网络是分层结构，适用于分级管理和控制系统。与星状结构相比，树状网络通信线路长度较短、成本低、易推广，但结构比星状网络复杂。网络中，除叶节点及其连线外，任一节点或连线的故障均影响其所在支路网络的正常工作。 优缺点 优点 易于推广：从本质上看这种结构可以延伸出很多分支和子分支，新的节点和新的分支易于加入网内。 故障隔离方便：如果某一分支的节点或线路发生故障，很容易将这个分支和…
双曲树
双曲树（）是一种信息可视化和图形绘制方法，其灵感来自双曲几何。 将分层数据显示为一棵树，由于每层的节点数量会呈指数级增长，因此会出现视觉上的混乱。对于一棵简单的二叉树来说，第 n 层的最大节点数是 2n，而分支较多的树的节点数增长得更快。因此，把树画成一个节点-链接图需要指数级的空间来显示。 解决上述问题的其中一种方法是使用双曲树，首先由Lamping等人提出。 双曲树采用双曲空间，其本质上比欧氏空间的“空间更大”。例如，在欧几里得空间…
分支因子
]] 在电脑运算、树数据结构、賽局理論领域中，分支因子（）是每个下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。 例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。 }}
H树
在分形几何中，H树（）是一种分形树结构，由互相垂直的线段构成，其中任意一条线段的长度都是次一级线段的\sqrt{2}倍。它因类似于字母“H”的重复图案而得名。它的豪斯多夫维数为2，能任意接近矩形中的每一点。其应用包括超大规模集成电路设计和微波工程。 构造 H树可从任意长度的线段开始构造，首先在该线段的两个端点作出两条垂线，如此反复，同时将每级绘制的线段长度缩短\sqrt{2}倍。 另一种生成相同分形集的方法是从一个边长比为1:\sqrt…
具象人类知识系统
具象人类知识系统（）有时也被称为狄德罗和达朗贝尔之树，是用来展示知识结构的树状图，由让·勒朗·达朗贝尔和德尼·狄德罗为《百科全书》（*'）制作。 该树是人类知识的分类，其灵感来自弗兰西斯·培根的《学术的进展》。树状图上只是的三个主要分支为：“记忆”/历史, “理智”/哲学和“想象”/诗歌。 值得注意的事实是神學归类在“哲学”下。历史学家羅伯·丹屯主张将宗教分类到人类理智中，其本身（啟示）并不是一个知识来源，是有关这个作品争议的重要因素。…
K-d树
在计算机科学里，*k-d树（k-维树*的缩写）是在k维欧几里德空间组织点的数据结构。k-d树可以使用在多种应用场合，如多维键值搜索（例：范围搜寻及最邻近搜索）。k-d树是空间二分树的一种特殊情况。 简介 k-d树是每个叶子节点都为k维点的二叉树。所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。节点左边的子树代表在超平面左边的点，节点右边的子树代表在超平面右边的点。选择超平面的方法如下：每个节点都与k维中垂直于超平面的那一维有关…
对话树
对话树是许多冒险游戏（含动作冒险游戏）、电子角色扮演游戏贯穿使用的游戏机制。视觉小说和恋爱模拟游戏等某些电子游戏类型，几乎完全围绕此类角色交互和分支对话。 参考资料
堆積
堆（）是计算机科学中的一種特別的完全二叉树。若是滿足以下特性，即可稱為堆積：「給定堆積中任意節點P和C，若P是C的父節點，那麼P的值會小於等於（或大於等於）C的值」。若父節點的值恆小於等於子節點的值，此堆積稱為最小堆積（）；反之，若父節點的值恆大於等於子節點的值，此堆積稱為最大堆積（）。在堆積中把根節點（）稱為堆積頂（top），而底層最靠右的節點稱為堆積底（bottom）。 堆積始於在1964年發表的堆積排序（），當時他提出了二元堆積樹…
基数树
在计算机科学中，基数树（，也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie（前缀树），其中作为唯一子节点的每个节点都与其父节点合并，边既可以表示为元素序列又可以表示为单个元素。 因此每个内部节点的子节点数最多为基数树的基数 ，其中为正整数，是2的次方，≥1，这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。 基数树的查找方式也与常规树不同（常规的树查找一开始就对整个键进行比…