平衡二叉树

什么是二叉树的名称（或二叉树的家族），它是平衡的，并且其最小节点数为其高度可能？平衡二叉树

来源

2010-01-03 Moody

只要是迂腐......节点的树高N的N个节点的最小数量（即：每个节点有一个孩子），并不平衡。也许你的意思是“节点数量的最小高度”？ – Tordek 2010-01-03 11:55:32

@穆迪是否必须是搜索树？ – 2010-01-03 12:02:57

@Tordek：问题中的措词是有效的。高度4的平衡二叉树的最小节点数为8，高度5为16，高度6为32，...，高度n为2 ^（n-1）。不过，我不确定这是否是穆迪想要的。 – 2010-01-03 12:08:34

这就是所谓的斐波那契树

来源

2010-01-22 03:58:52 Vlad

AVL是平衡树的log（n）高度（这是二叉树的高度最低可能）。
类似数据结构的另一种实现是Red Black Tree。

两个树实现O（日志（n））的所有操作。

来源

2010-01-03 11:39:07 Elisha

AVL Tree是你一直在寻找的东西。

维基百科：

在计算机科学中，一个AVL tree是一个平衡树，它是被发明第一个这样的数据结构。在AVL树中，任何节点的两个子子树的高度相差最多一个;因此，它也被称为高度平衡。在平均和最差情况下，查找，插入和删除都需要O（log n）时间，其中n是操作之前树中节点的数量。插入和删除可能需要通过一个或多个树轮旋转来重新平衡树。

来源

2010-01-03 11:40:56

平衡二叉树

（数据结构）

定义：binary tree其中没有leaf是超过一定量远离root比任何其他。在插入或删除node后，该树可能会因“旋转”而重新平衡。

泛化（我是那种...） binary tree。

专精（...是一种我的。） AVL tree，red-black tree，B-tree，balanced binary search tree。

聚合子（...是我的一部分或在我身上使用。） left rotation，right rotation。

也BB(α) tree，height-balanced tree见。

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

来源

2010-01-03 11:44:25

回答

相关问题