iT邦幫忙

4

資料結構觀念統整,無程式碼解說常見觀念: 二分搜索、linked list、stack、queue、graph、tree、二分搜索樹、heap、Hash Table

這邊將常見的資料結構概念統整為一篇

二分搜索(Binary Search)

二分搜尋(binary search)是一個經典的演算法,
在資料有排序過的情形下,
可以用O(log n)的時間複雜度找到資料

首先,我們思考一個情境:
假設現在大學期末考剛考完,
你要去找你的助教領取考卷,
但是你的助教說他很忙,
考卷按照學號順序由小到大排過,
放在隔壁的桌上,
請你自己去找,
那麼你該如何找到你的考卷呢?
(假設你的學號是107023456,考卷有200張)

線性搜尋(linear search)

https://ithelp.ithome.com.tw/upload/images/20200310/20117114YHWYTTPVta.png
最簡單的方法就是你一張張的把考卷拿起來看,
你最多把200張考卷都看完後,
你就能夠找到自己的考卷了

二分搜尋(binary search)- 適用在排序過的物件中尋找

但是既然考卷排過,有更聰明的策略,
你可以直接從中間的地方開始找,
比如說看第100張考卷好了,
假設第100張考卷上的學號是108021114
比你的學號大,那麼你的考卷一定是在前面100張裡面,
一下子你就可以少看一半的考卷了…

以此類推,每次都可以少搜索一半的數量,
可以大大的節省找東西的時間

linked list 與 array

array可以用來記錄一連串相同型別的資料,
例如說c++語言寫int array[4]={1,5,8,3};
指的就是連續存放4個整數的array,如圖:

https://ithelp.ithome.com.tw/upload/images/20200321/20117114e8vBG57QgC.png

那麼假設我們原本有一個長度為n的array,
我們想要在第1個位置插入一個元素,
那麼我們就必須把後面的元素都往後移動一格,
大概要O(n)的時間,相當耗時

https://ithelp.ithome.com.tw/upload/images/20200321/20117114CWDsQW5epu.png

刪除元素也需要O(n)的時間

https://ithelp.ithome.com.tw/upload/images/20200321/20117114OTZ34TdTWn.png

array在刪除/新增元素至中間時,
需要搬移整個陣列的元素,相當耗時

新朋友: linked list

那有沒有辦法讓資料隨便擺,我們仍然可以知道順序呢?(這樣就不必把資料搬來搬去)
答案是「記錄下一個資料的位置」

有點像是在玩尋寶遊戲的感覺,
假設有個人收集了小熊、小馬、小狗、小貓四種玩偶,

  • 小熊玩偶放在廚房
  • 小馬玩偶放在臥室
  • 小狗玩偶放在電視機上面
  • 小貓玩偶放在獎杯櫃

那麼他只要記得小熊玩偶放在廚房就好,
然後在小熊玩偶上面貼張紙條,寫說下一個玩偶放在臥室
到了臥室,找到小馬玩偶,上面再貼個紙條寫下一個玩偶電視機上面
這樣就可以知道所有的玩偶放哪裡了

概念上,大概長的像這樣:
https://ithelp.ithome.com.tw/upload/images/20200321/20117114aevTEQdBx4.png

我們用指標去記錄下一筆資料的位置在哪裡
(若你不知道指標可參考c/c++語言: 超好懂的指標(pointer)與參考(reference),歡迎初學者)

新增一個元素?

https://ithelp.ithome.com.tw/upload/images/20200321/201171142WTVYeKCG4.png

刪除一個元素?

https://ithelp.ithome.com.tw/upload/images/20200321/20117114MNKxWvnHS8.png

我們可以看到,不論是新增或刪除一個元素,
只要改變前後記錄的位置就好,
不必大幅搬動資料

stack- 最緊急的事情優先做

stack是一種先進後出的結構,
我們稱為FILO(First In, Last Out)的結構

