ต้นไม้ไบนารีในโครงสร้างข้อมูล (ตัวอย่าง)
ซาราห์ เฉิน
ต้นไม้ไบนารีคืออะไร?
คำว่าไบนารีหมายถึงสอง ในโครงสร้างข้อมูลแบบต้นไม้ “Binary Tree” หมายถึงต้นไม้ที่แต่ละโหนดสามารถมีโหนดย่อยได้สูงสุดสองโหนด (โหนดซ้ายและขวา) มันเป็นต้นไม้ไบนารีธรรมดา
อย่างไรก็ตาม มีไบนารีทรีอีกแบบหนึ่งที่ถูกใช้บ่อยที่สุดและมีหลายกรณีการใช้งาน เรียกว่า ไบนารีเสิร์ชทรี (BST) ไบนารีทรีนี้สามารถทำให้อัลกอริทึมการค้นหาเร็วขึ้นมาก โดยเฉพาะอย่างยิ่งความซับซ้อนของเวลา log(n) ในโครงสร้างข้อมูล n หมายถึงจำนวนโหนดในไบนารีทรี
อะไรคือความแตกต่างระหว่าง Binary Tree และ Binary Search Tree?
ความแตกต่างระหว่าง BST และแผนผังไบนารีปกติอยู่ที่โหนดด้านซ้ายของ BST มีค่าน้อยกว่าโหนดรูท และโหนดด้านขวามีค่ามากกว่าโหนดรูท ดังนั้นแผนผังย่อยด้านซ้ายจะมีค่าน้อยกว่ารากเสมอ และแผนผังย่อยด้านขวาจะมีค่ามากกว่ารากเสมอ
ตัวอย่างของแผนผังการค้นหาแบบไบนารี
มาดูตัวอย่างต่อไปนี้เพื่อสาธิตแนวคิดของ Binary Search Tree
ที่นี่คุณสามารถโหนดทั้งหมดปฏิบัติตามระเบียบวินัยที่กำหนดได้ มีสูตรสำหรับจำนวนโหนดสูงสุดในแผนผังการค้นหาแบบไบนารี หากเราสังเกตแผนผังด้านบน เราจะเห็นว่าแต่ละโหนดมีลูกสองคน ยกเว้นโหนดใบทั้งหมด และความสูง(h) ของ Binary Tree ที่กำหนดคือ 4 สูตรคือ 2h - 1- งั้นก็ให้ 15
รูปภาพที่ให้มาข้างต้นไม่ใช่ Binary Tree หรือ Balanced Binary Tree ที่สมบูรณ์ เรียกว่า Complete Binary tree หรือ Balanced Binary Tree มีโครงสร้างข้อมูลอื่นที่เรียกว่า AVL (Binary Tree อีกประเภทหนึ่ง) ที่ปรับความสูงของ Binary Tree ให้เหมาะสมและทำการค้นหา BST ได้เร็วขึ้นเหมือนในรูปที่ 3
ลองคำนวณการสืบค้นแบบลำดับของ Binary Tree ที่กำหนดไว้ข้างต้น คุณจะพบว่ามันจะให้ผลลัพธ์เป็นอาร์เรย์ที่เรียงลำดับไม่ลดลง และอัลกอริทึมการสืบค้นจะเหมือนกับ Binary Tree
ประเภทของไบนารีทรี
นี่คือ Binary Tree ประเภทที่สำคัญบางประเภท:
- ต้นไม้ไบนารีเต็ม: แต่ละโหนดสามารถมีโหนดย่อยได้ 0 หรือ 2 โหนดในแผนผังไบนารีนี้ ไม่อนุญาตให้ใช้โหนดย่อยเพียงโหนดเดียวในแผนผังไบนารีประเภทนี้ ดังนั้น ยกเว้นโหนดใบ โหนดทั้งหมดจะมีลูก 2 คน
- ต้นไม้ไบนารีเต็ม: แต่ละโหนดสามารถมี 0 หรือ 2 โหนดได้ ดูเหมือนว่า Full Binary Tree แต่องค์ประกอบ leaf ทั้งหมดจะเอียงไปทางแผนผังย่อยด้านซ้าย ในขณะที่โหนดแผนผังไบนารีแบบเต็มสามารถอยู่ในแผนผังย่อยทางขวาหรือซ้ายได้
- ต้นไม้ไบนารีที่สมบูรณ์แบบ: โหนดทั้งหมดต้องมี 0 หรือ 2 โหนด และโหนดใบทั้งหมดควรอยู่ในระดับหรือความสูงเท่ากัน ตัวอย่างข้างต้นของโครงสร้างไบนารีทรีแบบเต็มไม่ใช่ Perfect Binary Tree เนื่องจากโหนด 6 และโหนด 1,2,3 ไม่ได้มีความสูงเท่ากัน แต่ตัวอย่างของ Complete Binary Tree ก็คือ binary tree ที่สมบูรณ์แบบ
- ต้นไม้ไบนารีเสื่อมโทรม: แต่ละโหนดสามารถมีโหนดย่อยได้เพียงโหนดเดียว การดำเนินการทั้งหมด เช่น การค้นหา การแทรก และการลบ จะใช้เวลา O(N)
- ต้นไม้ไบนารีที่สมดุล: ที่นี่ต้นไม้ไบนารีนี้ ความแตกต่างของความสูงของแผนผังย่อยด้านซ้ายและขวาอยู่ที่ 1 มากที่สุด ดังนั้น ในขณะที่เพิ่มหรือลบโหนด เราจำเป็นต้องปรับสมดุลความสูงของต้นไม้อีกครั้ง Self-Balanced Binary Tree ประเภทนี้เรียกว่า ต้นไม้ AVL.
BST มีการทำงานพื้นฐาน 3 อย่าง ซึ่งจะอธิบายรายละเอียดด้านล่าง
การใช้งาน Binary Tree ใน C และ C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
Output:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
การใช้งาน Binary Tree ใน Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
Output:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
การประยุกต์ใช้ Binary Tree
นี่คือการใช้งานทั่วไปของ Binary Tree:
- การจัดระเบียบข้อมูลโหนดตามลำดับ
- ใช้ในแผนที่และตั้งค่าวัตถุโหนดในไลบรารีภาษาการเขียนโปรแกรม
- การค้นหาองค์ประกอบในโครงสร้างข้อมูล
» เรียนรู้บทช่วยสอนถัดไปของเราเกี่ยวกับ อัลกอริธึมการรวมกัน
