一、紅黑樹（Red-Black Tree）是二叉搜索樹（Binary Search Tree）的一種。二叉搜索樹在最壞的情況下可能會變成一個鏈表（當所有節點按從小到大的順序依次插入後）。這種低效產生的原因是樹沒有維持一定的平衡性，要提高搜索效率，就要想辦法來維持樹左邊的平衡，也就是要盡時降低樹的高度，可行的做法就是用一些策略在每次修改樹的內容之後都調整樹的結構，使之滿足一定的平衡條件。其中一種滿足一定平衡條件而且目前應用廣泛的是紅黑樹。它可以在每一次插入或刪除節點之後都會花O（log N）的時間來對樹的結構作修改，以保持樹的平衡。而紅黑樹的查找方法與二叉搜索樹完全一樣，也能夠在O(log N)時間上完成。而紅黑樹的插入和刪除節點的的方法只是在原二叉搜索樹搜索和刪除算法之後經過一定的過程來維持紅黑樹的性質不變。
紅黑樹的每個節點上的屬性除了有一個key、3個指針：parent、left、right以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑,當然也可以再加一些以key來索引的數據。而紅黑樹除了具有二叉搜索樹的所有性質之外，還具有以下5點性質：
1. 每個節點是黑色的或是紅色的。
2. 根節點是黑色的。
3. 空節點是黑色的（紅黑樹中，根節點的parent以及所有葉節點left、right都不指向NULL，而是指向一個定義好的空
