Download presentation
Presentation is loading. Please wait.
1
JAVA 程式設計與資料結構 第十七章 Tree
2
Introduction Tree是常用的資料結構，可以將資料有系統有組織的儲存。 最上面的那一個Node稱之為根(Root)
上一層的Node是下一層的父母(Parents)，下一層的Node是上一層的子女(children)，同一層的Node並擁有相同的Parents的是兄弟姊妹(siblings) Leaf
3
Depth and Height 如果v是Tree中的某一個Node，那麼v的深度(depth)為v的ancestor數量，但不包括v自己。也就是說，root在深度＝0，其下一層為深度＝1，以下列推。 某一點v的高度(height)之定義為自葉子算上來的層數減一，也就是說最底層的葉子之高度為0，其上一層的高度為1，依此列推。而自最底層的葉子到root的層數（亦即root的高度），也是該Tree的高度。
4
Binary Tree Binary Tree就是每一個Node最多可以有兩個children，一個是left child，另一個是right child。 沒有空隙的排列方式，我們稱之為Complete Binary Tree。而如果leaf的depth相差不超過1，我們稱之為Balance Tree。
5
depth跟Node的個數關係 Complete Binary Tree的Node數為 。
如果我們有100個Node排成一個Balance Tree，那最大的深度depth為多少？ 瞭解tree的深度可以知道搜尋的速度
6
worst-case的執行時間為O（log n)
Insert worst-case的執行時間為O（log n)
7
Remove
8
Remove
Similar presentations
