二叉樹，二叉查找樹

• 當沒有父節(jié)點時（即祖宗節(jié)點），父節(jié)點地址為null

  當沒有左子節(jié)點時，左子節(jié)點地址為null

  當沒有右子節(jié)點時，右子節(jié)點地址為null

• 根節(jié)點（或稱祖宗節(jié)點）的右側的所有結點稱為右子樹；左側稱為左子樹

• 特點

  • 只能有一個根節(jié)點，每個節(jié)點最多支持2個直接子節(jié)點

  • 節(jié)點的度：節(jié)點擁有的子樹的個數(shù)，二叉樹的度不大于2；葉子節(jié)點度為0的節(jié)點，也稱之為終端節(jié)點

  • 高度：葉子節(jié)點的高度為1；葉子節(jié)點的父節(jié)點高度為2；根節(jié)點的位置最高

    即從葉子節(jié)點往上數(shù)層數(shù)

  • 層：根節(jié)點在第一層，往下數(shù)依次類推

  • 兄弟節(jié)點：擁有共同父節(jié)點的節(jié)點互稱為兄弟節(jié)點（同層不同父的也可以認為是堂兄節(jié)點）

• 二叉查找樹（又稱二叉排序樹或二叉搜索樹）

  大的節(jié)點到小的節(jié)點，依次從右往左排

  • 特點：
    1. 每一個節(jié)點上最多有兩個子節(jié)點
    2. 左子樹上所有節(jié)點的值都小于根節(jié)點的值
    3. 右子樹上所有節(jié)點的值都大于根節(jié)點的值
  • 目的：提高檢索數(shù)據(jù)的性能
  • 二叉查找樹添加節(jié)點規(guī)則：
    1. 小的存左邊
    2. 大的存右邊
    3. 一樣的不存
  • 二叉查找樹是一種增刪改查都很快的數(shù)據(jù)結構，趨近于完美

平衡二叉樹

• 普通二叉查找樹的弊端：在添加元素時可能出現(xiàn)”變成鏈表“的情況，即根節(jié)點和所有子節(jié)點的度為1，名義上是二叉樹，實際上已經(jīng)變成了鏈表，操作效率瞬間變低

• 為解決二叉查找樹的弊端，引入平衡二叉樹的概念，在滿足二叉查找樹的條件下，盡可能的讓度為2，使得二叉樹的高度變得矮小，盡可能的均勻，性能進一步提高

• 平衡二叉樹的要求

  • 任意節(jié)點的左右兩個子樹的高度差不超過1，任意節(jié)點的左右兩個子樹都是一棵平衡二叉樹

• 平衡二叉樹在添加元素后可能導致不平衡

  • 基本策略是進行左旋，或者右旋保證平衡

    • 左旋

      [圖片上傳失敗...(image-f55cc8-1647070245558)]

    • 右旋

      [圖片上傳失敗...(image-1e6637-1647070245558)]

  • 旋轉的四種情況

    • 左左
      • 當根節(jié)點左子樹的左子樹有節(jié)點植入，導致二叉樹不平衡（右旋）
    • 左右
      • 當根節(jié)點左子樹的右子樹有節(jié)點插入，導致二叉樹不平衡
        • 以不平衡的節(jié)點為支點，先左旋再右旋（參考下方右左示意圖）
    • 右右
      • 當根節(jié)點右子樹的右子樹有節(jié)點插入，導致二叉樹不平衡（左旋）
    • 右左
      • 當根節(jié)點右子樹的左子樹有節(jié)點插入，導致二叉樹不平衡
        • 以不平衡的節(jié)點為支點，先右旋再左旋
        • image.png

紅黑樹

• 紅黑樹是一種自平衡的二叉查找樹，是計算機科學中的一種數(shù)據(jù)結構

• 又稱平衡二叉B樹

• 每一個節(jié)點可以是紅或黑，紅黑樹不是通過高度平衡的，它的平衡是通過“紅黑規(guī)則”進行實現(xiàn)的

• 紅黑規(guī)則

  • 每一個節(jié)點或紅或黑，根節(jié)點必須是黑色的
  • 如果一個節(jié)點沒有子節(jié)點或者父節(jié)點，則該節(jié)點相應的指針屬性值為Nil，這些Nil視為葉節(jié)點，葉節(jié)點是黑色的
  • 如果某一個節(jié)點是紅色的，那么它的子節(jié)點必須是黑色的（不能出現(xiàn)兩個紅色節(jié)點相連的情況）
  • 對每一個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上，均包含相同數(shù)目的黑色節(jié)點

• 相比普通二叉樹，紅黑樹的構成多了一個區(qū)域標記顏色值

• 添加節(jié)點

  • 添加的節(jié)點的顏色，可以是紅色，也可以是黑色

  • 默認使用紅色效率更高

    因為紅節(jié)點不在紅黑規(guī)則的路徑算法里，默認添加使用黑色會導致需要大量的調(diào)整工作以保障每次添加后平衡

  • 當出現(xiàn)子節(jié)點的父節(jié)點是紅色，即兩個紅色相連接時，判斷：父節(jié)點是否為紅色，叔叔節(jié)點（父節(jié)點的兄弟節(jié)點）是否為紅色；判斷得出父節(jié)點和叔叔節(jié)點均為紅時

    1. 將父節(jié)點設為黑色；將叔叔節(jié)點設為黑色
    2. 將祖父節(jié)點（父節(jié)點和叔叔節(jié)點的父節(jié)點）設為紅色
    3. 判斷祖父節(jié)點是否為根節(jié)點，是根節(jié)點時將根節(jié)點再次變?yōu)楹谏?/li>

  • 當出現(xiàn)父節(jié)點是紅色，叔叔節(jié)點是黑色

    1. 將父節(jié)點設為黑色
    2. 將祖父節(jié)點設為紅色
    3. 以祖父節(jié)點為支點進行旋轉

• 紅黑樹的增刪改查性能都非常好

總結

• 棧：后進先出，先進后出
• 隊列：先進先出，后進后出
• 數(shù)組：內(nèi)存連續(xù)區(qū)域，查詢快，增刪慢
• 鏈表：元素是游離的，查詢慢，首位操作極快
• 二叉樹：永遠只有一個根節(jié)點，每個節(jié)點不超過2個子節(jié)點的樹
• 查找二叉樹：小的放左邊，大的放右邊，極端情況下，樹的高度過高使得查詢性能變差
• 平衡查找二叉樹：讓樹的高度差不大于1，增刪改查效率都比較高
• 紅黑樹：基于紅黑規(guī)則實現(xiàn)的自平衡的排序二叉樹，增刪改查效率都很高