iT邦幫忙

2021 iThome 鐵人賽

DAY 10
1
Software Development

少女人妻在廚房裡想不通的演算法系列 第 10

【在廚房想30天的演算法】Day 10 資料結構:樹 Tree

Aloha~!又是我少女人妻Uerica!這陣子家人住院,從急診到加護病房再到普通病房,看到形形色色的病人,不免讓我不停思考人生追求是什麼,每個生病的人都長一樣,一樣的病人服、一樣的病床、一樣的不舒服,完全看不出這些人有多少財富或多高的成就。但我能看到的是他跟家人或朋友感情好不好,有沒有好好對待自己的身體,所以要好好愛自己還有身邊的人啊!


好的來進入主題吧~!

樹 (Tree)

樹是一種階層關係的資料結構,分支型的結構就像樹幹與樹枝的關係一樣。生活中常見的例子有家族族譜、決策模型等。

Vy6Esj9

樹的定義與特性

樹是由一個根節點(Root)開始發展,在樹狀結構中的最基本單位,稱為節點
(Node),而分支出去的節點稱為子節點(Child)。樹是沒有環的結構,且任意兩節點間只有一個唯一路徑,若隨意刪除其中一個枝 (Branch),就會變兩個樹。

  • 節點 (Node):樹狀結構中每一個資料元素都稱為節點。
  • 枝 (Branch):節點向下延伸擴展的所用到的枝。
  • 根節點 (Root):根節點具有唯一性,是整個樹狀結構最上層的樹根。
  • 葉節點 (Leaf):節點之下都沒有子節點稱為葉節點(像樹葉的葉子)。
  • 非終端點 (Non-terminal Nodes):除了葉節點外的其他節點。
  • 祖先節點 (Ancenstors) 與子孫節點 (Descendant):一個節點往上走一直到根節點之前,所經過的節點都稱為祖先節點。一個節點往下走,到葉節點前,每個經過的節點都稱為子孫節點。
  • 父節點 (Parent)與子節點 (Child):被分支的節點上方一個節點稱為此節點的父節點,而節點向下分支出的節點稱為子節點。如同父子關係般,父節點通常只有一個,子節點可以有一個或多個。
  • 兄弟節點 (Siblings):同一個父節點的其他節點,稱為兄弟節點。
  • 分支度 (Dregree):每個節點所擁有的子節點數。
  • 階層 (Level):從樹根開始,向下延伸的層級。
  • 樹深 (Depth):節點與節點間的距離。根節點深度為 0 。

DA6gmq3

樹的類型

一般的樹都是有序樹 (OrderedTree),指樹中任意節點與子節點之間是有順序關係的,每個節點的子節點是從左到右有次序的,另外還有無序樹(UnoderedTree),又稱「自由樹」,樹中任意節點的子節點之間沒有順序關係。以下介紹的都屬於有序樹。

二元樹(Binary tree)

樹依照不同的分支度可以區分成很多種類,但在資料結構中最廣泛使用的樹狀結構是二元樹。二元樹是指樹中的每一個節點 (Node) 最多只分支出2個子節點,,即分支度小於或等於 2 。二元樹的節點所分支的子節點,在左邊的稱為左子樹 (Left Sub-tree)、右邊則稱為右子樹 (Right Sub-tree)。

R8cUbjS

依照分支與節點的不同,還有下列幾種表示:

歪斜樹(Skewed Tree)
樹的每個節點的分支都只有左節點,或都只有右節點。
xENSQVc

嚴格二元樹 (Strictly binary tree)
指的是每個節點的子節點只能是 0 或 2 的二元樹,簡單來說就是除了葉節點以外,每個節點都有兩個子節點。
4PSRWVE

完滿二元樹 (Full Binary Tree)
又稱 Perfect Binary Tree ,如果樹的高度是 k 節點,那節點的個數就是 2 的 k - 1 次方,是具有最多節點的二元樹。除了葉節點外,每個節點都有兩個子節點。
CS4WK5s

完整二元樹 (Complete Binary Tree)
指的是在一個樹中,除了最後一層外,其餘的節點都有兩個子節點,且遵循由上而下、由左至右排列。
VMFEKUE

二元搜尋樹(Binary Search Tree)

二元搜尋數其實也算二元樹的一種,只是在節點的資料排列上有些需遵循的特性。二元樹搜尋樹的每一個節點值都不相同,而每一個節點的資料大於左邊的子節點、小於右子節點的資料值。若左右都沒有子節點則是該層的最大或最小值。
lfMn7OF

AVL樹 (Adelson-Velsky and Landis Tree)

AVL樹是屬於二元搜尋樹的一種,所以符合二元搜尋樹的所有特性。但除了二元搜尋樹的特性外,AVL還必須符合每一個節點的的左邊子節點的高度-右邊子節點的高度只能是 -1、0、1,所以 AVL樹 也是平衡樹的一種,此特性讓整個樹不會長歪,在搜尋時的速度會更快。

紅黑樹(Red–black tree)

紅黑樹也是二元搜尋樹的一種,且與 AVL 樹的作用類似,也是為了要保持樹狀結構的平衡,而紅黑樹遵循以下特性:

  • 樹上的每個節點 (node) 只能是紅色或黑色
  • 根節點 (root) 一定要是黑色
  • 葉節點 (leaf) 一定要是黑色的空值 (NULL)
  • 紅色節點的兩個子節點 (child) 一定要是黑色 (亦即不能有兩個紅色節點相連,注意:黑色節點的子節點顏色沒有限制)
  • 從任何節點出發,其下至葉節點所有路徑的黑色節點數目要相同

參考資料:

[資料結構] CH8. AVL Trees

用JavaScript學習資料結構與演算法 8:樹、 二元搜尋樹

樹狀結構_維基百科

資料結構的樹與二元樹(Trees and Binary Trees)

演算法筆記:Tree

Red-Black Tree / 紅黑樹

紅黑樹(Red Black Tree)介紹

Binary Tree: Intro(簡介)

JavaScript 學演算法(十二)- 樹 & 二元樹


好的今天就到這邊啦~記得多關心身邊的人喔~明天見啦掰掰!


上一篇
【在廚房想30天的演算法】Day 09 資料結構:佇列 Queue
下一篇
【在廚房想30天的演算法】Day 11 資料結構:圖 Graph
系列文
少女人妻在廚房裡想不通的演算法30

尚未有邦友留言

立即登入留言