它就像你把棉被整整齊齊的疊在衣櫃一樣,
如果你想要把放在最下層的棉被拿出來,
必須要先把放在上層的棉被拿出來,
才有辦法把下層的棉被拿出來

即是說,最後放進去stack裡面的東西,是最優先被處理的
其實日常生活也有類似這種stack的情形,
人會最優先處理最後發生的事
做事做到一半時,突然一件更緊急的事發生,
這時便會先做緊急的事,再回頭做原來的事項

例如:

  • 小明讀書讀到一半,突然接到暗戀同學打的電話,就先去接電話再回來讀書
  • 小華打電動打到一半,突然很想上廁所,只好先去上廁所再回來打電動

讀者可以想一想,日常生活中有沒有什麼情況也是屬於stack呢?

queue- 按照事情的先後順序做

queue則是一種先進先出的結構,
我們稱為FIFO(First In, Fisrt Out)的結構

queue其實非常好理解,
queue就好比日常生活在大賣場排隊結帳,
隊伍第一個人服務員就會優先幫他結帳

最先放進去queue裡面的東西,是最優先被處理的,
在日常生活可能比較常見這種模式,例如:

  • 期限較近的考試優先準備

Graph定義

graph是由一些頂點和一些邊所構成,
任意兩個頂點之間可以有邊相連或沒有
譬如說底下就是一張有四個頂點的graph:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114H05UJHm4U7.png

那麼graph有什麼用呢?
直接看一些生活上的例子應該會比較容易理解

一、表示地圖

譬如說這張是我隨意在網路上找的台灣地圖:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114CaAV7oT28K.png

我們可以把每個縣市想成是一個頂點,
如果在地圖上縣市有土地直接相鄰,
那麼兩個頂點之間就有邊相鄰,否則沒有

為了避免等一下圖畫的眼花瞭亂,
以「新北」、「桃園」、「新竹」、「金門」四個縣市做示範:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114MAhFwuK1Om.png

譬如說「新北」與「桃園」相鄰,畫一條線連起來,
「桃園」與「新竹」相鄰,畫一條線連起來,
「金門」不與任何縣市相鄰,所以不與其它頂點相連

其它例子還有日常生活會看到的「台北捷運圖」啦,
頂點是車站名,邊表示車站之間是否相鄰

二、朋友關係圖

譬如說我們可以把每個人想成是頂點,
如果兩個人之間互相認識,中間就連線
比如說:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114bMXOtqYJFd.png

我們可以用這張圖表示A, B, C, D, E, F在同一個班級裡上課,
其中A, B互相認識,
C, D, E互相認識,
F是邊緣人與其它人都不認識

所以其實graph是很生活化的東西,
讀者們也可以想想日常生活中有沒有什麼情況也是graph呢?

tree定義

講完了graph,那什麼是一個tree呢?
tree是一種特別的graph,
滿足兩個條件:

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

名詞解釋: 連通圖(connected graph)

連通圖很簡單,就是任兩個頂點都可以找到一條路徑把它連起來,
比如說台灣本島地圖(為了方便,只取「新北」、「桃園」、「新竹」三個縣市來畫)

https://ithelp.ithome.com.tw/upload/images/20200329/201171142SM3XEoGv0.png

儘管「新北」、「新竹」這兩個縣市沒有邊直接連接,
但是要從「新北」到「新竹」,可以走「新北->桃園->新竹」的路徑,
所以這張圖是連通的,
反之,若是加上離島(比如: 金門)的話圖就是不連通的,
因為金門沒有路徑到達其它的縣市

https://ithelp.ithome.com.tw/upload/images/20200329/20117114iwNpsoMFX8.png

名詞解釋: 循環(cycle)

cycle就是頂點之間的連接形成了一個圈,比如:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114c8dU9MHjhl.png

了解基礎名詞解釋後,
我們來看看為什麼tree要滿足這兩個條件:

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

