平衡二叉樹

什麼是二叉樹的名稱（或二叉樹的家族），它是平衡的，並且其最小節點數爲其高度可能？平衡二叉樹

來源

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

回答

相關問題