Wall of Text #9: Tree

น้องที่โรงเรียนให้ช่วยติวไปแข่งขันรายการหนึ่ง ซึ่งเราก็เคยไป จำได้ว่าคำถามที่เคยถามมีเกี่ยวกับ Data Structure เลยเล่าเรื่อง Tree ให้ เพราะในมัธยมไม่มีสอน

Tree Data Structure

โครงสร้างข้อมูลแบบ Tree แปลตรงตัวก็คือต้นไม้

แต่ละวงกลมในภาพ มีชื่อเรียกว่า Node แต่ละ Node จะมีตัวพ่อของมันเสมอ ยกเว้นด้านบนสุดของต้นไม้ ซึ่งดันเรียกว่าราก (Root)

Tree ที่อยากจะเล่าถึงเป็นพิเศษวันนี้คือ Binary Tree ซึ่งก็คือ Tree ที่มีลูก 0-2 กิ่ง

Math statement as a tree

การใช้งาน Binary Tree รูปแบบหนึ่งที่น่าสนใจคือเราสามารถแทนสมการคณิตศาสตร์เป็น Tree ได้ เช่น (1 +3) x 5 เขียนได้ดังนี้

ข้อสังเกตอย่างหนึ่งคือการเขียนเป็น Tree ช่วยลดการสับสนได้โดยไม่ต้องใส่วงเล็บ เช่น ถ้าเราเขียนสูตรด้านบนเป็น 1+3 x 5 แล้ว ตามลำดับความสำคัญของ operator เราจะต้องทำคูณหารก่อน คือ 1 + (3×5) ความหมายไม่เหมือนกัน

เมื่อเราแทนสูตรเป็น Tree แล้วก็ทำให้ประโยคไม่กำกวมเช่นเดียวกับการใส่วงเล็บ

Tree traversal

ยังอยู่กันที่ 1+(3×5)
(บทความนี้เผยแพร่ครั้งแรกเขียนว่าใช้ (1×3)+5 แต่รูปผิด เลยขอแก้สูตรให้ถูกต้อง)

เวลาเราไล่ Tree เราสามารถไล่ได้ 2 แบบดังนี้ (สมมุติว่ามองจากซ้ายไปขวา)

Depth first

แปลว่าไล่เอาด้านลึกลงก่อน เราจะได้

  • + จากด้านบนสุดก่อน
  • 1 เกาะด้านซ้าย ไม่มีลูกต่อกลับไปด้านบน
  • x จากด้านขวา
  • 3 จากด้านซ้าย
  • 5 จากด้านขวา

ส่วนมากที่จะพูดถึงต่อไปจะใช้ Depth first เป็นหลัก

Breath first

แปลว่าไล่เอาด้านกว้างก่อน เราจะได้

  • + จากแถวบนสุด
  • 1, x จากแถวที่สอง
  • 3, 5 จากแถวที่สาม

Project อันนึงที่เราเคยทำคือสำรวจความสัมพันธ์ของสองคนบน Steam ใช้ Breath first search เพื่อหาเส้นทางที่สั้นที่สุดระหว่างคนสองคนบน Steam (แต่นี่ไม่ใช่ Tree มันคือ Graph) เช่น

  • เราเป็นเพื่อนกับ A, B, C, …
  • A เป็นเพื่อนกับ A1, A2, A3, A4, …
  • B เป็นเพื่อนกับ B1, B2, B3, B4, …
  • C เป็นเพื่อนกับ C1, C2, C3, C4, …
  • ในชั้นแรกยังไม่เจอเป้าหมาย เราจะดูว่า A1, A2, A3, A4, B1, B2, B3, B4, C1, C2, C3, C4 เป็นเพื่อนกับใครบ้าง
  • A1 เป็นเพื่อนกับ A11, A12, A13, …
  • A2 เป็นเพื่อนกับ A21, A22, A23, …
  • ก็ยังไม่เจอ เราจะดูเพื่อนของ A11, A12, A13, A21, A22, A23, …
  • เราพบว่า A12 เป็นเพื่อนกับเป้าหมาย
  • สรุปว่า เส้นทางที่ใกล้ที่สุดคือ เรา -> A -> A1 -> A12 -> เป้าหมาย

ตอนที่ทำ ใช้สูตรโกงเล็กน้อยคือเราใช้ algorithm นี้สองข้างพร้อมกันเพื่อให้เร็วขึ้น

  • เราเป็นเพื่อนกับ A, B, C, …
  • เป้าหมายเป็นเพื่อนกับ ก, ข, ค, …
  • เอา set {A, B, C}, {ก, ข, ค} มา Intersect เพื่อดูว่าทับซ้อนหรือเปล่า
  • ถ้าไม่มีให้เปิดเพิ่มอีก 1 ชั้นของทั้งสองฝั่ง แล้วเอา set เพื่อนของเพื่อน ทั้งสองคนมา intersect กัน

Notation

