UNIT-3
1. Tree (Definition, terminology)
2. Binary tree
3. Binary search tree
4. AVL tree
5. B tree
6. B+tree
7. Tries
TREE
Tree data structure is a hierarchical structure that is used to represent and organize
data in a way that is easy to navigate and search.
It is a collection of nodes that are connected by edges and has a hierarchical
relationship between the nodes.
The topmost node of the tree is called the root, and the nodes below it are called the
child nodes.
Each node can have multiple child nodes, and these child nodes can also have their
own child nodes, forming a recursive structure.
Trees goes from top to bottom
It is represented with or without direction
With direction without direction
Links are Unidirectional
Node: which are going to store some information with or without direction
Terminology
BINARY TREE (definition, properties, types, traversal, creating)
A Binary Tree Data Structure is a hierarchical data structure in which each node
has at most two children, referred to as the left child and the right child.
The topmost node in a binary tree is called the root, and the bottom-most nodes
are called leaves.
A binary tree can be visualized as a hierarchical structure with the root at the top
and the leaves at the bottom.
Representation of Binary Tree
Each node in a Binary Tree has three parts:
Data
Pointer to the left child
Pointer to the right child
Example
Properties of Binary Tree
The maximum number of nodes at level L of a binary tree is 2L
The maximum number of nodes in a binary tree of height H is 2H – 1
Total number of leaf nodes in a binary tree = total number of nodes with 2 children +
1
In a Binary Tree with N nodes, the minimum possible height or the minimum number
of levels is Log2(N+1)
A Binary Tree with L leaves has at least | Log2L |+ 1 levels
Types of Binary Tree
1. Full Binary Tree
A Binary Tree is a full binary tree if every node has 0 or 2 children.
A full Binary tree is a special type of binary tree in which every parent node/internal
node has either two or no children. It is also known as a proper binary tree.
2. Degenerate (or pathological) tree
A Tree where every internal node has one child.
A degenerate or pathological tree is a tree having a single child either left or right.
3. Complete Binary Tree
A Binary Tree is a Complete Binary Tree if all the levels are completely filled except
possibly the last level and the last level has all keys as left as possible.
A complete binary tree is just like a full binary tree, but with two major differences:
Every level except the last level must be completely filled.
All the leaf elements must lean towards the left.
The last leaf element might not have a right sibling i.e. a complete binary tree doesn’t
have to be a full binary tree.
4. Perfect Binary Tree
A Binary tree is a Perfect Binary Tree in which all the internal nodes have two
children and all leaf nodes are at the same level.
The following are examples of Perfect Binary Trees.
A perfect binary tree is a type of binary tree in which every internal node has exactly
two child nodes and all the leaf nodes are at the same level.
Class notes
Binary tree traversal
Tree Traversal techniques include various ways to visit all the nodes of the tree.
Inorder Traversal:
o Inorder traversal visits the node in the order: Left -> Root -> Right
Preorder Traversal:
o Preorder traversal visits the node in the order: Root -> Left -> Right
Postorder Traversal:
o Postorder traversal visits the node in the order: Left -> Right -> Root
Creating Binary tree using Preorder and Inorder
BINARY SEARCH TREE (Definition, creation, Insertion, Deletion)
A Binary Search Tree is a data structure used in computer science for organizing and storing
data in a sorted manner. Each node in a Binary Search Tree has at most two children, a left
child and a right child, with the left child containing values less than the parent node and the
right child containing values greater than the parent node. This hierarchical structure allows
for efficient searching, insertion, and deletion operations on the data stored in the tree.
AVL TREE
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be more than
one.
The difference between the heights of the left subtree and the right subtree for any
node is known as the balance factor of the node.
Rotating the subtrees in an AVL Tree:
An AVL tree may rotate in one of the following four ways to keep itself balanced:
Left Rotation:
When a node is added into the right subtree of the right subtree, if the tree gets out of balance,
we do a single left rotation.
Right Rotation:
If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance,
we do a single right rotation.
Left-Right Rotation:
A left-right rotation is a combination in which first left rotation takes place after that right
rotation executes.
Right-Left Rotation:
A right-left rotation is a combination in which first right rotation takes place after that left
rotation executes
Difference between B-Tree and B+tree:
