Binary Search Trees / இருமத் தேடல் மரம்

A Binary Search Tree is a Binary Tree where every node’s left child has a lower value, and every node’s right child has a higher value.

 

A clear advantage with Binary Search Trees is that operations like search, delete, and insert are fast and done without having to shift values in memory.

ஒரு இருமத் தேடல் மரம் என்பது ஒரு இரும மரம் ஆகும். இதில் ஒவ்வொரு முனையின் இடது குழந்தையும் குறைந்த மதிப்பையும், வலது குழந்தையும் அதிக மதிப்பையும் கொண்டிருக்கும்.

 

இருமத் தேடல் மரங்களின் ஒரு தெளிவான நன்மை என்னவென்றால், தேடுதல், நீக்குதல் மற்றும் செருகுதல் போன்ற செயல்பாடுகள் வேகமாகவும், நினைவகத்தில் மதிப்புகளை நகர்த்த வேண்டிய அவசியம் இல்லாமலும் செய்யப்படுகின்றன.

Binary Search Tree (BST) is a type of Binary Tree data structure, where the following properties must be true for any node “X” in the tree:

 

• The X node’s left child and all of its descendants (children, children’s children, and so on) have lower values than X’s value.
• The right child, and all its descendants have higher values than X’s value.
• Left and right subtrees must also be Binary Search Trees.

These properties makes it faster to search, add and delete values than a regular binary tree.

To make this as easy to understand and implement as possible, let’s also assume that all values in a Binary Search Tree are unique.

இருமத் தேடல் மரம் (BST) என்பது ஒரு வகை இரும மரத் தரவுக் கட்டமைப்பாகும். இதில், மரத்தில் உள்ள எந்தவொரு ‘X’ முனைகளுக்கும் பின்வரும் பண்புகள் உண்மையாக இருக்க வேண்டும்:

 

• ‘X’ முனையின் இடது குழந்தை மற்றும் அதன் அனைத்து வழித்தோன்றல்களும் (குழந்தைகள், குழந்தைகளின் குழந்தைகள் மற்றும் பல) ‘X’-இன் மதிப்பை விடக் குறைந்த மதிப்புகளைக் கொண்டிருக்கும்.
• வலது குழந்தை மற்றும் அதன் அனைத்து வழித்தோன்றல்களும் ‘X’-இன் மதிப்பை விட அதிக மதிப்புகளைக் கொண்டிருக்கும்.
• இடது மற்றும் வலது துணை மரங்களும் பைனரி தேடல் மரங்களாகவே இருக்க வேண்டும்.

இந்த பண்புகள், ஒரு சாதாரண பைனரி மரத்தை விட மதிப்புகளைத் தேடுவது, சேர்ப்பது மற்றும் நீக்குவதை வேகமாக்குகின்றன.

 

இதை முடிந்தவரை எளிதாகப் புரிந்துகொள்வதற்கும் செயல்படுத்துவதற்கும், ஒரு இருமத் தேடல் மரத்தில் உள்ள அனைத்து மதிப்புகளும் தனித்துவமானவை என்றும் நாம் கருதுவோம்.

 

The size of a tree is the number of nodes in it (n).

A subtree starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants.

The descendants of a node are all the child nodes of that node, and all their child nodes, and so on. Just start with a node, and the descendants will be all nodes that are connected below that node.

The node’s height is the maximum number of edges between that node and a leaf node.

A node’s in-order successor is the node that comes after it if we were to do in-order traversal. In-order traversal of the BST above would result in node 13 coming before node 14, and so the successor of node 13 is node 14.

ஒரு மரத்தின் அளவு என்பது அதில் உள்ள முனைகளின் எண்ணிக்கை (n) ஆகும்.

 

ஒரு துணை மரம், அந்த மரத்தில் உள்ள முனைகளில் ஒன்றை உள்ளூர் மூலமாகத் தொடங்கி, அந்த முனை மற்றும் அதன் அனைத்து வழித்தோன்றல்களையும் கொண்டிருக்கும்.

 

ஒரு முனையின் வழித்தோன்றல்கள் என்பவை அந்த முனையின் அனைத்து குழந்தை முனைகள், அவற்றின் அனைத்து குழந்தை முனைகள், மற்றும் இப்படியே தொடரும் அனைத்து முனைகளும் ஆகும். ஒரு முனையில் இருந்து தொடங்கினால் போதும், அந்த முனையின் கீழே இணைக்கப்பட்டுள்ள அனைத்து முனைகளும் அதன் வழித்தோன்றல்களாகும்.

 

ஒரு முனையின் உயரம் என்பது அந்த முனைக்கும் ஒரு இலை முனைக்கும் இடையே உள்ள விளிம்புகளின் அதிகபட்ச எண்ணிக்கையாகும்.

 

ஒரு முனையின் இன்-ஆர்டர் வாரிசு என்பது, நாம் இன்-ஆர்டர் வரிசைப்படுத்தலைச் செய்தால், அதற்குப் பிறகு வரும் முனையாகும். மேலே உள்ள BST-யில் இன்-ஆர்டர் வரிசைப்படுத்தல் செய்தால், முனை 13-க்கு முன் முனை 14 வரும், எனவே முனை 13-இன் வாரிசு முனை 14 ஆகும்.

