[TH] Binary Search Tree

บทความนี้เป็นการเขียนโปรแกรมภาษา C/C++ กับบอร์ด Arduino Nano, Arduino Uno, LGT8F328P [NANO F328P-C] และ ET-BASE AVR EASY32U4 (ภาพที่ 1) หรือบอร์ดอื่น ๆ และแพล็ตฟอร์มอื่น ๆ ที่ใช้ภาษา C เพื่อเรียนรู้การเขียนโปรแกรมจัดการโครงสร้างข้อมูล (Data Structure) อีกประเภทหนึ่งซึ่งมีวิธีการจัดเก็บและจัดการที่แตกต่างกันไปอันมีชื่อว่าต้นไม้แบบ BST หรือ Binary Search Tree ดังในภาพที่ 2 ซึ่งเป็นโครงสร้างที่สามารถนำไปประยุกต์เกี่ยวกับการเก็บข้อมูลที่มีคุณลักษณะที่ข้อมูลทางกิ่งด้านซ้ายมีค่าที่น้อยกว่าตัวเอง และกิ่งด้านขวามีค่ามากกว่าต้นเอง หรือทำตรงกันข้ามคือกิ่งซ้ายมีค่ามากกว่า และกิ่งด้านขวามีค่าน้อยกว่า ทำให้การค้นหาข้อมูลในกรณีที่ต้นไม้มีความสมดุลย์ทั้งทางซ้ายและทางขวาบนโครงสร้าง BST ประหยัดเวลาหรือจำนวนครั้งในการค้นหาลงรอบละครึ่งหนึ่งของข้อมูลที่มี เช่น มีข้อมูล 100 ชุด ในรอบแรกถ้าตัวเองยังไม่ใช่ข้อมูลที่กำลังค้นหา จะเหลือทางเลือกให้หาจากกิ่งทางซ้ายหรือขวา ซึ่งการเลือกทำให้ข้อมูลของอีกฝั่งนั้นไม่ถูกพิจารณา หรือตัดทิ้งไปครึ่งหนึ่งโดยประมาณ แต่ถ้าเป็นกรณีที่ Binary Search Tree นั้นขาดความสมดุลย์จะส่งผลให้การค้นหามีความเร็วไม่แตกต่างกับการค้นหาแบบลำดับ (Sequential Search) เท่าใดนัก

โครงสร้างข้อมูล BST

โครงสร้างข้อมูลแบบ BST เป็นการเก็บข้อมูลที่มีโครงสร้าง 3 ลักษณะ ดังภาพที่ 2 และ 3 โดยในภาพแรกจะพบว่าข้อมูลที่เก็บในโครงสร้างต้นไม้นั้นประกอบไปด้วย node และใน node นี้เองประกอบไปด้วย 3 ส่วน คือ

• left สำหรับเก็บค่าตำแหน่งข้อมูลของโหนดที่อยู่ทางซ้ายมือของโหนดปัจจุบัน
• info สำหรับเก็บข้อมูลของโหนดปัจจุบัน
• right สำหรับเก็บตำแหน่งของโหนดที่อยู่ทางขวามือ

โหนดของ BST

จากภาพที่ 2 นำมาเขียนเป็นคลาส BSTNode เพื่อเก็บข้อมูลโหนดของ BST ได้ดังนี้

struct node {
    node * left;
    int info;
    node * right;
};

ในโค้ดด้านบนจะพบว่า ได้สร้างตัวแปรหรือคุณสมบัติของโหนดไว้ 3 รายการ คือ

• left สำหรับเก็บค่าตำแหน่งโหนดทางซ้าย โดยกำหนดค่าเริ่มต้นเป็น NULL
• info สำหรับเก็บค่าข้อมูลที่กำหนดในช่วงของการสร้างต้นไม้
• right สำหรับเก็บค่าตำแหน่งหรือการชี้ไปยังโหนดทางขวา ซึ่งค่าเริ่มต้นของการสร้างโหนดได้กำหนดเป็น NULL

การเพิ่มโหนด

การเพิ่มโหนดเข้าไปใน BST จะเกิดขึ้นได้ 3 กรณี คือ

