紅黑樹和二叉樹的區別

　　1、紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間複雜度相差不大的情況下，保證每次插入最多隻需要三次旋轉就能達到平衡，實現起來也更為簡單。

　　2、平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之後需要旋轉的次數不能預知。

　　樹是一種簡單的非線性結構，所有元素之間具有明顯的層次特性。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點，簡稱樹的根。每一個結點可以有多個後件，稱為該結點的子結點。沒有後件的結點稱為葉子結點。二叉樹是每個節點只能最多擁有2個子節點的樹結構，這些子節點一般被視為左子節點和右子節點。

　　紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間複雜度相差不大的情況下，保證每次插入最多隻需要三次旋轉就能達到平衡，實現起來也更為簡單。

　　平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節點之後需要旋轉的次數不能預知。

　　紅黑樹：是一種自平衡二叉查詢樹，是在計算機科學中用到的一種資料結構，典型的用途是實現關聯陣列。紅黑樹是在１９７２年被髮明，當時被稱為平衡二叉Ｂ樹。紅黑樹是一種特化的ＡＶＬ樹（平衡二叉樹），都是在進行插入和刪除操作時透過特定操作保持二叉查詢樹的平衡，從而獲得較高的查詢效能。它雖然是複雜的，但它的最壞情況執行時間也是非常良好的，並且在實踐中是高效的： 它可以在Ｏ時間內做查詢，插入和刪除，這裡的ｎ 是樹中元素的數目。