An Interest In:
Web News this Week
- April 1, 2024
- March 31, 2024
- March 30, 2024
- March 29, 2024
- March 28, 2024
- March 27, 2024
- March 26, 2024
June 28, 2021 11:43 pm GMT
Original Link: https://dev.to/ayabouchiha/part-4-insertion-search-in-binary-search-tree-4h44
part 4: insertion, search in binary search tree0
hi, this is part 4 of the tree data structure we'll explain binary search tree operations with their implementation such as insertion, and search.
In the next post, we will talk about the deletion.
#day_16
Insertion in the binary search tree
- Let's say we want to insert 17 in this binary search tree.
20 / \ 12 23 / \ / \7 15 21 35
- Since 17 < 20, we will go to the left sub-tree.
- 17 > 12, we will go the right.
- 17 > 15 and the no more child in the right's why we will go to the right and insert it.so this binary search tree above will be like this:
20 / \ 12 23 / \ / \7 15 21 35 \ 17
The insert approach
- We need to know that the inserted node will be always one of the binary search tree leaves.
- while the root is None(null) store the previous root in a variable
- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
root = root. right
- else (that means the previousRoot is greater than or equal the elementToInsert) move to the root of the left sub-tree
root = root. left
- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
- When the loop break (stop), the previous root will be:
- case 1:
previousRoot = None
if the binary search tree is empty. so the previousRoot will be the new NodepreviousRoot = Node(elementToInsert)
- case 2:
previousRoot < elementToInsert
if the previousRoot is less than the elementToInsert, so the node will be the right child of the previousRootpreviousRoot.right = elementToInsert
- case 3:
previousRoot >= elementToInsert
if the previousRoot is greater than or equal the elementToInsert, so the node will be the left child of the previousRootpreviousRoot.left = elementToInsert
- case 1:
Implementation of insert using python
def insert(elementToInsert: int, root = None): # new node TheNewNode = Node(elementToInsert) previousRoot = None while root is not None: previousRoot = root # if the root's value is less than elementToInsert if root.value < elementToInsert: # the root variable will be the root of the right sub-tree root = root.right # if the root value is greater than or equal elementToInsert else: # the root variable will be the root of the left sub-tree root = root.left # if the binary search tree is empty if previousRoot is None: previousRoot = TheNewNode # if the previous root value is greater than or equal the elementToInsert elif previousRoot.value >= elementToInsert: # the new node will be its left child previousRoot.left = TheNewNode # if the previous root value is less than the elementToInsert else: # the new node will be its right child previousRoot.right = TheNewNode return TheNewNode
Search in the binary search tree
We want to search for example the number 21
20 / \ 12 23 / \ / \7 15 21 35
- start from the root and compare its value with the wanted number (20 < 21), so we will go to the right sub-tree and compare its root with the wanted element.
- (23 > 21), that's why we will go to the left sub-tree and compare its root with the wanted element.
- since (21 == 21), will return the node
the search approach
- compare the root value with the wanted element.
- If the root is None (null) that means the element is not found return False.
- Else If the root is equal to the wanted element return the root.
- Else If the root is greater than it, return the same function with these arguments:(root of the left sub-tree, wanted element)
- Else (that means the root is less than the wanted element) return the same function with these arguments:(root of the right sub-tree, wanted element)
implementation of the search algorithm in the binary search tree
# If there are no more nodes. # that means the node value will be None(null) # that means the wanted element doesn't exist if root == None: # the wanted element is not found so return False return False # if the root value is equal to the wanted element # that means the wanted element is found if root.value == wantedElement: # return the node return root # if the root value is smaller than the wanted element if root.value < wantedElement: # return the same function with the root of the right sub-tree return search( wantedElement, root.right) # if the root value is greater than or equal the wanted element if root.value >= wantedElement: # return the same function with the root of the left sub-tree return search( wantedElement, root.left)
Happy coding! see you next post (we will discuss deletion)
References and useful resources
Original Link: https://dev.to/ayabouchiha/part-4-insertion-search-in-binary-search-tree-4h44
Share this article:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To