這邊你可以將樹與現實中的樹聯想在一起,
https://ithelp.ithome.com.tw/upload/images/20200329/20117114aZXDHjujYx.png

因為樹由根開始生長,所以一定是連通的,
不可能隔空生長出葉子,
沒有循環(cycle)像是保證生長的順序,
一定是從「根->樹幹->樹枝->葉子」這樣生長,
葉子不會長出根

你看若是我將樹的分岔點都想成是頂點,
是不是就很像一開始介紹的一種graph呢?

https://ithelp.ithome.com.tw/upload/images/20200329/20117114WWemK6yXF1.png

有根樹 (rooted tree)

在資料結構中討論的有根樹
有個特別的頂點叫做
可能為了表示由上往下生長(如父親、兒子的關係),
的位置是放在最上面的,
與現實中的樹相反

https://ithelp.ithome.com.tw/upload/images/20200329/20117114cfNGEQYSx1.png

名詞解釋: parent, chlidren

而節點之間的關係,也可以用parent, chlidren來互稱,
比如說這樣子的一棵樹:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114fJ1bXfVzxz.png

那麼我們稱B是A的chlid,A是B的parent,
E是B的chlid,B是E的parent

講到這裡,你是不是覺得跟公民課本上會看到的某張圖有點相似呢?
沒錯,就是家族樹

https://ithelp.ithome.com.tw/upload/images/20200329/20117114VHnqp9vq6Q.png

普通的家族樹滿足tree的定義,因為它

  • 是一個連通圖(connected graph)
  • 沒有循環(cycle)

但是在資料結構若是討論**有根樹 (rooted tree)**有更進一步的定義:

  • 除了root以外,每個頂點都恰好有一個parent
  • 每個頂點可以有多個chlidren
  • 沒有chlidren的頂點稱為leaf(葉子)

因此像家族樹中爸爸和媽媽生出你並不滿足**有根樹 (rooted tree)**的定義,
**有根樹 (rooted tree)**與生活中對應的樹,
比較像是「只記錄男性的家族族譜」,如圖:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114TMa1RpCUFL.png

有向圖(directed graph)

有向圖(directed graph)與一般的graph差別在邊上有方向,
適合用來表示有單行道的地圖,
或是用來表達有先後關係的做事順序,
譬如以下幾個生活實例。

一、吃飯順序

你去餐廳吃飯的時候,
餐點可能會按照一定的順序出來,
用頂點 A->B 表示 A要先吃完,B餐點才會出現

譬如說本圖表示要先吃完開胃菜才可以吃湯和主菜,
湯和主菜都吃完了才可以吃甜點

至於飲料沒有限制,什麼時候吃都可以

https://ithelp.ithome.com.tw/upload/images/20200506/201171145seWRFa8px.png

二、修課順序

譬如說在修課的時候,部分課程會要求「先修課程」,
也可以用有向圖表達修課先後關係,
譬如說圖中表示要修「進修英文」之前要先修完「基礎英文一」和「基礎英文二」才可以修,
通識課程則不需要先修課程

https://ithelp.ithome.com.tw/upload/images/20200506/20117114kL2VjiAtfl.png

DAG(directed acyclic graph)

簡單介紹完directed graph,
那什麼是directed acyclic graph呢?
acyclic是沒有環的
如果一個directed graph裡面沒有cycle,
就稱為是一個DAG

cycle簡單來說,就是你可以從一個點出發,
經過一條路徑後又回到原點,
譬如說這張圖你可以從A出發,
走A->B->C->D->A繞一圈回到A,
這張圖就是有cycle的
https://ithelp.ithome.com.tw/upload/images/20200506/2011711485u4YJErQG.png

反之,若把圖改成這樣就沒有cycle
https://ithelp.ithome.com.tw/upload/images/20200506/20117114FYqtB0d7Xf.png

