BINARY SEARCH TREE — FIND
I’m continuing my learning of the Binary Search Trees, so this post contains notes that I took on FINDING Data in the Binary Search Tree.
_______50_______
/ \
__25__ __75_
/ \ / \
15 35 65 85
/ \ / \ / \ / \
10 18 27 40 60 70 83 98
BINARY SEARCH TREES: FIND
There will be two Find methods
1. in the BTS class — making the initial call.
2. in the node class.
class BST {
find(data){
// this method will have a data param, which is the data we want to find in the tree.
if(this.root)
// this is to check to see if the tree is not empty. it is a boolean.
// if the tree is not empty, then search the tree for the data we want to find.
// if the tree is empty, then skip down and return false.
return this.root.find(data);
// we invoke the find() method within our node class starting at the root node.
return false
// if the tree is empty, then return false.
}
}
class Node{
find(data){
// this method will have a data param, which is the data we want to find in the tree.
if(this.data == data)
// if the data we’re looking for is equal to the data we’re currently at (this.data), then we have found the data we’re looking for and we can return true.
// if the data we’re looking for is NOT equal to the data we’re currently at (this.data), then skip down to the else if statement.
return true;
// if the data we’re looking for is equal to the data we’re currently at, then we have found the data we’re looking for and we can return true.
// if the data we’re looking for is NOT equal to the data we’re currently at from the initial ‘if statement’, then do the following
else if(data < this.data && this.left !== null)
// if one of the two conditions aren’t true, then skip down to the ‘else if statement’.
// if the data we’re looking for is less than the data we’re currently at (this.data) and if the node we’re at has a left child, then continue searching down the left subtree and do the following:
return this.left.find(data);
// if the data we’re looking for is less than the data we’re currently at (this.data) and if the node we’re at has a left child, then continue searching down the left subtree.
else if(data > this.data && this.right != null)
// if one of the two conditions from the ‘else if statement’ above aren’t true, then do the following:
// if the data we’re looking for is greater than the data we’re currently at (this.data) and if the node we’re at has a right child, then continue searching down the right subtree and do the following:
return this.right.find(data);
// if the data we’re looking for is greater than the data we’re currently at (this.data) and if the node we’re at has a right child, then continue searching down the right subtree.
return false;
// if none of the above conditions are true, that means the data does not exist in the tree and so return false.
}
}
If you wanted to retrieve an element form a tree, each time you go down one path of a tree, either the left or the right side, you are discarding about 1/2 of the tree, which allows us to find the element very fast.
Binary trees are extremely fast for insertion, deletion and accessing any element, even large trees.
Binary trees naturally stay sorted, so it is easy to get their elements in sequence.
These are the reasons why BST are very useful.
I will continue my learning of the Binary Search Tree.
