二叉搜索樹的缺陷

當(dāng)插入的數(shù)據(jù)是有序的數(shù)據(jù)，就會(huì)造成二叉搜索樹的深度過大。比如原二叉搜索樹右 11 7 15 組成，如下圖所示：

當(dāng)插入一組有序數(shù)據(jù)：6 5 4 3 2就會(huì)變成深度過大的搜索二叉樹，會(huì)嚴(yán)重影響二叉搜索樹的性能。

非平衡樹

• 比較好的二叉搜索樹，它的數(shù)據(jù)應(yīng)該是左右均勻分布的；
• 但是插入連續(xù)數(shù)據(jù)后，二叉搜索樹中的數(shù)據(jù)分布就變得不均勻了，我們稱這種樹為非平衡樹；
• 對(duì)于一棵平衡二叉樹來說，插入/查找等操作的效率是O（logN）；
• 而對(duì)于一棵非平衡二叉樹來說，相當(dāng)于編寫了一個(gè)鏈表，查找效率變成了O（N）;

樹的平衡性

為了能以較快的時(shí)間O（logN）來操作一棵樹，我們需要保證樹總是平衡的：

• 起碼大部分是平衡的，此時(shí)的時(shí)間復(fù)雜度也是接近O（logN）的；
• 這就要求樹中每個(gè)節(jié)點(diǎn)左邊的子孫節(jié)點(diǎn)的個(gè)數(shù)，應(yīng)該盡可能地等于右邊的子孫節(jié)點(diǎn)的個(gè)數(shù)；

常見的平衡樹

• AVL樹：是最早的一種平衡樹，它通過在每個(gè)節(jié)點(diǎn)多存儲(chǔ)一個(gè)額外的數(shù)據(jù)來保持樹的平衡。由于AVL樹是平衡樹，所以它的時(shí)間復(fù)雜度也是O（logN）。但是它的整體效率不如紅黑樹，開發(fā)中比較少用。
• 紅黑樹：同樣通過一些特性來保持樹的平衡，時(shí)間復(fù)雜度也是O（logN）。進(jìn)行插入/刪除等操作時(shí)，性能優(yōu)于AVL樹，所以平衡樹的應(yīng)用基本都是紅黑樹。

總結(jié)

以上是生活随笔為你收集整理的认识平衡树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。