天天看點
傳回

前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

資料結構 Data Structure Visualizations

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉樹（Binary Tree）

定義

二叉樹（binary tree）是指樹中節點的度不大于2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分别稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹

特點

  • 二叉樹是每個節點最多有兩個子節點的樹
  • 二叉樹的葉子節點有0個位元組點，二叉樹的根節點或者内部節點有一個或者兩個位元組點。
    前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

相關術語

①結點：包含一個資料元素及若幹指向子樹分支的資訊 。

②結點的度：一個結點擁有子樹的數目稱為結點的度 。

③葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點 。

④分支結點：也稱為非終端結點，度不為零的結點稱為非終端結點 。

⑤樹的度：樹中所有結點的度的最大值 。

⑥結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位于第L層，則其子節點位于第L+1層 。

⑦樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度 。

⑧有序樹：如果樹中各棵子樹的次序是有先後次序，則稱該樹為有序樹 。

⑨無序樹：如果樹中各棵子樹的次序沒有先後次序，則稱該樹為無序樹 。

⑩森林：由m（m≥0）棵互不相交的樹構成一片森林。如果把一棵非空的樹的根結點删除，則該樹就變成了一片森林，森林中的樹由原來根結點的各棵子樹構成 。

二叉搜尋樹（Binary Search Tree）

定義

二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜尋樹。是資料結構中的一類。在一般情況下，查詢效率比連結清單結構要高。

特點

一棵空樹，或者是具有下列性質的二叉樹：

（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；

（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；

（3）左、右子樹也分别為二叉排序樹；

（4）沒有鍵值相等的結點。

前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

BST樹的搜尋

從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那麼就命中；否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字.

如果BST樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那麼B樹的搜尋性能逼近二分查找；但它比連續記憶體空間的二分查找的優點是，改變BST樹結構（插入與删除結點）不需要移動大段的記憶體資料，甚至通常是常數開銷；

前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

但BST樹在經過多次插入與删除後，有可能導緻不同的結構：

前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

右邊也是一個BST樹，但它的搜尋性能已經是線性的了；同樣的關鍵字集合有可能導緻不同的樹結構索引；是以，使用BST樹還要考慮盡可能讓BST樹保持左圖的結構，和避免右圖的結構，也就是所謂的“平衡”問題；

平衡二叉樹（AVL Tree）

平衡樹(Balance Tree，BT) 定義

平衡樹(Balance Tree，BT) 指的是，任意節點的子樹的高度差都小于等于1。常見的符合平衡樹的有，B樹（多路平衡搜尋樹）、AVL樹（二叉平衡搜尋樹）等。平衡樹可以完成集合的一系列操作, 時間複雜度和空間複雜度相對于“2-3樹”要低，在完成集合的一系列操作中始終保持平衡，為大型資料庫的組織、索引提供了一條新的途徑。

特點

  • 所有節點的左右子樹的高度差小于1的二叉樹。

如下圖

根節點左邊高度是3，因為左邊最多有3條邊；右邊高度而2，相差1.

根節點左邊的節點50的左邊是1條邊，高度為1，右邊有兩條邊，高度為2，相差1。

前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

紅黑樹（Red-Black Tree）

定義

  • 紅黑樹（Red Black Tree） 是一種自平衡二叉搜尋樹，是在計算機科學中用到的一種資料結構，典型的用途是實作關聯數組.
  • 紅黑樹是一種特化的AVL樹（平衡二叉樹），都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能.

特點

  1. 節點是紅色或黑色
  2. 性質2. 根節點是黑色
  3. 所有葉子都是黑色。（葉子是NUIL節點）
  4. 每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
  5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點
前言--03---二叉樹、二叉搜尋樹、平衡二叉樹、紅黑樹、資料結構 Data Structure Visualizations二叉樹（Binary Tree）二叉搜尋樹（Binary Search Tree）平衡二叉樹（AVL Tree）紅黑樹（Red-Black Tree）

分析:

紅黑樹會主動平衡樹的結構,使樹兩邊資料盡量達到平衡.始終保證左子節點數 < 父節點數 < 右子節點數的規則。

但 紅黑樹 在大資料場景下面,樹的高度不可控,那麼存在葉子節點的資料,查找起來效率不會特别高.會多次IO讀取磁盤中的資料(索引一般儲存在磁盤當中).

應用

  • 廣泛用于C++的STL中,map和set都是用紅黑樹實作的.
  • 著名的linux程序排程Completely Fair Scheduler,用紅黑樹管理程序控制塊,程序的虛拟記憶體區域都存儲在一顆紅黑樹上,每個虛拟位址區域都對應紅黑樹的一個節點,左指針指向相鄰的位址虛拟存儲區域,右指針指向相鄰的高位址虛拟位址空間.
  • IO多路複用epoll的實作采用紅黑樹組織管理sockfd，以支援快速的增删改查.
  • ngnix中,用紅黑樹管理timer,因為紅黑樹是有序的,可以很快的得到距離目前最小的定時器.
  • java中TreeMap的實作.
資料結構和算法
上一篇: 資料結構：樹與二叉樹_二叉樹_定義
下一篇: 非二叉樹轉換成二叉樹

繼續閱讀