文章目錄

• • 為什么要有AVL樹
  • AVL的旋轉有哪幾種？
  • 為什么有了平衡樹還要有紅黑樹
  • 紅黑樹的特點
  • B 樹
  • B+ 樹
  • • 1：treenode
    • 2：插入
    • 3：擴容
  • B+ 樹索引和 B樹索引

為什么要有AVL樹

• 當出現極端的情況，樹的節點可能會近似與鏈表的形式，使得時間復雜度近似與 O（n）

AVL的旋轉有哪幾種？

• 左左型 ：節點都偏向左邊
  • 順時針旋轉兩個節點，使得自己的左子節點成為根節點，而自己成為右子節點
• 右右型：節點都偏向右邊
  • 逆時針旋轉兩個節點，使得自己的右子節點成為根節點，而自己成為左子節點
• 右左型：節點是偏向右邊，但是最底下的葉節點偏向左邊
  • 將它轉化為右右型號
  • 再進行右右型的旋轉
• 左右型：節點是偏向左邊，但是最底下的爺節點是偏向右邊
  • 將他轉化為左左型號
  • 再進行左左型的旋轉

為什么有了平衡樹還要有紅黑樹

• 平衡樹解決了在極端的情況下變成鏈表的情形，使得任意的兩個葉子節點的深度小于等于1。
• 這個要求是在是太嚴格了，基本上每次新增插入，或者是刪除的時候，都會破壞這個要求
• 使得每次都要進行左旋或者是右旋來調整，進而成為一顆平衡二叉樹
• 如果是在刪除，插入場景很多的情況下，AVL樹的性能會大大的折扣

紅黑樹的特點

• 是一種二叉搜索樹，任意的左子節點都比自己小，右子節點都比自己大
• 根節點是黑色的
• 每個葉子節點都是黑色的，并且里面不存數據，為空
• 任意兩個相鄰的節點不能是紅色的，也就是，紅節點是被黑節點分割開來
• 每個節點，從該節點到其可達的葉子節點的所有路勁，都包括相同數量的黑色節點

B 樹

• 每個節點中都存放著信息，所以查詢的時候，最快為O（1），最多為O（log n）
• 他的葉節點沒有指針進行相連，不適合與范圍查詢

B+ 樹

• B+ 樹是為了磁盤設計的一種平衡查找樹，所以的數據節點都放在同一層的葉節點中，并且各個葉節點有指針連接
• 有K個字數的節點就含有K 個元素，每個元素不放數據，只放索引，數據統一放在葉節點之中
• 所有的葉節點包含了全部的數據信息，以及指向數據的指針，并且數據是按照從小到大依次進行排列的。
• 所有的中間節點都同時存在于子節點中，在子節點是最大，最小元素
• B+ 樹是從下到上查找，而B 樹是從下到上查找
• 單一節點存儲更多的元素，使得樹變得矮胖了，樹下的分支變多了，減少I/O 的次數
• 所有的查詢都要查詢到葉子節點，查詢性能穩定
• 所有的葉子節點都是按序連接的，適合與范圍查詢

1：treenode

• treenode 是繼承了node結構，在node基礎上加了幾個字段
• 指向父節點的，指向左子節點，指向右子節點，還有表示顏色的

2：插入

• 找到一個合適的插入點，就是找到插入節點的父節點，紅黑樹滿足二叉搜索樹的特性，需要進行一次的平衡操作
• 插入會打破平衡
• 插入一定是紅色的節點，碰到父節點是黑色的，樹不會失衡

3：擴容

• treenode保持著一個 next的字段，查詢的時候不適用
• 但是新增或者是刪除節點的時候，仍然需要維護這個鏈表
• 鏈表方便split拆分這個紅黑樹的時候，拆分為高位鏈和地位鏈
• 高位鏈的數據，最重要存放到新表中去
• 拆分出來的鏈表，需要看一下他的長度

B+ 樹索引和 B樹索引

• 由于關系型數據庫和非關系型數據庫數據設計方式的不同，導致關系型數據庫常常用到數據的遍歷，而非關系型用到表的單一查詢
• 所以在MySQL 數據庫中，使用B+ 樹作為索引，而在mongodb中，B 樹作為索引

總結

以上是生活随笔為你收集整理的AVL,B,B+,红黑的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。