นอกจากว่าเราจะไล่ลงด้านลึกก่อนหรือด้านกว้างก่อนแล้ว เรายังสามารถเลือกได้ด้วยว่าหัวของ tree จะอยู่ตรงไหน

กลับมาที่ (1+3)x5

Prefix

สมมุติว่าเราจะไล่ Depth first, Prefix เราจะเขียนหัวก่อนเสมอ ได้ว่า x + 1 3 5

ถ้าย้อนกลับไปอ่านหัวข้อ Depth first จะสังเกตว่าวิธีที่เราไล่ตอนนั้นคือแบบ Prefix

Infix

Infix จะเขียนหัวไว้ตรงกลาง เขียนได้ว่า 1 + 3 x 5

สังเกตว่าวิธีนี้จะเหมือนที่เราใช้เขียนสูตรตามปกติ เพื่อความชัดเจนทุกครั้งเราอาจจะใส่วงเล็บคร่อมเป็น ((1+3)x5) เพื่อไม่ให้กำกวมว่าต้องอ่านจากซ้ายไปขวา

Postfix

วิธีสุดท้ายคือเอาหัวไว้ด้านหลัง เขียนได้ว่า 1 3 + 5 x

Calculation

ประโยชน์อย่างหนึ่งของ Postfix คือเราสามารถหาคำตอบได้ง่ายๆ โดยไม่ต้องใส่วงเล็บ

วิธีการคือ เอาตัวเลขทีละตัวจากซ้ายไปขวามาทดไว้ ถ้าเจอเครื่องหมายให้ดึงตัวทด 2 ตัวล่าสุดมาทำตามเครื่องหมาย แล้วใส่เฉพาะคำตอบคืน

เช่นจากด้านบน (1+3) x 5 เขียนเป็น Postfix ได้ว่า 1 3 + 5 x

  • 1 ทดไว้
  • 3 ทดไว้ เป็น 1 3
  • เจอเครื่องหมาย + เอามาบวกกันได้ 4 แล้วใส่คืน
  • 5 ทดไว้ เป็น 4 5
  • เจอเครื่องหมายคูณ เอามาคูณกันได้ 20 เป็นคำตอบสุดท้าย

ถ้าเป็นรูปนี้ 1+(3×5) เราจะเขียน Postfix ได้ว่า 1 3 5 x +

  • 1 3 5 x ทดไว้ เจอเครื่องหมาย x เอาสองตัวล่าสุดคูณกัน 3 x 5 = 15 ใส่คืน
  • ตอนนี้ที่ทดอยู่คือ 1 15
  • 1 15 + เจอเครื่องหมายเอามาบวกกันได้ 16

ข้อสังเกตเวลาเราใช้เครื่องคิดเลขที่รองรับการป้อนข้อมูลแบบ Postfix

  • เราไม่ต้องทดเลขไว้ในใจ เช่นถ้าจะกด (1+3) x (2+5) เราต้องกด 1+3, 2+5 แล้วเอาคำตอบมาคูณกัน (อาจจะใช้ระบบ MS ของเครื่องคิดเลข) แต่ถ้าเป็น Postfix เราสามารถกด 1 3 + 2 5 + x ได้เลย
  • เราไม่ต้องกดเครื่องหมาย = เพื่อหาคำตอบสุดท้าย เพราะตัวสุดท้ายเป็นเครื่องหมายคณิตศาสตร์เสมอ

Tree ใช้ตอนไหน

นอกเหนือจาก Binary Tree ที่มีแค่สองขาแล้ว Tree ธรรมดาก็มีประโยชน์หลายอย่าง เช่น

Abstract Syntax Tree

เวลาเขียนโปรแกรมแล้ว Compile ตัว Compiler จะสร้าง Tree จากโปรแกรมของเรา

เช่นโปรแกรมนี้

if (x == 0) {
   x = x + 1;
}
print("%d", x);

เขียนเป็น Tree ได้ว่า

ซึ่งถ้าเราลองคิดตาม Tree แบบ Depth first ดูก็จะพบว่าได้ลำดับการทำงานเหมือนกับโปรแกรมเดิมเลย ซึ่งช่วยให้ compiler สามารถแปลงโค้ดโปรแกรมต่อเป็นภาษาเครื่องได้ง่าย

หาข้อมูล

เราสามารถใช้ Tree เก็บข้อมูลเพื่อให้หาข้อมูลได้ง่ายๆ เช่น

จากภาพนี้ถ้าเราต้องการหาคำว่า bag ว่ามีหรือไม่ เราก็ไล่ไปทีละตัว คือ b, a, แล้วชั้นสุดท้ายพบว่าไม่มี g แสดงว่าไม่มีคำนี้

เมื่อเทียบกับการเขียนทุกคำคือ app, apt, ape, ace, act, bad, ban, bat แล้วไล่จากซ้ายไปขวา การใช้ tree ไวกว่ากันเยอะ