Trees: Foundations & Traversal
นิยาม การแทนข้อมูล และการท่องไปในต้นไม้

Day 06 Morning: โครงสร้างข้อมูลพื้นฐานที่สำคัญที่สุดในโลกของอัลกอริทึม

สิ่งที่จะได้เรียนรู้

1

นิยามทางคณิตศาสตร์และคุณสมบัติของ Tree

2

การจัดเก็บ Tree ในหน่วยความจำ (Adjacency List/Array)

3

การท่องไปในต้นไม้ด้วย Pre-order, In-order และ Post-order

แหล่งอ้างอิง: https://cses.fi/book/book.pdf

Tree คืออะไร?

นิยามทางกราฟ:

ต้นไม้ (Tree) คือ กราฟเชื่อมโยง (Connected Graph) ที่ **ไม่มีวงจร (Acyclic)**

คุณสมบัติสำคัญ:

ถ้าต้นไม้มี \( n \) โหนด จะต้องมีเส้นเชื่อมทั้งหมด \( n-1 \) เส้นเสมอ
มีเส้นทาง (Path) เพียงเส้นทางเดียวเท่านั้นที่เชื่อมระหว่างโหนด 2 โหนดใดๆ
การเพิ่มเส้นเชื่อมเพียง 1 เส้น จะทำให้เกิดวงจร (Cycle) ทันที

รายละเอียดเพิ่มเติม: https://roadmap.sh/datastructures-and-algorithms

โครงสร้างแบบเรียกซ้ำ (Recursive Structure)

"โหนดแต่ละโหนด สามารถมองเป็นรากของต้นไม้ย่อย (Subtree) ได้เสมอ"

ในต้นไม้ที่มีราก (Rooted Tree) ต้นไม้ย่อยของโหนด \( v \) ประกอบด้วยโหนด \( v \) เองและทายาท (Descendants) ทั้งหมดของมัน แนวคิดนี้ช่วยให้เราเขียนอัลกอริทึมด้วย **Recursion** ได้อย่างมีประสิทธิภาพ

