AVL樹和紅黑樹差別

二叉查找樹：

二叉查找樹就是左結點小于根節點，右結點大于根節點的一種排序樹，也叫二叉搜尋樹。也叫BST。二叉查找樹比普通樹查找更快，查找、插入、删除的時間複雜度為O（logN）。但是二叉查找樹有一種極端的情況，就是會變成一種線性連結清單似的結構。此時時間複雜度就變味了O（N）。(為了解決這種情況，出現了二叉平衡樹)

平衡二叉樹：

平衡二叉樹全稱平衡二叉搜尋樹，也叫AVL樹。是一種自平衡的樹。

AVL樹也規定了左結點小于根節點，右結點大于根節點。并且還規定了左子樹和右子樹的高度差不得超過1。這樣保證了它不會成為線性的連結清單。AVL樹的查找穩定，查找、插入、删除的時間複雜度都為O（logN），但是由于要維持自身的平衡，是以進行插入和删除結點操作的時候，需要對結點進行頻繁的旋轉。

AVL樹每一個節點隻能存放一個元素，并且每個節點隻有兩個子節點。當進行查找時，就需要多次磁盤IO，（資料是存放在磁盤中的，每次查詢是将磁盤中的一頁資料加入記憶體，樹的每一層節點存放在一頁中，不同層資料存放在不同頁。）這樣如果需要多層查詢就需要多次磁盤IO。為了解決AVL樹的這個問題，就出現了B樹

為什麼B類樹可以進行優化呢？我們可以根據B類樹的特點，構造一個多階的B類樹，然後在盡量多的在結點上存儲相關的資訊，保證層數盡量的少，以便後面我們可以更快的找到資訊，磁盤的I/O操作也少一些，而且B類樹是平衡樹，每個結點到葉子結點的高度都是相同，這也保證了每個查詢是穩定的。

紅黑樹：

紅黑樹也叫RB樹，RB-Tree。是一種自平衡的二叉查找樹，它的節點的顔色為紅色和黑色。它不嚴格控制左、右子樹高度或節點數之差小于等于1。也是一種解決二叉查找樹極端情況的資料結構。

紅黑樹規定了：

1.節點是紅色或黑色。

2.根節點是黑色。

3.每個葉子節點都是黑色的空節點（NIL節點）。

4 每個紅色節點的兩個子節點都是黑色。也就是說從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)。

5.從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

紅黑樹在查找方面和AVL樹操作幾乎相同。但是在插入和删除操作上，AVL樹每次插入删除會進行大量的平衡度計算，紅黑樹是犧牲了嚴格的高度平衡的優越條件為代價，它隻要求部分地達到平衡要求，結合變色，降低了對旋轉的要求，進而提高了性能。紅黑樹能夠以O(log2 n)的時間複雜度進行搜尋、插入、删除操作。此外，由于它的設計，任何不平衡都會在三次旋轉之内解決。