Content of slide
Tree
Binary tree Implementation
Binary Search Tree
BST Operations
Traversal
Insertion
Deletion
Types of BST
Complexity in BST
Applications of BST
1 of 126
Downloaded 2,189 times
More Related Content
Binary Search Tree in Data Structure
1. Click to add Title
e-Infochips Institute of Training Research and Academics Limited
Binary Search Tree
Guided By:-
Mrs. Darshana Mistry
Presented By:-
Dharita Chokshi
Disha Raval
Himani Patel
2. Outlines
Tree
Binary tree Implementation
Binary Search Tree
BST Operations
Traversal
Insertion
Deletion
Types of BST
Complexity in BST
Applications of BST
3. Trees
Tree
Each node can have 0 or more children
A node can have at most one parent
Binary tree
Tree with 02 children per node
Also known as Decision Making Tree
4. Trees
Terminology
Root no parent
Leaf no child
Interior non-leaf
Height distance from root to leaf (H)
5. Why is h important?
The Tree operations like insert, delete, retrieve etc. are
typically expressed in terms of the height of the tree h.
So, it can be stated that the tree height h determines
running time!
6. Binary Tree Implementation
Class Node
{
int data; // Could be int, a class, etc
Node *left, *right; // null if empty
void insert ( int data ) { }
void delete ( int data ) { }
Node *find ( int data ) { }
}
7. Binary Search Tree
Key property is value at node
Smaller values in left subtree
Larger values in right subtree
Example
X > Y
X < Z
Y
X
Z
9. Difference between BT and BST
A binary tree is simply a tree in which each node can have at
most two children.
A binary search tree is a binary tree in which the nodes are
assigned values, with the following restrictions :
1. No duplicate values.
2. The left subtree of a node can only have values less than
the node
3. The right subtree of a node can only have values greater
than the node and recursively defined
4. The left subtree of a node is a binary search tree.
5. The right subtree of a node is a binary search tree.
10. Binary Tree Search Algorithm
TREE-SEARCH(x,k)
If x==NIL or k==x.key
return x
If k < x.key
return TREE-SEARCH(x.left,k)
else
return TREE-SEARCH(x.right,k)
121. AVL Tree
AVL tree is a self-balancing Binary Search Tree (BST)
where the difference between heights of left and right
subtrees cannot be more than one for all nodes.
122. Red Black Tree
Every node has a color
either red or black.
Root of tree is always
black.
There are no two
adjacent red nodes (A red
node cannot have a red
parent or red child).
Every path from root to a
NULL node has same
number of black nodes.
124. Complexity in BST
Operation Average Worst Case Best Case
Search O(log n) O(n) O(1)
Insertion O(log n) O(n) O(1)
Deletion O(log n) O(n) O(1)
125. Applications of BST
Used in many search applications where data is
constantly entering/leaving, such as the map and set
objects in many languages' libraries.
Storing a set of names, and being able to lookup based
on a prefix of the name. (Used in internet routers.)
Storing a path in a graph, and being able to reverse any
subsection of the path in O(log n) time. (Useful in
travelling salesman problems).
Finding square root of given number
allows you to do range searches efficiently.