平衡树
维基百科，自由的百科全书
平衡树是计算机科学中的一类数据结构。 二叉查找树是计算机科学中的一种重要的查找结构，而一般的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。
在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。
基本操作 [编辑]
几乎所有平衡树的操作都基于树旋转操作，通过旋转操作可以使得树趋于平衡。
各种平衡树 [编辑]
- AVL树，经典平衡树, 所有操作的最坏复杂度都是
的。 - Treap，利用随机堆的期望深度来优化树的深度，达到较优的期望复杂度。
- 伸展树，使得经常查找的结点深度较小，从而降低均摊复杂度。
- 红黑树。
- 節點大小平衡樹。
的。其他类型 [编辑]
- 跳表，一种支持平衡树大多数操作的数据结构
|
||||||||||||||||||||||||||