直觀來說,如果用directed graph表示做事順序的話,
DAG可以保證找到一個順序把事情做完,
如果不是DAG就沒辦法做(表示有環,會互相把事情卡住),
舉例來說:

我有很多東西想吃,

  • 吃魚之前要先吃豆花
  • 吃飲料之前要先吃魚
  • 吃水果之前要先吃飲料
  • 吃飲料之前要先吃豆花
    https://ithelp.ithome.com.tw/upload/images/20200506/20117114vOnxUtP1mp.png

這樣的話就沒辦法找到滿足上述條件的吃東西順序

簡介topological sort

topological sort(中文譯作拓撲排序)就是找到一種順序,
使得你能夠順利把表示事情先後順序的directed graph做完,
譬如說這張圖是吃飯順序
https://ithelp.ithome.com.tw/upload/images/20200506/201171145seWRFa8px.png

  • 先吃完開胃菜才可以吃湯和主菜,
  • 湯和主菜都吃完了才可以吃甜點
  • 飲料沒有限制,什麼時候吃都可以

那麼「開胃菜」->「湯」->「主菜」->「甜點」->「飲料」是一個合法的拓撲排序,
「開胃菜」->「飲料」 ->「主菜」->「湯」->「甜點」也是一個合法的拓撲排序,
拓撲排序有很多種可能排法,只要不違反先後次序的都可以

directed graph能夠做topological sort的充要條件就是它必須是一個DAG

二分搜索樹(Binary Search Tree)

BST是一種特別的binary tree,它滿足二個特性:

  • 左邊子樹的所有節點都比root來的小
  • 右邊子樹的所有節點都比root來的大

例如下圖所示就是一個BST:
https://ithelp.ithome.com.tw/upload/images/20200520/20117114geTEEiicdc.png
(圖片來源: Geeksforgeeks- Binary Search Tree)

這種結構有一個好處,在樹很「平衡」的狀況下,
(所謂「平衡」指的是每一層左邊的樹跟右樹的樹的節點數量都差不多),
那麼要查找一個數有沒有在這棵樹裡面,只需要O(log n)的時間

比如說上樹要找「6」有沒有在這棵樹裡面呢?
首先從root出發,把目標數字跟root上的「8」比一下,
6比8小,所以6只有可能在左邊的樹,不會在右邊的樹,
一下子就少搜索一半的可能

這邊可以學如何在BST裡插入、刪除元素:

heap(堆)

heap是一個二元樹的結構,滿足兩個性質:

  • heap property: 每個父節點要比小孩節點還要小(滿足此特性為min heap,若父節點比小孩節點還要大則為 max heap)
  • shape property: 指heap的長相一定要由上到下、由左到右的擺放節點

譬如說底下是一個heap:
https://ithelp.ithome.com.tw/upload/images/20200314/20117114WwVEtAL5H3.png

這個結構可以幫助我們快速的做到兩件事:

  • insert: 在heap中插入一個元素
  • extract-min: 把heap中最小的元素拿走

insert- O(log n)

要插入一個元素很簡單,譬如我們想在上面畫的那個heap裡插入「1」這個元素,
直接放到heap的下一個位置即可(這樣一定滿足shape property),如圖:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114qFxp9v8oKH.png

可是這樣的話你會發現好像不太對,
heap property說上面的點一定要比下面的點還要小,
可是現在位於上面的「8」比新加入的「1」還大,那怎麼辦呢?

解決的方法就是讓插入的元素跟它的父親節點比較,
如果插入的元素比較小,就跟它父親節點交換,
一直重複做直到大小關係是正確的,
如下圖演示:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114P7GhAy91bW.png
https://ithelp.ithome.com.tw/upload/images/20200314/20117114pblHgf39Yc.png

你會發現,交換的次數最多就是跟樹的高度相同,
所以若樹的節點個數為n個,交換的次數即是O(log n)這麼多次

extract-min- O(log n)

