class Node
attr_accessor :data, :left, :right
def initialize(data)
@data = data
@left = nil
@right = nil
end
end
def searchNode(rootTemp, key)
if(rootTemp == nil)
return nil
end
if(rootTemp.data == key)
return rootTemp
elsif(rootTemp.data < key)
return searchNode(rootTemp.right, key)
else
return searchNode(rootTemp.left, key)
end
end
def search(key)
return searchNode($root,key)
end
def insertNode(rootTemp, key)
if (rootTemp == nil)
rootTemp = Node.new(key)
return rootTemp
end
if (key < rootTemp.data)
rootTemp.left = insertNode(rootTemp.left, key)
elsif (key > rootTemp.data)
rootTemp.right = insertNode(rootTemp.right, key)
end
return rootTemp
end
def insert(key)
$root = insertNode($root, key)
end
def inOrderNode(rootTemp)
if (rootTemp != nil)
inOrderNode(rootTemp.left)
print(rootTemp.data, " ")
inOrderNode(rootTemp.right)
end
end
def inOrder()
inOrderNode($root)
end
def deleteNode(rootTemp, key)
if (rootTemp == nil)
return rootTemp
end
if (key < rootTemp.data)
rootTemp.left = deleteNode(rootTemp.left, key)
elsif (key > rootTemp.data)
rootTemp.right = deleteNode(rootTemp.right, key)
else
if (rootTemp.left == nil)
return rootTemp.right
elsif (rootTemp.right == nil)
return rootTemp
end
rootTemp.data = minValue(rootTemp.right)
rootTemp.right = deleteNode(rootTemp.right, rootTemp.data)
end
return rootTemp
end
def delete(key)
$root = deleteNode($root, key)
end
def minValue(rootTemp)
min = rootTemp.data
while (rootTemp.left != nil)
min = rootTemp.left.data
rootTemp = rootTemp.left
end
return min
end
$root = nil
insert(16)
insert(10)
insert(25)
insert(13)
insert(18)
print("Inorder traversal: \n")
inOrder()
searchedRes = search(5)
if (searchedRes == nil)
print("\n\nThe number 5 is not present in the BST\n")
else
print("\n"+searchedRes.data+" is present in the BST\n")
end
print("\nLet us delete the element 10 from the Binary Search Tree\n")
delete(10)
print("\nInorder traversal after Deletion \n")
inOrder()
insert(3)
print("\nInorder traversal after insertion of the new element 3 : \n")
inOrder()
puts
So, we would be constructing the below Binary Search Tree :
And we have the below methods :
Firstly, we would be constructing the above Binary Search Tree, with the help of insert method..
insert(16)
So, we pass the element 16 to the insert(...) method.
And the below insert(...) method with one argument is called.
def insert(key) $root = insertNode($root, key) end
Initially, the variable root is nil as defined the constructor. Then we take the key i.e. 16 in this case. And pass the root and key to the insert method with two arguments.
def insertNode(rootTemp, key) if (rootTemp == nil) rootTemp = Node.new(key) return rootTemp end if (key < rootTemp.data) rootTemp.left = insertNode(rootTemp.left, key) elsif (key > rootTemp.data) rootTemp.right = insertNode(rootTemp.right, key) end return rootTemp end
The first line checks if the root is nil or not.
if (rootTemp == nil) rootTemp = Node.new(key) return rootTemp end
And in this case root is nil. So, we create a new Node object with the key i.e. 16.
Then assign it to the Node object root.
And return the Node root.
return root
In the next line we try to insert the element 10 in the Binary Search Tree using the insert(...) method.
insert(10)
And the insert(...) method is called.
And in the similar way we check,
if (key < rootTemp.data) rootTemp.left = insertNode(rootTemp.left, key) elsif (key > rootTemp.data) rootTemp.right = insertNode(rootTemp.right, key) end
If the key i.e. 10 is less than the root element root.data. The first condition matches.
if (key < rootTemp.data) rootTemp.left = insertNode(rootTemp.left, key)
And a recursive call is made to insert(...) method.
rootTemp.left = insertNode(rootTemp.left, key)
So, the method executes and returns the Node that contains 10, setting the value of root.left with this Node that contains 10.
Similarly, all the elements are inserted using the insert(...) method.
insert(25) insert(13) insert(18)
And the below Binary Search Tree is formed,
Then we use the inOrder() method to traverse the Binary Search Tree.
inOrder()
Next, we search, if the element 5 is present in the Binary Search Tree using the search(...)method.
searchedRes = search(5)
And the search(...) method with one argument is called.
def search(key) return searchNode($root,key) end
And the search(...) method with two arguments is called with the key element as 5(i.e The element to be searched).
def searchNode(rootTemp, key) if(rootTemp == nil) return nil end if(rootTemp.data == key) return rootTemp elsif(rootTemp.data < key) return searchNode(rootTemp.right, key) else return searchNode(rootTemp.left, key) end end
So, there are a couple of if statements, where the first if statement checks if the root element is nil or not.
if(rootTemp == nil) return nil end
In this case the root element is 16. So, we go to the next if statement that checks if the key element 5 (i.e. The element to be searched), is equal to the root element or not.
if(rootTemp.data == key) return rootTemp
In this case the root element is 16 which is not equal to the element that needs to be searched.
So, the next if statement checks, if the element that needs to be searched(i.e. 5) is greater than the root element(i.e. 16) or not.
elsif(rootTemp.data < key) return searchNode(rootTemp.right, key)
In this case 5 is less than 16. So, even this condition is not satisfied.
The logic behind this if statement is to check, if the element to be searched is greater than the root element or not. If the element to be searched, is greater than the root element then it should be on the right side of the tree and we are suppose to search there.
Now, since 5 is less than 16. We come to the final else statement. Which assumes that the element to be searched (i.e. 5) is less than the root element (i.e. 16) and must be on the left hand side.
else return searchNode(rootTemp.left, key)
Now, in this else statement, a recursive call is made to the search(root.left, key) method. So, the assumption is that the element 5 should be in the Left Sub-Tree.
And the Node search(Node root, int key) method is called again with the root as 10.
The same way all the if statements are executed and finally, the element 5 is not found in the Binary Search Tree.
Next, we try to delete the element 10 from the Binary Search Tree.
delete(10)
Calling the delete(...) method.
Similarly, in this case, delete(...) method with one argument is called,
def delete(key) $root = deleteNode($root, key) end
And the deleteNode(...) method with two arguments is called.
def deleteNode(rootTemp, key) if (rootTemp == nil) return rootTemp end if (key < rootTemp.data) rootTemp.left = deleteNode(rootTemp.left, key) elsif (key > rootTemp.data) rootTemp.right = deleteNode(rootTemp.right, key) else if (rootTemp.left == nil) return rootTemp.right elsif (rootTemp.right == nil) return rootTemp end rootTemp.data = minValue(rootTemp.right) rootTemp.right = deleteNode(rootTemp.right, rootTemp.data) end return rootTemp end
So, we are trying to delete the element 10 from the Binary Search Tree. So, the key is 10 that we have passed to the delete(...) method.
The delete(...) method is almost same as the search(...) method.
In the search(...) method, we have located the element to be searched. Even in delete(...) method, we will locate the element first(The code is exactly same as the search(...) method). Then call the minValue(root.right) method
The minValue(...) method will find the inorder-successor. i.e. When we delete the element, we need to find a replacement of it, so that the Binary Search Tree properties should be intact.
Thus, we go to the Right Sub-Tree of the element to be deleted. And as we know the Right Sub-Tree contains all the elements that are greater than the root element. So, we have to find the smallest element from the Right Sub-Tree..
And, as we know the smallest element of the Right Sub-Tree resides on the leftmost leaf.
And that's exactly what we will find in def minValue(root) method.
def minValue(rootTemp) min = rootTemp.data while (rootTemp.left != nil) min = rootTemp.left.data rootTemp = rootTemp.left end return min end