โครงสร้างข้อมูล - โครงสร้างการค้นหาแบบไบนารี

Binary Search Tree (BST) คือต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง -

  • ค่าของคีย์ของแผนผังย่อยด้านซ้ายมีค่าน้อยกว่าค่าของคีย์ของโหนดหลัก (รูท)

  • ค่าของคีย์ของแผนผังย่อยด้านขวามากกว่าหรือเท่ากับค่าของคีย์ของโหนดหลัก (รูท)

ดังนั้น BST จึงแบ่งต้นไม้ย่อยทั้งหมดออกเป็นสองส่วน แผนผังย่อยด้านซ้ายและแผนผังย่อยด้านขวาและสามารถกำหนดเป็น -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

การเป็นตัวแทน

BST คือชุดของโหนดที่จัดเรียงในลักษณะที่พวกมันรักษาคุณสมบัติ BST แต่ละโหนดมีคีย์และค่าที่เกี่ยวข้อง ขณะค้นหาคีย์ที่ต้องการจะถูกเปรียบเทียบกับคีย์ใน BST และหากพบค่าที่เกี่ยวข้องจะถูกดึงออกมา

ต่อไปนี้เป็นการแสดงภาพของ BST -

เราสังเกตว่าคีย์โหนดรูท (27) มีคีย์ที่มีค่าน้อยกว่าทั้งหมดบนแผนผังย่อยด้านซ้ายและคีย์ที่มีมูลค่าสูงกว่าบนแผนผังย่อยด้านขวา

การทำงานขั้นพื้นฐาน

ต่อไปนี้คือการทำงานพื้นฐานของต้นไม้ -

  • Search - ค้นหาองค์ประกอบในต้นไม้

  • Insert - แทรกองค์ประกอบในต้นไม้

  • Pre-order Traversal - สำรวจต้นไม้ในลักษณะสั่งจองล่วงหน้า

  • In-order Traversal - เดินลัดเลาะไปตามต้นไม้ตามลำดับ

  • Post-order Traversal - เดินลัดเลาะไปตามต้นไม้ในลักษณะโพสต์ออร์เดอร์

โหนด

กำหนดโหนดที่มีข้อมูลอ้างอิงโหนดลูกด้านซ้ายและขวา

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

การดำเนินการค้นหา

เมื่อใดก็ตามที่ต้องการค้นหาองค์ประกอบให้เริ่มค้นหาจากโหนดรูท จากนั้นหากข้อมูลน้อยกว่าค่าคีย์ให้ค้นหาองค์ประกอบในทรีย่อยด้านซ้าย มิฉะนั้นให้ค้นหาองค์ประกอบในทรีย่อยด้านขวา ทำตามอัลกอริทึมเดียวกันสำหรับแต่ละโหนด

อัลกอริทึม

struct node* search(int data){
   struct node *current = root;
   printf("Visiting elements: ");
	
   while(current->data != data){
	
      if(current != NULL) {
         printf("%d ",current->data);
			
         //go to left tree
         if(current->data > data){
            current = current->leftChild;
         }  //else go to right tree
         else {                
            current = current->rightChild;
         }
			
         //not found
         if(current == NULL){
            return NULL;
         }
      }			
   }
   
   return current;
}

แทรกการทำงาน

เมื่อใดก็ตามที่จะแทรกองค์ประกอบอันดับแรกให้หาตำแหน่งที่เหมาะสม เริ่มค้นหาจากโหนดรูทจากนั้นหากข้อมูลมีค่าน้อยกว่าค่าคีย์ให้ค้นหาตำแหน่งว่างในทรีย่อยด้านซ้ายและแทรกข้อมูล มิฉะนั้นให้ค้นหาตำแหน่งว่างในทรีย่อยด้านขวาและแทรกข้อมูล

อัลกอริทึม

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) {                
         parent = current;
			
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            //insert to the left
				
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}