要找到一個heap最小的元素很簡單,
一定是在最上面的位置,
不過如果我們直接把最小的那個元素拿走:
https://ithelp.ithome.com.tw/upload/images/20200314/20117114zXYdd3Myvq.png

然後你就會發現這形狀好像不太對,因為最上面少了一個節點,
所以我們需要把最後一個節點的元素直接補到最上面,
以維持heap的形狀:

https://ithelp.ithome.com.tw/upload/images/20200314/20117114B2PO68TO79.png

但這時heap property又不滿足了,
其實接下來要做的事跟插入元素做的事很類似,
插入元素是把元素跟上面交換,
所以這次我們其實是要把「11」這個元素跟下面比較小的元素交換,
讓大小關係是正確的

https://ithelp.ithome.com.tw/upload/images/20200314/20117114N8t1qnSenC.png
(注意不能把11跟8交換,不然8會比6還大)

https://ithelp.ithome.com.tw/upload/images/20200314/20117114Xm5stvXUfq.png

這邊交換的次數最多也是跟樹的高度相同,
所以若樹的節點個數為n個,交換的次數亦是O(log n)這麼多次

Hash Table(雜湊表)

想像我們現在要解這樣一個問題,
有一個集合S裡面有n個元素,
每個元素的範圍來自[1,u](u可能比n大很多),
那麼要怎麼查詢一個元素x是否在S裡面?

看看學過的工具可以做的多快?
第一種方式是用BST:

  • 空間: O(n)
  • 查詢時間: O(log n)
  • 更新時間(插入新的元素): O(log n)

另外可以用一個大小為u個bit的vector,
第i個bit若為1,表示元素i在我們的集合S裡,則:

  • 空間: O(u) (在u大n小的時候很浪費空間)
  • 查詢時間: O(1)
  • 更新時間(插入新的元素): O(1)

Hash Table則可以截取上述兩種資料結構好處,做到:

  • 空間: O(n)
  • 查詢時間: 期望值O(1) (在糟糕的情況下,可能需O(n)的時間)
  • 更新時間(插入新的元素): 期望值O(1)

程式庫使用

Hash Table 大致相當於c++語言的map, unordered_map
python語言的dict
在程式中可以直接呼叫使用,
簡單來說特色就是查找速度快 (在很多解題平台是加速的技巧)

原理簡介

由於Hash Table使用現有的程式庫可以達到還不錯的效果,
我有些懶的研究Hash的細節,
簡略記錄簡單的原理

  1. 建立一個大小為m的Hash Table,m的大小為θ(n)
  2. 構造一個Hash Function h: [1,u] -> [1,m]
  3. 對於每個在S裡面的元素s,把它放進Hash Table的格子h(s)裡面

未來要查找s是否在集合S裡面,
就去看s有沒有放在格子h(s)裡面即可,
如果hash的效果要好,
就是儘可能不會有多個元素放在同一格

延伸閱讀

若想要學習有關資料結構的程式碼實作,
推薦閱讀演算法與資料結構
這是很詳細的資料結構教學,
但是以c++程式實作


1 則留言

1
Anthony_Yang
iT邦新手 3 級 ‧ 2020-08-12 14:13:13

名詞解釋: parent, chlidren
而節點之間的關係,也可以用parent, chlidren來互稱,
比如說這樣子的一棵樹:

https://ithelp.ithome.com.tw/upload/images/20200329/20117114fJ1bXfVzxz.png

那麼我們稱B是A的chlid,A是B的parent,
E是B的chlid,B是E的chlid

B是E的parent

心原一馬 iT邦研究生 5 級 ‧ 2020-08-12 20:07:52 檢舉

謝謝糾正,已於文內更正

感謝大大的分享
真的超清楚
重新再學習了資料結構的觀念

心原一馬 iT邦研究生 5 級 ‧ 2020-08-14 20:39:26 檢舉

不客氣,助人助己,謝謝你的讚美~

我要留言

立即登入留言