平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离，因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。
1
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为"对称二叉B树"，它现代的名字源于Leo J. Guibas和罗伯特·塞奇威克于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况算法分析，并且在实践中高效：它可以在
O
{\displaystyle {\text{O}}}
时间内完成查找、插入和删除，这里的
n
{\displaystyle n}
是树中元素的数目。
AVL树是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是
O
{\displaystyle O}
。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
替罪羊树是电脑科学中，一种基于部分重建的自平衡二叉查找树。在替罪羊树上，插入或删除节点的平摊最坏时间复杂度是
O
{\displaystyle {\text{O}}}
，搜索节点的最坏时间复杂度是
O
{\displaystyle {\text{O}}}
。
在计算机科学中，B树是一种自平衡的树，能够保持数据有序。这种资料结构能够让查找数据、顺序访问、插入数据及删除的动作，都在时间复杂度内完成。B树，概括来说是一个一般化的二元搜寻树一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种资料结构常被应用在数据库和文件系统的实现上。
在计算机科学中，B树是一种自平衡的树，能够保持数据有序。这种资料结构能够让查找数据、顺序访问、插入数据及删除的动作，都在时间复杂度内完成。B树，概括来说是一个一般化的二元搜寻树一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种资料结构常被应用在数据库和文件系统的实现上。
AVL树是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是
O
{\displaystyle O}
。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
AVL树是计算机科学中最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是
O
{\displaystyle O}
。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者格奥尔吉·阿杰尔松-韦利斯基和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。
Mini wiki
