Course Content
Data Structure & Algorithms PART I
Data Structure & Algorithms PART I
BST
| Operation | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Memory Complexity |
Search | O(log n) | O(log n) | O(n) | O(n) |
Insertion | O(log n) | O(log n) | O(n) | O(n) |
Deletion | O(log n) | O(log n) | O(n) | O(n) |
A binary Search Tree is a type of Binary tree. Let’s study the table to understand the difference between these trees.
| **** | Binary Tree | Binary Search Tree |
Definition | A Binary Tree is a non-linear data structure in which a node can have 0, 1, or 2 nodes. Individually, each node consists of a left pointer, right pointer, and data element | A Binary Search Tree is an organized binary tree with a structured organization of nodes. Each subtree must also be of that particular structure |
Structure | There is no required organization structure of the nodes in the tree | The values of left subtree of a particular node should be lesser than that node and the right subtree values should be greater |
Operations | The operations that can be performed are deletion, insertion and traversal | As these are sorted binary trees, they are used for fast and efficient binary search, insertion and deletion |
Types | Complete BT, Full BT, Balanced BT... | AVL tree, Splay tree, T-tee... |
So look at a cool and real Binary search tree (BST later) - picture.
Let’s talk more about BST.
We have talked briefly about the structure of each node in the binary tree:
- Data;
- Left pointer;
- Right pointer.
Why a binary tree?
Imagine that we need to find some information about a particular company employee.
How would we act? Let's take a large array, where there are all the company employees, perhaps sort it, and then it will get the information we need.
But every time a new employee joins the company, we will need to sort again, possibly, and in the worst case, look for this person in a heap again for a long time.
Imagine that when a new employee enters the company, we have a ‘cell’ for this employee. And the cell is not simple: it is in a specific structure in a particular place. And when we want to find a person, we do not go through everything, but simply go through this structure looking for a person in the desired cell. This idea is based on the principle of operation of a binary search tree.
Let’s imagine that our employees have numbers. Each employee has a unique number.
In the first case, we discussed that finding the employee with the 10 keys would be hard.
In the second case, due to the rules of the BST, we will need to make only some moves answering questions Yes/No to get to the node we need. picture
Moreover, inside every node, we can store much information!
We can even add the day when the first employee’s tooth was deleted! Isn’t it amazing?
Operations:
The average case of time complexity of these operations is O (log n).
In the table, you have probably noticed that there are many types of BSTs.
We will learn some of them and, of course, how to implement them!
And now it is time for the test!
Thanks for your feedback!