Traversal of a Binary Search Tree / ஒரு இரும தேடல் மரத்தின் ஊடுருவல்

To check if a Binary Tree is BST, is to do an in-order traversal and check if the resulting list of values are in an increasing order.

ஒரு இரும மரம் BST தானா என்பதைச் சரிபார்க்க, அதில் இன்-ஆர்டர் டிராவர்சல் செய்து, அதன் விளைவாகக் கிடைக்கும் மதிப்புகளின் பட்டியல் ஏறுவரிசையில் உள்ளதா என்பதைச் சரிபார்க்க வேண்டும்.

 

Example

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

 

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

 

root = TreeNode(13)

node7 = TreeNode(7)

node15 = TreeNode(15)

node3 = TreeNode(3)

node8 = TreeNode(8)

node14 = TreeNode(14)

node19 = TreeNode(19)

node18 = TreeNode(18)

 

root.left = node7

root.right = node15

 

node7.left = node3

node7.right = node8

 

node15.left = node14

node15.right = node19

 

node19.left = node18

 

Traverse

inOrderTraversal(root)

 

Output :

3, 7, 8, 13, 14, 15, 18, 19,

Search for a Value in a BST / ஒரு BST-யில் ஒரு மதிப்பைத் தேடுதல்

How it works:

• Start at the root node.
• If this is the value we are looking for, return.
• If the value we are looking for is higher, continue searching in the right subtree.
• If the value we are looking for is lower, continue searching in the left subtree.
• If the subtree we want to search does not exist, depending on the programming language, return None, or NULL, or something similar, to indicate that the value is not inside the BST.

இது செயல்படும் விதம்:

 

• மூல முனையிலிருந்து தொடங்கவும்.
• இதுவே நாம் தேடும் மதிப்பாக இருந்தால், அதைத் திருப்பி அனுப்பவும்.
• நாம் தேடும் மதிப்பு அதிகமாக இருந்தால், வலது துணைமரத்தில் தேடுவதைத் தொடரவும்.
• நாம் தேடும் மதிப்பு குறைவாக இருந்தால், இடது துணைமரத்தில் தேடுவதைத் தொடரவும்.
• நாம் தேட விரும்பும் துணைமரம் இல்லை என்றால், நிரலாக்க மொழியைப் பொறுத்து, அந்த மதிப்பு BST-க்குள் இல்லை என்பதைக் குறிக்க None, அல்லது NULL, அல்லது அதுபோன்ற ஒன்றை திருப்பி அனுப்பவும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

 

def search(node, target):

if node is None:

return None

elif node.data == target:

return node

elif target < node.data:

return search(node.left, target)

else:

return search(node.right, target)

 

root = TreeNode(13)

node7 = TreeNode(7)

node15 = TreeNode(15)

node3 = TreeNode(3)

node8 = TreeNode(8)

node14 = TreeNode(14)

node19 = TreeNode(19)

node18 = TreeNode(18)

 

root.left = node7

root.right = node15

 

node7.left = node3

node7.right = node8

 

node15.left = node14

node15.right = node19

 

node19.left = node18

 

Search for a value

result = search(root, 8)

if result:

print(“Found the node with value: {result.data}”)

else:

print(“Value not found in the BST.”)

 

Output:

Found the node with value: 8

 

Insert a Node in a BST

How it works:

• Start at the root node.
• Compare each node:
• Is the value lower? Go left.
• Is the value higher? Go right.
• Continue to compare nodes with the new value until there is no right or left to compare with. That is where the new node is inserted.

 

ஒரு BST-யில் ஒரு முனையைச் செருகுதல்

இது எவ்வாறு செயல்படுகிறது:

• ரூட் முனையிலிருந்து தொடங்கவும்.
• ஒவ்வொரு முனையையும் ஒப்பிட்டுப் பார்க்கவும்:
• மதிப்பு குறைவாக உள்ளதா? இடதுபுறம் செல்லவும்.
• மதிப்பு அதிகமாக உள்ளதா? வலதுபுறம் செல்லவும்.
• ஒப்பிடுவதற்கு வலது அல்லது இடதுபுறம் எதுவும் இல்லாத வரை, புதிய மதிப்புடன் முனைகளை ஒப்பிடுவதைத் தொடரவும். அந்த இடத்தில்தான் புதிய முனை செருகப்படுகிறது.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

 

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

 

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

 

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

 

root.left = node7

root.right = node15

 

node7.left = node3

node7.right = node8

 

node15.left = node14

node15.right = node19

 

node19.left = node18

 

Inserting new value into the BST

insert(root, “Meals”)

 

Traverse

inOrderTraversal(root)

 

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

 

Find The Lowest Value in a BST Subtree

How it works:

• Start at the root node of the subtree.
• Go left as far as possible.
• The node you end up in is the node with the lowest value in that BST subtree.

ஒரு BST துணைமரத்தில் மிகக் குறைந்த மதிப்பைக் கண்டறிதல்

