红黑树
红黑树（）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为「对称二叉B树」，它现代的名字源于利奧尼達斯·J·吉巴斯和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在\text{O}(\log n)时间内完成查找、插入和删除，这里的n是树中元素的数目。 歷史 1972年，鲁道夫·拜尔發明了…
标签：#二叉树
共 10 篇文章
線段樹 (儲存區間)
線段樹（）是一種二元樹形資料結構，1977年由喬恩·本特利發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。 一個包含n個區間的線段樹，空間複雜度為O(n)，查詢的時間複雜度則為O(\log n+k)，其中k是符合條件的區間數量。 此資料結構亦可推廣到高維度。 結構 線段樹是一個平衡的二叉树，它将每个长度不为1的区间划分成左右两个区间递归求解。令整個區間的長度為N，則其有N個葉節點，每個葉節點代表一個單位區間，每個內…
二叉空间分割
在 计算机科学中，二叉空间分割（，简称BSP）是一种通过使用超平面作为分割，递归细分空间为两凸集的算法。这个过程将空间细分转化为了树结构，即所谓的二叉空间分割树（BSP树）。 二叉空间分割算法是在1969年为3D计算机图形所开发，其结构使得场景中的物体包含有额外用于渲染的空间信息，例如可以将物体对象针对观察者位置快速的从前至后进行排序。其他BSP的应用包括：在 CAD中执行几何行动与形状(构造实体几何)，机器人技术和3D游戏中的碰撞探测…
二元搜尋樹
二叉搜索树（，简称BST）是一种有根二叉树数据结构。它要求每个内部节点的键值都大于其左子树中所有节点的键值，且都小于其右子树中所有节点的键值。该树各项操作时间复杂度均与树的高度成线性关系。 二叉搜索树每次比较都能排除大约一半的剩余节点，故能以对数时间查找、插入、删除数据。但其性能依赖于节点的插入顺序，插入随机键值时仍能维持对数级别，但在下会退化成链表。为保证效率，研究者发明了多种平衡树，能将最坏查找复杂度维持在O(\log n)。 二叉…
二叉树
在電腦科學中，二元樹（）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構。通常分支被稱作“左子樹”或“右子樹”。二元樹的分支具有左右次序，不能随意顛倒。 二元樹的第i層至多擁有2^{i-1}個節點；深度為k的二元樹至多總共有2^{k+1}-1個節點（定义根节点所在深度 k_0=0），而總計擁有節點數符合的，稱為「完美二叉树」；深度為k有n個節點的二元樹，當且僅當其中的每一節點，都可以和深度k的滿二元樹，序號1到n的節點一…
树堆
樹堆（），是計算機科學中術語。是有一个随机附加域满足堆的性质的二叉搜索树，其結構相当于以随机數據插入的二叉搜索树。其基本操作的期望時間複雜度为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:引线二叉树;}-）是添加了直接指向节点的前驱和后继的指针的二叉树。 定义 线索二叉树 的定义如下: “一个二叉树通过如下的方法“穿起来”：所有原本为空的右子節點指针改为指向该节点在中序序列中的后继，所有原本为空的左子節點指针改为指向该节点的中序序列的前驱。” 线索二叉树能线性地遍历二叉树，从而比递归的中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节…
堆有序
当一颗二叉树的每个结点都大于等于它的两个子结点时，它被称之为堆有序。相应地，在堆有序的二叉树中，每个结点都小于等于它的父结点（如果有的话）。从任意结点向上，我们都能得到一列非递减的元素；从任意结点向下，我们都能得到一列非递增的元素。特别地：根结点是堆有序的二叉树中最大的结点。