红黑树
红黑树（）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为「对称二叉B树」，它现代的名字源于利奧尼達斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在\text{O}(\log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。 歷史 1972年，鲁道夫·拜尔發明了…
标签：#樹結構
共 5 篇文章
樹狀圖 (圖論)
在圖論內，樹狀圖（）是一個有向图；並且，對其中一個我們稱呼作根的頂點v，以及任何其他頂點u，此圖必然存在且只存在一條從v到u的路徑。換句話說，樹狀圖是一個有向的，有根的樹，並且所有的邊都指離根的方向。所有的樹狀圖都是一個有向无环图。 參見 樹 (圖論) 樹狀結構
树旋转
在数据结构中，树旋转（）是对二叉树的一种操作，不影响元素的顺序，但会改变树的结构，会将一个节点上移，一个节点下移。树旋转会改变树的形状，因此常被用来将较小的子树下移、较大的子树上移，从而降低树的高度、提升许多树操作的效率。 树的旋转方向有很多不同的定义，有些定义彼此之间还存在冲突。有些人认为旋转方向应该反映节点的移动方向（左子树旋转到父节点的位置为右旋），有些人则认为旋转方向应该反映被旋转的子树是哪棵（左子树旋转到父节点的位置为左旋，与…
树堆
樹堆（），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为O(\log{n})。相對於其他的平衡二叉搜索樹，Treap的特点是實現簡單，且能基本實現隨機平衡的結構。属于弱平衡树。 介绍 Treap一词由Tree和Heap二词合成而来。其本身是一棵二叉搜索树，它的左子树和右子树也分别是一个Treap，和一般的二叉搜索树不同的是，Treap为每个节点记录优先…
笛卡尔树
笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。 定义 无相同元素的数列构造出的笛卡尔树具有下列性质： 结点一一对应于数列元…