Tree data structure: Binary Search Tree
Tree
A tree is a data structure that consists of nodes connected by edges.
Tree data structures are non-linear data structures, and they allow us to implement algorithms much faster than when using linear data structures.
Binary tree
A Binary tree can have two children: a left node and a right node. Every Node contains two elements: a key used to identify the data stored by the Node and a value that is the data contained in the Node. The following figure shows the binary tree terminology.
Binary search tree
The most common type of Binary tree is the Binary search tree, which has two main characteristics:
· The left Node's value must be less than its parent's value.
· The value of the right Node must be greater than or equal to the value of its parent.
Moreover, you can search in a tree data structure quickly, as you can with an ordered array, and insert and delete items quickly, as you can with a linked list.
Finding a value takes a maximum of log2(N) attempts. As the collection of nodes gets large, the binary search tree becomes faster over a linear search which takes up to (N) comparisons.
Binary search tree: Use Case
A company can use the Global Trade Item Number (GTIN) to identify its trade items uniquely.
The GTIN can identify the types of products that different manufacturers produce.
A Webshop wants to retrieve information about GTINs efficiently using a binary search algorithm.
Solution
We create a Product Class, the data contained in a Node.
We create a NodeP Class to store a list of Products. Moreover, this Class allows us to have two NodeP attributes to hold the left and right nodes.
We create a TreeP Class to implement an abstract data type called binary search tree, which includes a NodeP root variable for the first element to be inserted. We need to implement an insert method, where every time a new GTIN is inserted, it compares the current GTIN versus the new GTIN. Depending on the result, we store the new GTIN on the left or right Node. In this way, the insert method maintains an ordered binary search tree.
A Test case to verify our assumptions:
And here is the implementation for the insert method:
We create a Test case for the find method.
And here is the implementation that shows a find method (the gtin parameter is our key), which iterates through all nodes until a GTIN is found. This algorithm reduces the search space to N/2 because the binary search tree is always ordered.
This Binary Search Tree works well when the data is inserted randomly. Therefore, when the values to be inserted are already ordered, a binary tree becomes unbalanced. With an unbalanced tree, we can not find data quickly.
One approach to solving unbalanced trees is the red-black tree technique, a binary search tree with some special features.
Assuming that we already have a balanced tree, the following algorithm shows us how fast in terms of comparisons could be a binary search tree that depends on a number N of elements. For instance, in 1 billion products, to find a product by GTIN, the algorithm needs only 30 comparisons. See Big O Notation.
Here is our assumption.
And here is our implementation.
Learn to traverse a Tree in this link and the inner workings of other data structures and algorithms easily.
If you consider that one of my stories was useful and want to support me as a writer, join as a Medium member with my referral link!.
I like to share my knowledge and experience in Java Programming, Big O Notation, Algorithms, Coding interview, Data Structures, Clean Code, SOLID Principles, Distributed Systems, Spring Framework, Web Services, and other Tech topics.
Originally published at https://codersite.dev on May 12, 2020.
