平衡二叉树

Question

什么是二叉树(或二叉树族)的名称，它是平衡的，并且对于其高度具有可能的最小节点数？

Answer 1

它被称为斐波那契树

Answer 2

平衡二叉树

(数据结构)

定义:一种binary tree，其中leaf离root的距离不超过一定的量。在插入或删除node之后，树可能会通过“旋转”重新平衡。

泛化(我是一种...) binary tree。

专业化(...是我的一种。) AVL tree，red-black tree，B-tree，balanced binary search tree。

聚合子对象(...是me的一部分或在me中使用。) left rotation，right rotation。

另请参见BB(α) tree、height-balanced tree。

-- http://www.itl.nist.gov/div897/sqg/dads/HTML/balancedbitr.html

Answer 3

是一个高度为log(n)的平衡树(这是二叉树可能的最低高度)。

类似数据结构的另一个实现是Red Black Tree。

这两棵树都实现了O(log(n))中的所有操作。