Aug 19, 2021
Binary Search Trees
Introduction to Binary Search Trees
What do you want to know about tree data structure?
A binary search tree is a very versatile data structure and it is faster when inserting, removing, and searching elements.
As you can see in the image there can be only one root node all other nodes are accessed by using the root node. C is the parent node of F and G nodes, which are considered child nodes. These nodes can have two child nodes, but not more than that. Some nodes can exist without child nodes that are considered leaf nodes.
What are the properties of a Binary Tree?
- The left subtree of a node contains only nodes with keys, that are lesser than the node’s key.
- The right subtree of a node contains only keys that are greater than the node’s key.
- Left and right subtree each must also be a binary search tree.
What are the applications of Binary Trees?
Binary trees are mostly employed in computing for searching and sorting since they allow data to be stored hierarchically. Insertion, deletion, and traversal are some of the most frequent operations that may be performed on binary trees.
What are the benefits?
- An excellent complement to the hierarchical data storage method.
- The structural linkages that exist in the supplied data set should be reflected.
- Compared to linked lists and arrays, make insertion and deletion faster.
- A versatile method of storing and transporting data.
- It can store a large number of nodes.
How to implement a Binary Tree?
We’ll use an auxiliary Node class that will store int values. And keep a reference to each child:
class Node {
int value;
Node leftChild;
Node rightChild; Node(int value) {
this.value = value;
rightChild = null;
leftChild = null;
}
}
Then we’ll add the starting node of our tree, usually called the root:
public class BinaryTree { Node root; // ...
}
What are the basic operations?
What is a Binary Search Tree?
A binary search tree, also known as an ordered or sorted binary tree in computer science, is a rooted binary tree data structure in which each internal node stores a key that is larger than all keys in the node’s left subtree but less than those in the node’s right subtree.
What is the difference between a Binary tree and a Binary Search Tree?
A Binary Tree is a simple structure with the simple constraint that no parent can have more than two offspring, but a Binary Search Tree is a version of the binary tree that follows a certain order in which the nodes should be ordered.
In my next article, I hope to explain these basic operations of Binary Trees. So happy coding!!