1. ข้อมูลที่เพิ่มนั้นมีอยู่แล้ว
2. ข้อมูลที่เพิ่มเข้ามานั้นน้อยกว่าโหนดปัจจุบัน
3. ข้อมูลที่เพิ่มเข้ามีค่ามากกว่าโหนดปัจจุบัน

โดยกรณีที่เป็นข้อมูลมีอยู่แล้วจะรายงานว่าข้อมูลซ้ำ (หรือไม่ต้องรายงานเพื่อเพิ่มความเร็วของการทำงาน)

ชุดคำสั่งสำหรับสร้างโหนดใหม่เป็นดังนี้

node* newNode(int info) { // สร้างโหนดใหม่
  node* new_node = (node*)malloc(sizeof(node));
  if (new_node != NULL) {
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->info = info;
  }
  return new_node;
}

โค้ดโปรแกรมสำหรับเมธอดหรือฟังก์ชัน insert() เป็นดังนี้

node * insert(node * pNode, int info) {
  if (pNode == NULL) {
    Serial.print("Insert ");
    Serial.print(info);
    Serial.println("... done.");
    return newNode(info);
  }
  if (pNode->info < info) {
    pNode->left = insert( pNode->left, info);
  } else if (pNode->info > info) {
    pNode->right = insert(pNode->right, info );
  } else if (pNode->info == info){
    Serial.println("This information is a duplicate of what already exists.");
  }
  return pNode;
}

การค้นหา

การค้นหาหรือการท่อง (Traverse) เข้าไปในต้นไม้แบบ BST เพื่อเข้าถึงข้อมูลของแต่ละโหนดนั้นมีด้วยกัน 3 วิธีดังต่อไปนี้

การค้นหาแบบ pre-order

แบบ pre-order มีหลักการทำงานคือทำ VLR ดังนี้

• ดึงข้อมูลของตัวเอง (V)
• ถ้าไปซ้ายได้ให้ไปทางซ้าย (L)
• ถ้าไม่ได้ให้ไปทางขวา (R)

โค้ดโปรแกรมของการทำงาน pre-order เป็นดังนี้

void preorder( node *root) {
  if (root != NULL) {
    preorder(root->left);
    preorder(root->right);
    Serial.println(root->info);
  }
}

การค้นหาแบบ in-order

หลักการทำงานของแบบ in-order แตกต่างออกไป คือ LVR ซึงเป็นดังนี้

• ถ้าไปซ้ายได้ให้ไปซ้าย (L)
• ดึงข้อมูล (V)
• ถ้าไปขวาได้ให้ไปขวา (R)

สามารถเขียนโค้ดของการทำงานแบบ in-order ได้ดังต่อไปนี้

void inorder( node *root) {
  if (root != NULL) {
    inorder(root->left);
    Serial.println(root->info);
    inorder(root->right);
  }
}

การค้นหาแบบ post-order

กรณีของแบบ port-order นั้นทำงานเป็น LRV คือ

• ถ้าไปซ้ายได้ให้ไปซ้าย (L)
• ถ้าไปขวาได้ให้ไปขวา (R)
• ดึงข้อมูล (V)

จากขั้นตอนจะได้ว่า โค้ดของ post-order คือ

void postorder( node *root) {
  if (root != NULL) {
    Serial.println(root->info);
    postorder(root->left);
    postorder(root->right);
  }
}

ตัวอย่างโปรแกรม

ตัวอย่างโปรแกรมสำหรับการเพิ่มโหนดที่มีข้อมูล 5, 3, 7, 1, 0, 2, 4, 6, 9 และ 8 ซึ่งเมื่อทำด้วยมือจะได้ผลลัพธ์ดังภาพที่ 4

struct node {
  node* left;
  int info;
  node* right;
};

node* newNode(int info) { // สร้างโหนดใหม่
  node* new_node = (node*)malloc(sizeof(node));
  if (new_node != NULL) {
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->info = info;
  }
  return new_node;
}

void inorder( node *root) {
  if (root != NULL) {
    inorder(root->left);
    Serial.println(root->info);
    inorder(root->right);
  }
}

void preorder( node *root) {
  if (root != NULL) {
    preorder(root->left);
    preorder(root->right);
    Serial.println(root->info);
  }
}

