平衡二叉搜索樹和二叉搜索樹有什麼區別？

對不起，如果這是一個非常基本的問題，但我對樹木相當陌生，因此，這個疑問最近困擾着我。平衡二叉搜索樹和二叉搜索樹有什麼區別？

二叉搜索樹和平衡二叉搜索樹有什麼區別？並非每個BST（二進制搜索樹）已經是BBST（平衡BST）？

2015-06-24 John Lui

請參閱[this SO post]（http://stackoverflow.com/questions/8015630/definition-of-a-balanced-tree）瞭解平衡二叉樹的一個很好的討論。 –

不同的是，平衡二叉樹的可能最小高度

2015-06-24 13:27:28

「平衡」是一個二叉樹可以有一個屬性。它通常意味着樹中的每個節點在其下面的每個子樹上具有大致相同數量的後代節點。它更具體地意味着樹的「高度」已經最小化。

對於不是「平衡」的樹，可能有一個二叉樹，其中所有「左」子節點都爲空，並且它還具有「二叉搜索樹」的屬性。這被稱爲退化樹，因爲它在結構上更像鏈接列表，因此將具有O（N）搜索時間而不是O（log（N））。

2015-06-24 16:26:52 Daniel

基本上，從外行的角度來講，我可以說一棵平衡樹是左子樹和右子樹的高度相差最多1倍的樹嗎？而在BST，這可能不一定是真的？ –

這是「必要但不夠」。它必須包括「每棵子樹也是一棵平衡樹」 – Daniel

回答