An Interest In:
Web News this Week
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
- April 19, 2024
- April 18, 2024
- April 17, 2024
Some of Our Sources
- Techcrunch
- Technology Review
- TutsPlus - Code
- Joshua Blankenship
- Spoon Graphics
- Vandelay Design
- Noupe
- Spyre Studios
- Android Dissected
- TechPowerUp
Help Webnuz
Referal links:
Binary Search Tree Series Part 2
Find or Search Implementation.
When looking for a node with a particular value on the tree, the arrangement of the nodes where the lesser value than the parent node. This means there is a particular optimization done when storing data in a binary tree. After every iteration when looking for the node the number of possible nodes is halved. This lets us get to the solution much more quickly.
Example.
Given we have 1000,000 elements in our data stored in an array and the array is sorted. Assume the node we are searching for is near the end of the let's say 1000,000nth node, Instead of making 1 million comparisons looking the for the node since we know our array is sorted we would compare our value with the middle value in the array, if the value is greater than the middle value then we would know the value most probably exists in the top half of the array(from element 500,000- 1000,000) I say probably because the value might not exist at all in our data and we have to account for the possibility. By gaining this key insight we can ignore the bottom half of our array and make the next comparisons between our target value and the middle value in the top half of the array which would be the 750,000th element. We do this iteratively until we find or value or reach the end in which we return -1 or not found. This search methodology is faster because it always is eliminating half the search data where there is 100% certainty the value does not exist.from 1000,000, to 500,000 ... 250,000... 125,000,
The time complexity becomes O(log n) instead of O(n^2). See the below
as a reference.
This is exactly how the search works in a tree.
Pseudo Code/ Steps to follow:
- First create variables current, it to the root node and found set it to false.
- Start looping while the current node exists and the found variable is still false.
- If the value is less than the value stored in the current node then set current to the left property of the current variable
- If the value is greater than the current's value property then set the current to the current variable right property.
- Otherwise set found variable to true.
- outside the while check if the found is still false then return undefined if it is, otherwise returns the current variableCode implementation in JavaScript:
class Node{ constructor(val){ this.val = val; this.left = null; this.right = null; }}class BST{ constructor(){ this.root = null; }// implementation and explanation in the first part of the //series. insert(val){ let newNode = new Node(val); if(!this.root){ this.root = newNode; }else{ let current = this.root; while(true){ if(val < current.val){ if(current.left === null){ current.left = newNode; return this }else{ current = current.left; } }else{ if(current.right === null){ current.right = newNode; return this }else{ current = current.right } } } } } find(val){ let current = this.root; let found = false; while(current && !found){ if(val < current.val){ current = current.left; } }else if(val > current.val){ current = current.right; }else{ found = true } } if(!found) return undefined return current } }In Python:-
class Node: def __init__(self,val): self.val = val self.left = None self.right = Noneclass BST: def __init__(self): self.root= None def insert(self, val): newNode = Node(val) if self.root == None: self.root= newNode else: current = self.root while True: if val< current.val: if current.left == None: current.left = newNode return self else: current= current.left else: if(current.right == None): current.right = newNode return self else: current = current.right def find(self, val): current= self.root found = False while current and not found: if val < current.val: current = current.left elif val > current.val: current= current.right else: found = True if(not found): return "not found" return currentbst = BST()bst.insert(100)bst.insert(200)bst.insert(150)bst.insert(175)bst.insert(160)bst.insert(180)bst.insert(75)bst.insert(50)bst.insert(65)bst.insert(40)bst.insert(55)bst.insert(20)print(bst.find(21))Next in this series, we will take a look at the search Methodologies. Starting with Breadth-First Search.
Original Link: https://dev.to/edwardcashmere/binary-search-tree-series-part-2-503k
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To