[TOC] ## 概述 紅黑樹是一種近似平衡的二叉查找樹 從`2-3`樹或`2-3-4`樹衍生而來 染色為紅或黑節點，來模仿`2-3`樹或`2-3-4`樹的3節點和4節點 2-3-4 樹對照實現的紅黑樹是普通的紅黑樹，而 2-3 樹對照實現的紅黑樹是一種變種，稱為左傾紅黑樹，其更容易實現。 使用平衡樹數據結構，可以提高查找元素的速度 ## 2-3 樹 `3階的B樹`(注：`B`為`Balance`平衡的意思) 它不是一棵二叉樹，是一棵三叉樹。具有以下特征： 1. 內部節點要么有1個數據元素和2個孩子，要么有2個數據元素和3個孩子，葉子節點沒有孩子，但有1或2個數據元素。 2. 所有葉子節點到根節點的長度一致。這個特征保證了完全平衡，非常完美的平衡。 3. 每個節點的數據元素保持從小到大排序，兩個數據元素之間的子樹的所有值大小介于兩個數據元素之間。  ### 樹插入元素  ### 左傾紅黑樹 左傾紅黑樹可以由`2-3`樹的二叉樹形式來實現。 其定義為： 1. 根節點的鏈接是黑色的。 2. 紅鏈接均為左鏈接。 3. 沒有任何一個結點同時和兩條紅鏈接相連 4. 任意一個節點到達葉子節點的所有路徑，經過的黑鏈接數量相同，也就是該樹是完美黑色平衡的。比如，某一個節點，它可以到達5個葉子節點，那么這5條路徑上的黑鏈接數量一樣。