红黑树
红黑树（）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为「对称二叉B树」，它现代的名字源于利奧尼達斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在\text{O}(\log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。 歷史 1972年，鲁道夫·拜尔發明了…
标签：#搜索树
共 16 篇文章
加权平衡树
在计算机科学里面，加权平衡树（，縮寫：WBTs）是一种可以用来实现集合、字典（映射）和序列的平衡树。这些树结构在20世纪70年代被Nievergelt和Reingold作为有界限的自平衡树或BB[α]树提出。让这些结构普及的是高德纳。 就像其他自平衡树一样，加权平衡树储存的账簿信息可以在树结构被插入和删除操作打乱时，通过平衡结点和操作树旋转来使树结构重新达到平衡。特别的地方是，加权平衡树的每个结点储存这个结点下子树的大小，并且这个结点左…
AA树
AA樹在電腦科學一種形式的自平衡二元搜尋樹用於高效存儲和檢索序數據。AA樹的名稱是由它的發明者阿爾尼·安德森（Arne Andersson）而來。 AA樹是紅黑樹的一種變種，是安德森教授1993年在他的論文《Balanced search trees made simple》中介紹，設計的目的是減少紅黑樹考慮的不同情況，區別於紅黑樹的是，AA樹的紅節點只能作為右葉子，從而大大簡化了維護2-3樹的模擬。維護紅黑樹的平衡需要考慮7種不同的情…
左倾红黑树
左傾紅黑樹（，縮寫：LLRB）是一種類型的自平衡二元搜尋樹。它是紅黑樹的變體，並保證對操作相同漸近的複雜性，但被設計成更容易實現。 左傾紅黑樹（LLRB） 是 Robert Sedgewick 在 〈Left-Leaning Red-Black Trees〉（2008） 一文中提出，其核心理念是強制所有紅邊只能出現在左邊，透過這個限制，把原本需要處理的對稱情況「砍掉一半」，以此簡化紅黑樹的實作複雜度，但仍保有與 2–3 樹等價的平衡性 …
線段樹 (儲存區間)
線段樹（）是一種二元樹形資料結構，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…
可持久化线段树
可持久化线段树（又称函数式线段树）是一种可持久化数据结构（）。这种数据结构在普通线段树的基础之上支持查询某个历史版本，同时时间复杂度与线段树是同级，空间复杂度相较而言更高。 原理 与大部分可持久化数据结构相似，可持久化线段树在更新时尽可能与之前某一个旧版本共用一部分结点，从而节省空间。 例如，有一颗维护着区间和的线段树，现在以这颗线段树作为基础，将下标为 5 的元素数值减去一，同时另存为一个新的版本。按照一般线段树中使用的思路，当位于根…
最佳化二元搜尋樹
計算機科學中， 一個最佳化二元搜尋樹（Optimal BST），有時也被叫做重量平衡二元樹， 是有可能在已知的一串序列中得到最短搜尋時間的一棵二元搜尋樹（或期望的搜尋時間）。 最佳化二元搜尋樹可分為兩種：靜態的和動態的。 靜態的最佳化問題中，在完全被創建好之前，這棵樹是不能被修改的。在這狀況中，在這棵樹中的每個節點都存在特定的設計，這些設計是依照每個節點被存取的機率去設計出會得到最短的搜尋時間。不同的演算法能依照每筆資料所給的存取機率去…
二元搜尋樹
二叉搜索树（，简称BST）是一种有根二叉树数据结构。它要求每个内部节点的键值都大于其左子树中所有节点的键值，且都小于其右子树中所有节点的键值。该树各项操作时间复杂度均与树的高度成线性关系。 二叉搜索树每次比较都能排除大约一半的剩余节点，故能以对数时间查找、插入、删除数据。但其性能依赖于节点的插入顺序，插入随机键值时仍能维持对数级别，但在下会退化成链表。为保证效率，研究者发明了多种平衡树，能将最坏查找复杂度维持在O(\log n)。 二叉…
替罪羊树
替罪羊树（）是電腦科學中，一种基于部分重建的自平衡二叉搜索树。在替罪羊树上，插入或删除节点的平攤最壞時間複雜度是\text{O}(\log n)，搜索节点的最壞時間複雜度是\text{O}(\log n)。 在非平衡的二叉搜索树中，每次操作以后检查操作路径，找到最高的满足\max(size(son_L),size(son_R))>\alphasize(this)的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为…
树旋转
在数据结构中，树旋转（）是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，会将一个节点上移，一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。 树的旋转方向有很多不同的定义，有些定义彼此之间还存在冲突。有些人认为旋转方向应该反映节点的移动方向（左子树旋转到父节点的位置为右旋），有些人则认为旋转方向应该反映被旋转的子树是哪棵（左子树旋转到父节点的位置为左旋，与…
树堆
樹堆（），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为O(\log{n})。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。属于弱平衡树。 介绍 Treap一词由Tree和Heap二词合成而来。其本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap为每个节点记录优先…
伸展树
伸展树（）是一种能够自我平衡的二叉查找树，它能在均摊O(\log n)的时间内完成基于伸展（Splay）操作的插入、查找、修改和删除操作。它是由丹尼爾·斯萊托和羅伯特·塔揚在1985年发明的。 在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行調整，把被查找的条目搬移到离树根近一些的地…
AVL树
AVL树（）是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的時間複雜度都是 O(\log{n})。增加和删除元素的操作则可能需要藉由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和葉夫根尼·蘭迪斯，他们在1962年的论文《An algorithm for the organizati…
线索二叉树
在计算机科学中，引線二元樹（或稱-{zh-hant:線索二元樹;zh-hans:引线二叉树;}-）是添加了直接指向节点的前驱和后继的指针的二叉树。 定义 线索二叉树 的定义如下: “一个二叉树通过如下的方法“穿起来”：所有原本为空的右子節點指针改为指向该节点在中序序列中的后继，所有原本为空的左子節點指针改为指向该节点的中序序列的前驱。” 线索二叉树能线性地遍历二叉树，从而比递归的中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节…
搜索树
在计算机科学中，搜索树是一种树状数据结构，它的作用是能更方便地从一个集合中找到所要查找的键。搜索树規定其每个节点的键必须大于其左子树中的任何一個键且小于其右子树中的任何一個键。二元搜尋樹、三叉搜索树、B树等都屬於搜索樹。 参考文献