Arab Academy for Science, Technology & Maritime Transport

College of Artificial Intelligence ━━━━━ Alamein Campus

Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

Binary Search Tree

Name Registration Number

Miral Metwally Elnakib 20102753

1
Table of Contents
1) History and definition ……………………………………………… 3

2) Operations Steps (Algorithm) and complexity…………………… 4

2.1 Creatin…………………………………………………………………………………. 4

2.2 Insertion……………………………………………………………………………........ 5

2.3 Deletion………………………………………………………………………………… 6

2.4 Modify………………………………………………………………………………….... 7

2.5 Search…………………………………………………………………………………… 8

3) Applications…………………………………………………………. 9

4) References…………………………………………………………….10

2
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

1) History and Definition

The splay tree is a form of self-adjusting binary search tree invented by Sleator and Tarjan. Splay
trees are as effective as both dynamically balanced and static optimum search trees on any
sufficiently long access sequence, to within a constant factor Sleator and Tarjan have proposed a far
more powerful hypothesis: splay trees are as effective as any kind of dynamically modified search
tree on any sufficiently long access sequence and to within a constant factor. Accessing the items
in a splay tree in sequential order takes linear time, i.e., O (1) time per access, according to this
dynamic optimality conjecture.

A binary search tree, like Linked Lists, is a data structure made up of nodes. These nodes are either
empty or contain connections to other nodes (links). These other nodes are called a left node and a
right node, respectively. Values are assigned to nodes. These numbers decide where they'll get into
the BST(binary search tree).Each node is referenced by only one other node, its parent, similar to a
linked list (except for the root node). As a result, we can assume that each node in a BST is a BST
in and of itself. We meet another node further down the tree, and that node has a left and a right.
The node then has a left and a right depending on which way we go, and so on. The size of the left
node is often smaller than the size of its parent, the right node still exceeds the number the parent.,
A BST is called balanced if, with the exception of the last level, every level of the tree is completely
filled. The tree is filled from left to right on the final stage. A perfect BST is both full and complete
(all child nodes are on the same level, and each node has a left node).

3
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

2) Operations Steps (Algorithm) and complexity

2.1 Creation

The creation of binary search tree takes O (log n) time to complexity. Binary search algorithm often
operates on a sorted list. As a result, the first logical step is to sort the given list. After sorting, the
list's median is compared to the desired value.

• If the desired value is equal to the value of the central index, the index is returned as a response.
• If the target value is less than the list's central index contract, then the right side of the list is
ignored.
• If the optimal value exceeds the value of the central index, the left half is discarded.
• After that, the procedure is replicated on shorter lists until the goal value is discovered.

4
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

2.2 Insertion operation

The insertion operation in a binary search tree takes O (log n) time to complexity. A new node is
always inserted as a leaf node in a binary search tree. The following is how the insertion procedure
is carried out...

• Step 1 - Create a new Node with given value and set its left and right to NULL.
• Step 2 - Check whether tree is Empty.
• Step 3 - If the tree is Empty, then set root to new Node.
• Step 4 - If the tree is Not Empty, then check whether the value of new Node
is smaller or larger than the node (here it is root node).
• Step 5 - If new Node is smaller than or equal to the node then move to its left child. If
new Node is larger than the node then moves to its right child.
• Step 6- Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).
• Step 7 - After reaching the leaf node, insert the new Node as left child if the new Node
is smaller or equal to that leaf node or else insert it as right child.

5
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

2.3 Modify
To begin building a tree, we must first construct a new form of node with left and right properties.
This node object is similar to the node objects that are found in lists. The only difference is that
instead of one connection, the new node object has two. It always has a value, and the same getters
and setters are used to control its values.

We can use a Tree node to build a BST object once we've implemented it. An operation to insert
values and an operation to delete values are the two key operations we want to implement for our
BST object. We can quickly expand the systems to add more later once we have these two
operations.

BST object will only have one resource, which will be the tree's base. All other values within the
tree can be determined by iterating the root at any time. Recursion is used to enforce the insert
process, as it is with almost every tree method. Let's look at an example to get a better understanding
of what we need to do with our insert process.

6
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

2.4 Deletion Operation

In a binary search tree, the deletion operation is performed with O (log n) time complexity. Deleting
a node from Binary search tree includes following three cases...

• Case 1: Deleting a Leaf node (A node with no children).

• Case 2: Deleting a node with one child.
• Case 3: Deleting a node with two children.

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

• Step 1 - Find the node to be deleted using search operation.

• Step 2 - Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child

We use the following steps to delete a node with one child from BST...

• Step 1 - Find the node to be deleted using search operation.

• Step 2 - If it has only one child then create a link between its parent node and child node.
• Step 3 - Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children

We use the following steps to delete a node with two children from BST...

• Step 1 - Find the node to be deleted using search operation.

• Step 2 - If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.
• Step 3 - Swap both deleting node and node which is found in the above step.
• Step 4 - Then check whether deleting node came to case 1 or case 2 or else go to step 2.
• Step 5 - If it comes to case 1, then delete using case 1 logic.
• Step 6- If it comes to case 2, then delete using case 2 logic.
• Step 7 - Repeat the same process until the node is deleted from the tree.

7
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

2.5 Search Operation

In a binary search tree, the search operation is performed with O (log n) time complexity. The
search operation is performed as follows...

• Step 1 - Read the search element from the user.

• Step 2 - Compare the search element with the value of root node in the tree.
• Step 3 - If both are matched, then display "Given node is found!!!" and terminate the
function
• Step 4 - If both are not matched, then check whether search element is smaller or
larger than that node value.
• Step 5 - If search element is smaller, then continue the search process in left subtree.
• Step 6- If search element is larger, then continue the search process in right subtree.
• Step 7 - Repeat the same until we find the exact element or until the search element is
compared with the leaf node
• Step 8 - If we reach to the node having the value equal to the search value then
display "Element is found" and terminate the function.
• Step 9 - If we reach to the leaf node and if it is also not matched with the search
element, then display "Element is not found" and terminate the function.

8
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Camp
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

3) Applications of BST
BSTs are used for a lot of applications due to its ordered structure.

• BSTs are used for indexing and multi-level indexing.

• They're also useful for implementing different search algorithms.
• It's useful for keeping a sorted stream of data.
• Internally, self-balancing BSTs are used to implement Tree Map and Tree Set data structures.

9
 Arab Academy for Science, Technology & Maritime Transport
College of Artificial Intelligence ━━━━━ Alamein Campus
Course code GN121 Data Structures & Algorithms April 2021
Lecturer Prof. Dr. Osama Ismail
Teaching assistant Nagy Khairat Aly

4) References
• https://link.springer.com/content/pdf/10.1007/BF02579253.pdf

• https://afteracademy.com/blog/binary-search-tree-introduction-operations-and-

applications

• https://www.freecodecamp.org/news/data-structures-101-binary-search-tree-

398267b6bff0/

• https://www.upgrad.com/blog/binary-search-

algorithm/#:~:text=Learning%2C%200%25%20EMI-

,Time%20and%20Space%20complexity,values%20not%20in%20the%20list.

10