此條目需要补充更多来源 。(2019年7月8日 ) 请协助補充多方面可靠来源 以改善这篇条目，无法查证 的内容可能會因為异议提出 而移除。"平衡树" — 网页、新闻、书籍、学术、图像 ），以检查网络上是否存在该主题的更多可靠来源（判定指引 ）。
平衡树 是计算机科学 中的一类数据结构，为改进的二叉查找树 。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升[1] 平衡树 。
在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。
基本操作 旋转（rotate）：几乎所有平衡树的操作都基于树旋转 操作（也有部分基于重构，如替罪羊树 ），通过旋转操作可以使得树趋于平衡。对一棵查找树（search tree）进行查询、新增、删除等动作，所花的时间与树的高度h成比例，并不与树的容量n成比例。如果可以让树维持平衡，也就是让h维持在 O ( log n ) {\displaystyle O(\log {n})} O ( log n ) {\displaystyle O(\log {n})} [1]
插入（insert）：在树中插入一个新值。
删除（delete）：在树中删除一个值。
查询前驱（predecessor）：前驱定义为小于x ，且最大的数。
查询后继（successor）：后继定义为大于x ，且最小的数。
在维护节点大小（size）后，可以支持以下操作：
查询排名（rank）：排名定义为比x小的数的个数加一。
查询第k大：即排名为k 的数。
各种平衡树 AVL树 ：是最早被发明的自平衡二叉查找树 。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度 都是 O ( log n ) {\displaystyle O(\log {n})} 树旋转 ，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky 和Evgenii Landis，他们在1962年的论文An algorithm for the organization of information 中公开了这一数据结构。 节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。树堆 （Treap）：是有一个随机附加域满足堆 的性质的二叉搜索树 ，其结构相当于以随机数据插入的二叉搜索树 。其基本操作的期望时间复杂度 为 O ( log n ) {\displaystyle O(\log {n})} 平衡二叉搜索树 ，Treap的特点是实现简单，且能基本实现随机平衡的结构。伸展树 （Splay tree）：能在均摊 O ( log n ) {\displaystyle O(\log {n})} 罗伯特·塔扬 在1985年发明的。在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，被查频率高的那些条目就应当经常处于靠近树根的位置。于是想到设计一个简单方法，在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。 它的优势在于不需要记录用于平衡树的冗余信息。红黑树 （Red–black tree）：在1972年由鲁道夫·贝尔 发明，被称为"对称二叉B树 "，它现代的名字源于Leo J. Guibas和Robert Sedgewick 于1978年 写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间 ，并且在实践中高效：它可以在 O ( log n ) {\displaystyle O(\log {n})} 加权平衡树 （Weight balanced tree）：加权平衡树的每个结点储存这个结点下子树的大小，可以用来实现顺序统计树 操作。优势在于占用空间相对较小。2-3树 ：其内部节点（存在子节点的节点）要么有2个孩子和1个数据元素，要么有3个孩子和2个数据元素，叶子节点没有孩子，并且有1个或2个数据元素。2–3树和AA树 是等距同构 的，换句话说，对于每个2–3树，都至少有1个AA树和它的元素排列是相同的。AA树 ：AA树是红黑树 的一种变种，是Arne Andersson教授在1993年年在他的论文"Balanced search trees made simple"中介绍，设计的目的是减少红黑树 考虑的不同情况，区别于红黑树的是，AA树的红节点只能作为右叶子，从而大大简化了维护2-3树 的模拟。替罪羊樹 ：其平衡基于部分重建，在非平衡的二叉搜索树 中，每次操作以后检查操作路径，找到最高的满足左右子树大小大于平衡因子（alpha）乘以自身大小的结点，重建整个子树。这样就得到了替罪羊树，而被重建的子树的原来的根就被称为替罪羊节点。
其他类型 以下数据结构支持平衡树大多数操作，但实现有根本不同:
应用 用于表示有序的线性数据结构，如优先队列 、关联数组 、键(key)-值(value)的映射 等。自平衡的二叉查找树与哈希表的相比，各有优缺。平衡树在按序遍历所有键值时是量级最优的，哈希表不能。自平衡二叉查找树在查找一个键值时，最坏情况下时间复杂度优于哈希表， O ( log n ) {\displaystyle O(\log n)} O ( n ) {\displaystyle O(n)} O ( log n ) {\displaystyle O(\log n)} O ( 1 ) {\displaystyle O(1)}
平衡树的排序方法，虽然在平均时间复杂度上也是 O ( n log n ) {\displaystyle O(n\log n)} 快速排序 、堆排序 、归并排序 等同为 O ( n log n ) {\displaystyle O(n\log n)}
参考文献
外部链接 Dictionary of Algorithms and Data Structures: Height-balanced binary search tree （页面存档备份，存于互联网档案馆 ） GNU libavl （页面存档备份，存于互联网档案馆 ）, a LGPL-licensed library of binary tree implementations in C, with documentation
平衡树, 此條目需要补充更多来源, 2019年7月8日, 请协助補充多方面可靠来源以改善这篇条目, 无法查证的内容可能會因為异议提出而移除, 致使用者, 请搜索一下条目的标题, 来源搜索, 网页, 新闻, 书籍, 学术, 图像, 以检查网络上是否存在该主题的更多可靠来源, 判定指引, 是计算机科学中的一类数据结构, 为改进的二叉查找树, 一般的二叉查找树的查询复杂度取决于目标结点到树根的距离, 即深度, 因此当结点的深度普遍较大时, 查询的均摊复杂度会上升, 为了实现更高效的查询, 产生了, 不平衡的树结构, 在这. 此條目需要补充更多来源 2019年7月8日 请协助補充多方面可靠来源以改善这篇条目 无法查证的内容可能會因為异议提出而移除 致使用者 请搜索一下条目的标题 来源搜索 平衡树 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 平衡树是计算机科学中的一类数据结构 为改进的二叉查找树 一般的二叉查找树的查询复杂度取决于目标结点到树根的距离 即深度 因此当结点的深度普遍较大时 查询的均摊复杂度会上升 1 为了实现更高效的查询 产生了平衡树 不平衡的树结构 在这里 平衡指所有叶子的深度趋于平衡 更广义的是指在树上所有可能查找的均摊复杂度偏低 平衡的树结构 目录 1 基本操作 2 各种平衡树 3 其他类型 4 应用 5 参考文献 6 外部链接基本操作 编辑旋转 rotate 几乎所有平衡树的操作都基于树旋转操作 也有部分基于重构 如替罪羊树 通过旋转操作可以使得树趋于平衡 对一棵查找树 search tree 进行查询 新增 删除等动作 所花的时间与树的高度h成比例 并不与树的容量n成比例 如果可以让树维持平衡 也就是让h维持在O log n displaystyle O log n 的左右 就可以在O log n displaystyle O log n 的复杂度内完成各种基本操作 1 插入 insert 在树中插入一个新值 删除 delete 在树中删除一个值 查询前驱 predecessor 前驱定义为小于x 且最大的数 查询后继 successor 后继定义为大于x 且最小的数 在维护节点大小 size 后 可以支持以下操作 查询排名 rank 排名定义为比x小的数的个数加一 查询第k大 即排名为k的数 各种平衡树 编辑AVL树 是最早被发明的自平衡二叉查找树 在AVL树中 任一节点对应的两棵子树的最大高度差为1 因此它也被称为高度平衡树 查找 插入和删除在平均和最坏情况下的时间复杂度都是O log n displaystyle O log n 增加和删除元素的操作则可能需要借由一次或多次树旋转 以实现树的重新平衡 AVL树得名于它的发明者G M Adelson Velsky和Evgenii Landis 他们在1962年的论文An algorithm for the organization of information 中公开了这一数据结构 节点的平衡因子是它的左子树的高度减去它的右子树的高度 有时相反 带有平衡因子1 0或 1的节点被认为是平衡的 带有平衡因子 2或2的节点被认为是不平衡的 并需要重新平衡这个树 平衡因子可以直接存储在每个节点中 或从可能存储在节点中的子树高度计算出来 树堆 Treap 是有一个随机附加域满足堆的性质的二叉搜索树 其结构相当于以随机数据插入的二叉搜索树 其基本操作的期望时间复杂度为O log n displaystyle O log n 相对于其他的平衡二叉搜索树 Treap的特点是实现简单 且能基本实现随机平衡的结构 伸展树 Splay tree 能在均摊O log n displaystyle O log n 的时间内完成基于伸展 Splay 操作的插入 查找 修改和删除操作 它是由丹尼尔 斯立特 Daniel Sleator 和罗伯特 塔扬在1985年发明的 在伸展树上的一般操作都基于伸展操作 假设想要对一个二叉查找树执行一系列的查找操作 为了使整个查找时间更小 被查频率高的那些条目就应当经常处于靠近树根的位置 于是想到设计一个简单方法 在每次查找之后对树进行调整 把被查找的条目搬移到离树根近一些的地方 伸展树应运而生 伸展树是一种自调整形式的二叉查找树 它会沿着从某个节点到树根之间的路径 通过一系列的旋转把这个节点搬移到树根去 它的优势在于不需要记录用于平衡树的冗余信息 红黑树 Red black tree 在1972年由鲁道夫 贝尔发明 被称为 对称二叉B树 它现代的名字源于Leo J Guibas和Robert Sedgewick于1978年写的一篇论文 红黑树的结构复杂 但它的操作有着良好的最坏情况运行时间 并且在实践中高效 它可以在O log n displaystyle O log n 时间内完成查找 插入和删除 这里的n是树中元素的数目 加权平衡树 Weight balanced tree 加权平衡树的每个结点储存这个结点下子树的大小 可以用来实现顺序统计树操作 优势在于占用空间相对较小 2 3树 其内部节点 存在子节点的节点 要么有2个孩子和1个数据元素 要么有3个孩子和2个数据元素 叶子节点没有孩子 并且有1个或2个数据元素 2 3树和AA树是等距同构的 换句话说 对于每个2 3树 都至少有1个AA树和它的元素排列是相同的 AA树 AA树是红黑树的一种变种 是Arne Andersson教授在1993年年在他的论文 Balanced search trees made simple 中介绍 设计的目的是减少红黑树考虑的不同情况 区别于红黑树的是 AA树的红节点只能作为右叶子 从而大大简化了维护2 3树的模拟 替罪羊樹 其平衡基于部分重建 在非平衡的二叉搜索树中 每次操作以后检查操作路径 找到最高的满足左右子树大小大于平衡因子 alpha 乘以自身大小的结点 重建整个子树 这样就得到了替罪羊树 而被重建的子树的原来的根就被称为替罪羊节点 其他类型 编辑以下数据结构支持平衡树大多数操作 但实现有根本不同 跳表 有序向量 值域线段树 数字搜索树 DigitalSearchTree 应用 编辑用于表示有序的线性数据结构 如优先队列 关联数组 键 key 值 value 的映射等 自平衡的二叉查找树与哈希表的相比 各有优缺 平衡树在按序遍历所有键值时是量级最优的 哈希表不能 自平衡二叉查找树在查找一个键值时 最坏情况下时间复杂度优于哈希表 O log n displaystyle O log n 对比O n displaystyle O n 但平均时间复杂度逊于hash表 O log n displaystyle O log n 对比O 1 displaystyle O 1 平衡树的排序方法 虽然在平均时间复杂度上也是O n log n displaystyle O n log n 但由于cache性能 树的调整操作等 性能上不如快速排序 堆排序 归并排序等同为O n log n displaystyle O n log n 复杂度的排序 参考文献 编辑 1 0 1 1 Donald Knuth The Art of Computer Programming Volume 3 Sorting and Searching Second Edition Addison Wesley 1998 ISBN 0 201 89685 0 Section 6 2 3 Balanced Trees pp 458 481 外部链接 编辑Dictionary of Algorithms and Data Structures Height balanced binary search tree 页面存档备份 存于互联网档案馆 GNU libavl 页面存档备份 存于互联网档案馆 a LGPL licensed library of binary tree implementations in C with documentation 取自 https zh wikipedia org w index php title 平衡树 amp oldid 70583384, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。