void postorder( node *root) {
  if (root != NULL) {
    Serial.println(root->info);
    postorder(root->left);
    postorder(root->right);
  }
}

node * insert(node * pNode, int info) {
  if (pNode == NULL) {
    Serial.print("Insert ");
    Serial.print(info);
    Serial.println("... done.");
    return newNode(info);
  }
  if (pNode->info < info) {
    pNode->left = insert( pNode->left, info);
  } else if (pNode->info > info) {
    pNode->right = insert(pNode->right, info );
  } else if (pNode->info == info){
    Serial.println("This information is a duplicate of what already exists.");
  }
  return pNode;
}

node * rootNode = NULL;

void setup() {
  Serial.begin(9600);
  rootNode = insert( rootNode, 5);
  rootNode = insert( rootNode, 3);
  rootNode = insert( rootNode, 7);
  rootNode = insert( rootNode, 1);
  rootNode = insert( rootNode, 0);
  rootNode = insert( rootNode, 2);
  rootNode = insert( rootNode, 4);
  rootNode = insert( rootNode, 6);
  rootNode = insert( rootNode, 9);
  rootNode = insert( rootNode, 8);
  Serial.println("---------- Pre-order -----------");
  preorder(rootNode);
  Serial.println("---------- In-order -----------");
  inorder(rootNode);
  Serial.println("---------- Post-order -----------");
  postorder(rootNode);
}

void loop() {
}

ตัวอย่างของผลลัพธ์เป็นดังนี้

Insert 5... done.
Insert 3... done.
Insert 7... done.
Insert 1... done.
Insert 0... done.
Insert 2... done.
Insert 4... done.
Insert 6... done.
Insert 9... done.
Insert 8... done.
---------- Pre-order -----------
8
9
6
7
4
2
0
1
3
5
---------- In-order -----------
9
8
7
6
5
4
3
2
1
0
---------- Post-order -----------
5
7
9
8
6
3
4
1
2
0

หมายเหตุ : ลำดับของการแสดงต้องดูจากล่างขึ้นบนนะครับ

สรุป

จากบทความนี้จะพบว่าการเข้าใจหลักการทำงานของโครงสร้างข้อมูลทำให้สามารถนำมาประยุกต์ใช้กับภาษา C และถ้าเข้าใจวิธัการเลือกคำสั่งจะทำให้สามารถนำโค้ดเหล่านั้นไปใช้ได้หลากหลายแพล็ตฟอร์ม อย่างตัวอย่างในรอบนี้ผู้เขียนทดสอบในเครื่อง PC ที่เป็น Linux และ macOS หรือไมโครคอนโทรลเลอร์ต่าง ๆ เช่น Arduino Nano, Arduino Uno, LGT8F328P [NANO F328P-C] และ ET-BASE AVR EASY32U4

ข้อดีของ BST ยังคงเป็นกรณีที่เมื่อต้นไม้มีความสมดุลย์จะทำให้การค้นหานั้นรวดเร็วกว่าการค้นหาแบบลำดับมาก ๆ แต่ถ้าเมื่อใดที่ต้นไม้ไม่มีความสมดุลย์ และเสียสมดุลย์ไปทางข้างใดข้างหนึ่งมาก ๆ เช่น ถ้าเพิ่มข้อมูลเป็น 1,2,3,4,5,6,7,8,9 และ 10 จะพบว่าต้นไม้ทั้งหมดเอียงขวา คือ มีแต่โหนดทางขวา เมื่อทำการค้นหาจึงทำงานเหมือนเป็นการหาแบบลำดับ แต่เพิ่มเวลาของการทำงานที่เป็นส่วนของการตรวจสอบโหนดทางซ้าย โหนดทางขวาและการย้ายโหนดเข้าไปจะทำให้ความเร็วของการทำงานนั้นย่ำแย่กว่าการใช้แถวลำดับหรือ Array กับการเก็บข้อมูล 1 ถึง 10 และค้นหาแบบเรียงลำดับ

สุดท้ายนี้ขอให้สนุกกับการเขียนโปรแกรมครับ

(C) 2020-2023, โดย อ.ดนัย เจษฎาฐิติกุล/อ.จารุต บุศราทิจ
ปรับปรุงเมื่อ 2023-01-01