樹 (抽象資料類型)
閱讀設定
(由子節點跳轉過嚟)
呢篇文 需要熟悉呢方面嘅人幫手寫。 |
樹(英文:tree)係一種喺電腦科學上好有用嘅數據結構,重點特性係拃數據有「高低層」之分。
定義
[編輯]睇埋:數據結構
一樖數據樹都係會[1]:Ch. 6
- 有若干粒節點(node),每粒節點都儲住咗件數據;而且
- 啲節點分層-除咗做起始點嗰粒節點(根節點;root)之外,每粒節點有一粒(而且頂櫳一粒)母節點(parent;指喺嗰粒節點上面,連住嗰粒節點嘅另一粒節點);
- 一粒節點可以有若干粒子節點(child / children);
於是就形成拃節點喺起始點嗰度一層層噉每層都分叉嘅樣,而是但攞粒根節點以外嘅節點,粒節點同根節點之間都有條獨一無二嘅路徑連住兩點。喺電腦科學上,啲人通常會將數據樹畫做樹狀圖噉嘅樣,根節點畫喺最頂,根節點嘅子節點會並排噉列喺根節點下面,根節點嘅子節點嘅子節點會並排噉列喺下一層... 如此類推。好似下面幅圖噉,幅圖表示緊樖數據樹,紅色嗰點係樖數據樹嘅根節點,根節點下一層嘅係佢啲子節點,再下一層嗰啲係根節點嘅子節點嘅子節點... 如此類推,而每粒節點入面嗰個整數就係粒節點裝住嗰件數據[2]。
運算
[編輯]睇埋:搜尋演算法
對樹型數據可以做嘅簡單運算有以下呢啲[1]:Ch. 6:
EmptyTree
,出一樖空嘅數據樹;MakeTree(v, l, r)
,建立一樖二元樹(binary tree;指樖樹每粒節點頂攏得兩粒子節點,好似下圖噉[3]),根節點係v
,由兩樖二元樹l
同r
組成;Leaf(v) = MakeTree(v, EmptyTree, EmptyTree)
-建立一樖得一粒節點v
嘅二元樹;isEmpty(t)
,如果t
係樖空嘅數據樹,噉isEmpty(t)
會出1
(真),否則就出0
(假);
建立一樖有咁上下複雜嘅二元樹可以用類似噉嘅碼(睇返遞歸):
t = MakeTree(8, MakeTree(3,Leaf(1),MakeTree(6,EmptyTree,Leaf(7))), MakeTree(11,MakeTree(9,EmptyTree,Leaf(10)),MakeTree(14,Leaf(12),Leaf(15))))
應用
[編輯]睇埋:人工智能
喺實際應用上,樹呢款數據結構成日畀人攞嚟儲住一啲有關決策嘅資訊:想像家吓有人工智能研究者想教電腦玩遊戲,想部電腦識捉國際象棋;佢可以(簡化講)教部電腦將捉國際象棋嘅過程想像做一樖數據樹-捉國際象棋可以想像成喺每個時間點(層)度揀其中一個可能選擇(每粒節點表示其中一個可能選擇),跟住再行去下一個時間點(去下一層)嗰度,而每粒節點入面嗰件數據表示「揀呢個選擇嘅效益」。有關數據樹嘅具體應用例子,可以睇吓蒙地卡羅樹搜尋(MCTS)呢種演算法[4]。
睇埋
[編輯]攷
[編輯]- ↑ 1.0 1.1 John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.
- ↑ Susanna S. Epp (Aug 2010). Discrete Mathematics with Applications. Pacific Grove, CA: Brooks/Cole Publishing Co. p. 694.
- ↑ Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620.
- ↑ Monte Carlo Tree Search. Towards Data Science.