Subtree Size = 1 + Sum(Sizes of Children's Subtrees)

อ้างอิง: https://cses.fi/book/book.pdf (Chapter 14)

การแทนข้อมูล: Adjacency List

เป็นวิธีที่นิยมที่สุดในการเก็บ Tree ในการแข่งขัน:

vector<int> adj[N];
// เพิ่มเส้นเชื่อมระหว่าง u และ v
adj[u].push_back(v);
adj[v].push_back(u);

ข้อดี:

• ใช้พื้นที่เพียง \( O(n) \)
• สามารถท่องไปในเพื่อนบ้านของโหนดได้รวดเร็ว
• รองรับต้นไม้ที่มีขนาดใหญ่ถึง \( 10^5 - 10^6 \) โหนด

ต้นไม้คู่ (Binary Trees)

นิยาม:

เป็นต้นไม้ที่มีรากซึ่งแต่ละโหนดจะมีลูกได้ **ไม่เกิน 2 โหนด** (ซ้ายและขวา)

โหนดทางซ้าย (Left Child)

โหนดทางขวา (Right Child)

สามารถเป็นค่าว่างได้ (Empty Subtree)

Binary Trees เป็นพื้นฐานของโครงสร้างขั้นสูงอย่าง Segment Tree และ Binary Search Tree (BST)

การเก็บโหนดด้วยอาเรย์ (Array Trick)

ในต้นไม้คู่ที่สมบูรณ์ (Complete Binary Tree) เราสามารถใช้ Index ของอาเรย์แทนตำแหน่งได้:

• ราก (Root) อยู่ที่ Index \( 1 \)
• ลูกซ้ายของโหนด \( i \) อยู่ที่ \( 2i \)
• ลูกขวาของโหนด \( i \) อยู่ที่ \( 2i + 1 \)
• พ่อของโหนด \( i \) อยู่ที่ \( \lfloor i/2 \rfloor \)

**เทคนิคนี้ใช้บ่อยมากในการเขียน Binary Heap และ Segment Tree**

เพิ่มเติม: https://www.geeksforgeeks.org/tree-data-structure/

การท่องไปในต้นไม้ (Tree Traversal)

เนื่องจากต้นไม้ไม่มีวงจร การท่องไปในโหนดต่างๆ จึงง่ายกว่ากราฟทั่วไป เพราะเราไม่จำเป็นต้องกังวลว่าจะกลับมาที่โหนดเดิมจากทิศทางอื่น

Depth-First Search (DFS)

พยายามลงไปให้ลึกที่สุดก่อนถอยกลับ

Breadth-First Search (BFS)

ท่องไปทีละระดับความลึก (Level-order)

การเขียน DFS สำหรับต้นไม้

// s = โหนดปัจจุบัน, e = โหนดพ่อ (เพื่อไม่ให้เดินย้อนกลับ)

void dfs(int s, int e) {

// 1. จัดการข้อมูลของโหนด s (Pre-order)

for (auto u : adj[s]) {

if (u == e) continue;

dfs(u, s);

}

// 2. จัดการข้อมูลหลังลูกๆ ทำงานเสร็จ (Post-order)

}

**หมายเหตุ**: ในต้นไม้ที่มีราก เราไม่จำเป็นต้องใช้ array `visited` ก็ได้ เพียงแค่จำโหนดพ่อ (Parent) ไว้

ลำดับการท่อง (Traversal Orderings)

Pre-order: ทำที่รากก่อน -> ไปทางซ้าย -> ไปทางขวา

In-order: ไปทางซ้าย -> ทำที่ราก -> ไปทางขวา (ใช้มากใน BST เพื่อเรียงลำดับ)

Post-order: ไปทางซ้าย -> ไปทางขวา -> ทำที่ราก (ใช้คำนวณ Subtree Info)

**ความท้าทาย**: ถ้าเรารู้ลำดับ Pre-order และ In-order เราจะสามารถสร้าง Tree เดิมกลับมาได้อย่างแม่นยำ!

ข้อมูลเพิ่มเติม: https://atcoder.jp/contests/dp (Educational DP Contest)

ความลึกและความสูง (Depth & Height)

Depth (ความลึก)

จำนวนเส้นเชื่อมจาก Root มายังโหนดปัจจุบัน โดยความลึกของ Root คือ \( 0 \)

Height (ความสูง)

เส้นทางที่ยาวที่สุดจากโหนดปัจจุบันลงไปจนถึง Leaf โดยความสูงของ Leaf คือ \( 0 \)

"ความสูงของต้นไม้ คือ ความสูงของ Root หรือระยะทางจาก Root ถึงโหนดที่อยู่ลึกที่สุด"

อ้างอิง: https://cses.fi/book/book.pdf

การคำนวณความลึกด้วย DFS

void calculate_depth(int s, int e, int d) {

depth[s] = d;

for (auto u : adj[s]) {

if (u == e) continue;

calculate_depth(u, s, d + 1);

}

พารามิเตอร์ \( d \) จะเพิ่มขึ้นเรื่อยๆ เมื่อเราเดินลงไปยังโหนดลูก ทำให้เราบันทึกระยะห่างจาก Root ได้ในเวลา \( O(n) \)

ดีกรีของโหนด (Degree)

ในกราฟทั่วไป **Degree** คือจำนวนเส้นเชื่อมที่ติดกับโหนดนั้น แต่ใน Rooted Tree เรามักจะสนใจ:

Out-degree: จำนวน "ลูก" (Children) ของโหนดนั้น
In-degree: มีค่าเป็น \( 1 \) เสมอสำหรับโหนดที่ไม่ใช่ Root (เพราะมีพ่อเพียงคนเดียว)

"โหนดที่เป็น Leaf คือโหนดที่มีลูกเป็น \( 0 \) หรือมี Degree รวมเป็น \( 1 \) ในกรณีต้นไม้ไม่มีราก"

ขนาดของ Subtree (Subtree Size)

นิยาม: \( count(s) \) คือจำนวนโหนดทั้งหมดใน Subtree ที่มี \( s \) เป็นราก

สูตรการคำนวณแบบเรียกซ้ำ:
\( count(s) = 1 + \sum_{u \in children(s)} count(u) \)

เทคนิคนี้ใช้ **Post-order logic**: เราต้องให้ลูกๆ คำนวณขนาดของตัวเองให้เสร็จก่อน แล้วจึงนำมารวมกันเพื่อบอกขนาดของโหนดพ่อ

ศึกษาเพิ่มเติม: https://www.geeksforgeeks.org/tree-data-structure/

การแทนข้อมูล: Parent Array

วิธีที่ง่ายที่สุดในการเก็บโครงสร้างต้นไม้ที่มีราก คือการเก็บเพียง **"โหนดพ่อ"** ของแต่ละโหนด

int parent[N]; // parent[i] เก็บหมายเลขโหนดพ่อของ i

• เหมาะสำหรับปัญหาที่ต้องการเดิน "ขึ้น" ไปหา Root (เช่น LCA หรือ DSU)
• ประหยัดพื้นที่มาก ใช้เพียง \( O(n) \) ในรูปแบบอาเรย์มิติเดียว
• ข้อเสีย: หาโหนดลูกได้ยาก ต้องวนลูปตรวจสอบทั้งอาเรย์

BFS: การท่องไปตามระดับ (Level-order)

ใช้ **Queue** ในการจัดการลำดับการเยี่ยมชม โดยเริ่มจาก Root และขยายไปยังโหนดลูกทีละชั้น

ขั้นตอน:

1. ใส่ Root ใน Queue
2. ดึงโหนดออกมา และใส่ลูกๆ ทั้งหมดของมันลงใน Queue
3. ทำซ้ำจน Queue ว่าง

queue<int> q; q.push(root);
while(!q.empty()){
  int s = q.front(); q.pop();
  for(auto u : adj[s]){
    if(u == parent[s]) continue;
    q.push(u);
  }
}

เส้นผ่านศูนย์กลาง (Diameter)

"ระยะทางที่ยาวที่สุดระหว่างโหนด 2 โหนดใดๆ"

• ในต้นไม้อาจมีโหนดหลายคู่ที่มีระยะทางเท่ากับ Diameter

• เป็นหนึ่งในปัญหาคลาสสิกที่สามารถแก้ได้ด้วย DFS 2 ครั้ง หรือ DP บนต้นไม้

• การหาเส้นทางนี้ช่วยให้เข้าใจโครงสร้างความกว้างของต้นไม้ได้ดีขึ้น

รายละเอียดอัลกอริทึม: https://roadmap.sh/datastructures-and-algorithms

คุณสมบัติเส้นทางเดียว (Unique Path)

ความจริงที่สำคัญ:

สำหรับโหนด \( u \) และ \( v \) ใดๆ ในต้นไม้ จะมี **เส้นทาง (Path) เพียงเส้นเดียวเท่านั้น** ที่เชื่อมระหว่างกัน

"หากมีเส้นทางมากกว่าหนึ่ง นั่นแปลว่ามีวงจร (Cycle) และกราฟนั้นจะไม่ใช่ต้นไม้อีกต่อไป"

ระยะทางระหว่างโหนด (Distance)

ระยะทาง \( dist(u, v) \) คือจำนวนเส้นเชื่อมบนเส้นทางที่สั้นที่สุดระหว่าง \( u \) และ \( v \)

\( dist(u, v) = depth[u] + depth[v] - 2 \cdot depth[LCA(u, v)] \)

*LCA (Lowest Common Ancestor) คือ บรรพบุรุษร่วมที่อยู่ลึกที่สุดของโหนดทั้งสอง

สรุปความต่าง: Tree vs Graph

คุณสมบัติ	Tree	General Graph
จำนวนเส้นเชื่อม	\( n-1 \)	\( 0 \) ถึง \( \frac{n(n-1)}{2} \)
วงจร (Cycles)	ไม่มีเด็ดขาด	มีหรือไม่มีก็ได้
การเชื่อมโยง	ต้องเชื่อมถึงกันหมด	อาจมีโหนดที่แยกตัว (Disconnected)
ความลึก (Stack)	DFS ทำงานง่ายกว่ามาก	ต้องระวัง Infinite Loop

อ้างอิง: https://cses.fi/book/book.pdf

อัลกอริทึมการหา Diameter (2-DFS)

ขั้นตอนที่เรียบง่ายแต่ทรงพลัง:

เลือกโหนด \( a \) ใดๆ ก็ได้ในต้นไม้
ใช้ DFS/BFS หาโหนด \( b \) ที่อยู่ **ไกลที่สุด** จาก \( a \)
ใช้ DFS/BFS อีกครั้งหาโหนด \( c \) ที่อยู่ **ไกลที่สุด** จาก \( b \)
ระยะทางระหว่าง \( b \) และ \( c \) คือ **เส้นผ่านศูนย์กลาง (Diameter)**

*หมายเหตุ: อัลกอริทึมนี้ใช้ได้เฉพาะกับต้นไม้ที่ไม่มีน้ำหนักเส้นเชื่อมเป็นลบ

ศึกษาการพิสูจน์: https://cses.fi/book/book.pdf

บรรพบุรุษร่วมที่ต่ำที่สุด (LCA)

นิยาม LCA(u, v):

คือโหนดที่เป็นบรรพบุรุษ (Ancestor) ของทั้ง \( u \) และ \( v \) และมีความลึก (Depth) **มากที่สุด**

การประยุกต์ใช้:

ใช้หาระยะทางระหว่างโหนด, ตรวจสอบความสัมพันธ์ในครอบครัวของโหนด, และแก้ปัญหาเส้นทางบนต้นไม้

ความซับซ้อน:

Naive: \( O(n) \)
Binary Lifting: \( O(\log n) \)

ความสัมพันธ์ระหว่าง LCA และระยะทาง

dist(u, v) = depth[u] + depth[v] - 2 \cdot depth[LCA(u, v)]

เหตุผลคือ เมื่อเราเดินทางจาก \( u \) ไปยัง \( v \) เราต้องขึ้นไปหาจุดเชื่อมต่อที่เตี้ยที่สุด (LCA) แล้วค่อยลงไปหาอีกโหนดหนึ่ง การลบส่วนที่ซ้ำซ้อนของเส้นทางบรรพบุรุษออกทำให้ได้ระยะทางที่แท้จริง

เพิ่มเติมเรื่อง Binary Lifting: https://usaco.guide/gold/LCA

Binary Search Tree (BST)

เป็น Binary Tree พิเศษที่มีการจัดเรียงข้อมูลอย่างเป็นระบบ:

L
โหนดใน **Subtree ซ้าย** ทั้งหมดต้องมีค่าน้อยกว่าโหนดปัจจุบัน
R
โหนดใน **Subtree ขวา** ทั้งหมดต้องมีค่ามากกว่าโหนดปัจจุบัน

"BST ช่วยให้เราค้นหาข้อมูล (Search) ได้ในเวลา \( O(\log n) \) หากต้นไม้มีความสมดุล"

BST และการท่องแบบ In-order

"In-order traversal of BST results in sorted order"

เมื่อเราท่องไปใน BST ด้วยลำดับ (ซ้าย -> ราก -> ขวา) เราจะได้ข้อมูลที่เรียงลำดับจาก **น้อยไปมาก** เสมอ

void in_order(Node* node) {
  if (!node) return;
  in_order(node->left);
  cout << node->value << " ";
  in_order(node->right);
}

ความสมดุลของต้นไม้ (Balance)

Balanced

ความสูงของต้นไม้คงอยู่ที่ \( O(\log n) \) ทำให้ทุกการดำเนินการ (Search, Insert, Delete) ทำงานได้รวดเร็ว

Skewed (Degenerate)

ต้นไม้กลายสภาพเป็น Linked List ทำให้ความสูงกลายเป็น \( O(n) \) และประสิทธิภาพตกลงอย่างมหาศาล

"เราใช้โครงสร้างอย่าง AVL Tree หรือ Red-Black Tree เพื่อรักษาความสมดุลนี้"

การแทนข้อมูล: Edge List

เก็บเพียงรายการของเส้นเชื่อมทั้งหมดที่มีในต้นไม้

struct Edge { int u, v, weight; };
vector<Edge> edges;

• เหมาะสำหรับอัลกอริทึมที่สนใจ "เส้นเชื่อม" มากกว่า "เพื่อนบ้าน"
• นิยมใช้มากในปัญหา **Minimum Spanning Tree (MST)** เช่น Kruskal's algorithm
• ใช้พื้นที่ \( O(n) \) เพราะมีเส้นเชื่อมเพียง \( n-1 \) เส้น

ป่า (Forest)

Forest

นิยาม:

ป่า คือ กราฟที่ **ไม่มีวงจร (Acyclic)** แต่ไม่จำเป็นต้องเชื่อมต่อกัน (Disconnected)

"Forest คือกลุ่มของต้นไม้หลายๆ ต้นที่แยกจากกัน หากเพิ่มเงื่อนไขว่ากราฟต้องเชื่อมโยงกัน Forest จะกลายเป็น Tree ทันที"

เกริ่นนำ: Dynamic Programming on Trees

หลายปัญหาบนต้นไม้สามารถแก้ได้ด้วย DP โดยใช้โครงสร้างแบบเรียกซ้ำ:

dp[s] = f(dp[u1], dp[u2], ..., dp[uk])

"เมื่อ \( u_i \) คือลูกทั้งหมดของ \( s \). เราจะรอให้คำตอบของลูกๆ พร้อมก่อน (Post-order) แล้วจึงสรุปผลที่โหนดแม่"

ตัวอย่าง: การหาขนาด Subtree, การหาค่าสูงสุดในเส้นทาง, การเลือกโหนดที่ไม่ติดกัน (Independent Set)

สรุปเนื้อหาช่วงเช้า

โครงสร้าง (Structure)

เข้าใจนิยาม \( n \) โหนด \( n-1 \) เส้นเชื่อม และความเป็นกราฟที่ไม่มีวงจร

การแทนที่ (Representation)

Adjacency List คือหัวใจหลัก และ Parent Array คือเครื่องมือเดินขึ้นหาบรรพบุรุษ

การท่องไป (Traversal)

DFS และ BFS คือรากฐานของทุกอัลกอริทึมบนต้นไม้

คุณสมบัติ (Properties)

LCA, Distance และ Diameter ช่วยให้เราเข้าใจความกว้างและลึกของต้นไม้

พักเที่ยง!

Coming up next (13:00):

เราจะนำ DFS และ BFS มาใช้แก้ปัญหาที่ซับซ้อนขึ้น เช่น การหาจุดวิกฤต, การจัดการกับข้อมูลตามระดับชั้น และการนำ Traversal ไปประยุกต์กับโจทย์โอลิมปิก

Next: Tree Traversal: BFS & DFS applications

Trees: Foundations & Traversal นิยาม การแทนข้อมูล และการท่องไปในต้นไม้