இது எவ்வாறு செயல்படுகிறது:

• துணைமரத்தின் மூல முனையிலிருந்து தொடங்கவும்.
• முடிந்தவரை இடதுபுறம் செல்லவும்.
• நீங்கள் சென்றடையும் முனைதான் அந்த BST துணைமரத்தில் மிகக் குறைந்த மதிப்பைக் கொண்ட முனையாகும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

 

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

 

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

 

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

 

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

 

root.left = node7

root.right = node15

 

node7.left = node3

node7.right = node8

 

node15.left = node14

node15.right = node19

 

node19.right = node18

 

Inserting new value into the BST

insert(root, “Meals”)

 

Traverse

inOrderTraversal(root)

 

Find Lowest

print(“\nLowest value:”,minValueNode(root).data)

 

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

Lowest Value: Chuttney

 

Delete a Node in a BST

How it works:

• If the node is a leaf node, remove it by removing the link to it.
• If the node only has one child node, connect the parent node of the node you want to remove to that child node.
• If the node has both right and left child nodes: Find the node’s in-order successor, change values with that node, then delete it.

ஒரு BST-யில் ஒரு முனையை நீக்குதல்

இது எவ்வாறு செயல்படுகிறது:

 

• அந்த முனை ஒரு இலை முனையாக இருந்தால், அதற்கான இணைப்பை நீக்குவதன் மூலம் அதை அகற்றவும்.
• அந்த முனைக்கு ஒரே ஒரு குழந்தை முனை மட்டும் இருந்தால், நீங்கள் நீக்க விரும்பும் முனையின் பெற்றோர் முனையை, அந்தக் குழந்தை முனையுடன் இணைக்கவும்.
• அந்த முனைக்கு வலது மற்றும் இடது என இரண்டு குழந்தை முனைகளும் இருந்தால்: அந்த முனையின் இன்-ஆர்டர் வாரிசை (in-order successor) கண்டறிந்து, அந்த முனையுடன் மதிப்புகளைப் பரிமாறிக்கொண்டு, பின்னர் அதை நீக்கவும்.

Example:

class TreeNode:

def init(self, data):

self.data = data

self.left = None

self.right = None

 

def insert(node, data):

if node is None:

return TreeNode(data)

else:

if data < node.data:

node.left = insert(node.left, data)

elif data > node.data:

node.right = insert(node.right, data)

return node

 

def inOrderTraversal(node):

if node is None:

return

inOrderTraversal(node.left)

print(node.data, end=”, “)

inOrderTraversal(node.right)

 

def minValueNode(node):

current = node

while current.left is not None:

current = current.left

return current

 

def delete(node, data):

if not node:

return None

 

if data < node.data:

node.left = delete(node.left, data)

elif data > node.data:

node.right = delete(node.right, data)

else:

Node with only one child or no child

if not node.left:

temp = node.right

node = None

return temp

elif not node.right:

temp = node.left

node = None

return temp

 

Node with two children, get the in-order successor

node.data = minValueNode(node.right).data

node.right = delete(node.right, node.data)

 

return node

 

root = TreeNode(“Sambar”)

node7 = TreeNode(“Idly”)

node15 = TreeNode(“Tamarind Rice”)

node3 = TreeNode(“Chuttney”)

node8 = TreeNode(“Juice”)

node14 = TreeNode(“Sambal Fish”)

node19 = TreeNode(“Yolk”)

node18 = TreeNode(“Zincovite”)

 

root.left = node7

root.right = node15

 

node7.left = node3

node7.right = node8

 

node15.left = node14

node15.right = node19

 

node19.right = node18

 

Inserting new value into the BST

insert(root, “Meals”)

 

Traverse

inOrderTraversal(root)

 

Delete node 15

delete(root,”Tamarind Rice”)

 

Traverse

print() # Creates a new line

inOrderTraversal(root)

 

Output:

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Tamarind Rice, Yolk, Zincovite

Chuttney, Idlly, Juice, Meals, Sambar, Sambal Fish, Yolk, Zincovite

 

Binary Search Trees take the best from two other data structures: Arrays and Linked Lists.

 

Data Structure	Searching for a value	Delete / Insert leads to shifting in memory
Sorted Array	O(logn)	Yes
Linked List	O(n)	No
Binary Search Tree	O(logn)	No

 

இரும தேடல் மரங்கள் (Binary Search Trees) மற்ற இரண்டு தரவுக் கட்டமைப்புகளான அணிவரிசைகள் மற்றும் இணைக்கப்பட்ட பட்டியல்கள் ஆகியவற்றிலிருந்து சிறந்த அம்சங்களை எடுத்துக்கொள்கின்றன.

 

தரவுக் கட்டமைப்பு	ஒரு மதிப்பைத் தேடுதல்	நீக்குதல் / செருகுதல் நினைவகத்தில் இடமாற்றத்திற்கு வழிவகுக்கிறது
வரிசைப்படுத்தப்பட்ட அணி	O(logn)	ஆம்
இணைக்கப்பட்ட பட்டியல்	O(n)	இல்லை
இருநிலை தேடல் மரம்	O(logn)	இல்லை