TREES

BALANCED SEARCH TREE

 A balanced binary tree is the one with every node not having
much of difference in height of left and right subtree.
 Searching and Traversing will be much more efficient if the
tree is balanced.
 Normal Binary Search Tree may become unbalanced if the
keys are in sorted order while inserting.
 For making a balanced search tree, different types of
balancing trees are used. Some of them are:
 Some of them are:
 AVL Balanced Trees
 Red-Black Trees
 B-Trees
2
 AVL TREES
 Named after its two Soviet inventors, G. M. Adelson-Velskii and
E. M. Landis
 AVL tree is the self balancing binary search tree in which
 the heights of the two child subtrees of any node differ by at most one
 Every subtree is itself an AVL Tree
 If the difference in more than one, then the tree is rebalanced by
applying certain rules of rotation
 Hence for an AVL tree:

|HL-HR|<=1
where HL and HR are the heights of left and right subtrees for any given
node

3
AVL TREES…

-1
1 0

2 -2 0 -1
0 1
1 -1 0
0 0
0 0
0

4
ALGORITHM FOR CREATING AVL TREES
1. Start
2. Insert a NewNode into the tree using normal BST insertion
algorithm
3. Trace the path from newly inserted leaf towards the root
4. For each node ‘x’ encountered, check if the height of left(x)
and right(x) differ by atmost 1
1. If yes, proceed to parent node of ‘x’, until root node is visited
2. If not, restructure the tree by doing rotation either single or
double
5. Continue until all nodes are inserted
6. Stop

5
RULES OF ROTATION
 Compute balance factor(BF) as follows:
bf = height of left subtree – height of right subtree
 There are 4 kinds of rotation which are implemented
using 2 different rotation function
 BF = +2 means that the node is unbalanced because of
the left subtree of the node and there will be one right
rotation for sure.
 BF = -2 means that the node is unbalanced because of
the right subtree of the node and there will be one left
rotation for sure.
 Whether a single rotation needs to be done or whether
the tree needs to be rotated twice depends upon the
balance factor of the child of the root of the subtree that
is unbalanced. 6
RULES OF ROTATION…
 The 4 kinds of rotation are:
 left – left rotation: If balance factor(BF) of point is 2
and the BF of the left child is > 0
 a single ‘right’ rotation
 left – right rotation: If BF of point is 2 and the BF of
the left child is < 0
 a ‘left’ rotation followed by a ‘right’ rotation
 right – left rotation: If BF of point is -2 and the BF
of the left child is > 0
 a ‘right’ rotation followed by a ‘left’ rotation
 right – right rotation: If BF of point is -2 and the BF
of the left child is < 0
 a single ‘left’ rotation 7
ROTATION EXAMPLE…
Left-Right Rotation & Left-Left Rotation
+2

-1
Rotate left
0

Left-right condition Left-left condition

Rotate right

8
ROTATION EXAMPLE…
Right-Left Rotation & Right-Right Rotation
-2

+1

Rotate right
0

Right-left condition Right-Right condition

Rotate left

9
 AVL TREE EXAMPLE…
+2

-1

Rotate left

18
18

Left-right condition

Rotate right

18
10
AVL TREE EXAMPLE…

11
LEFT ROTATION
Node* leftRotate(Node* x)
{
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;

// Update heights
updateHeight(x);
updateHeight(y);

return y; // new root

12
}
RIGHT ROTATION
Node* rightRotate(Node* y)
{
Node* x = y->left;
Node* T2 = x->right;

x->right = y;
y->left = T2;

// Update heights
updateHeight(y);
updateHeight(x);

return x; // new root

13
}
LEFT RIGHT ROTATION
Node* leftRightRotate(Node* z)
{
z->left = leftRotate(z->left);
return rightRotate(z);
}

14
RIGHT LEFT ROTATION
Node* rightLeftRotate(Node* z)
{
z->right = rightRotate(z->right);
return leftRotate(z);
}

15
 typedef struct Node
UPDATE HEIGHT {
int data;
void updateHeight(Node* node) struct Node* left;
{ struct Node* right;
struct Node* parent;
int hl = 0, hr = 0;
int height;
if (node->left)
} Node;
hl = node->left->height;
else
hl = 0;
Node* createNode(int data, Node* parent) {
if (node->right) Node* node = (Node*)malloc(sizeof(Node));
hr = node->right->height; node->data = data;
else node->left = NULL;
hr = 0; node->right = NULL;
node->parent = parent;
if (hl > hr)
node->height = 1;
node->height = hl + 1; return node;
else }
node->height = hr + 1;
16
}
AVL TREE
 Create BST and AVL Balanced tree from the following set of data:
 10, 20, 30, 35, 50, 70, 40, 80, 60, 65
 3, 5, 11, 8, 4, 1, 12, 7, 2, 6, 10
 14, 12, 18, 23, 4, 44, 64, 66
 14, 12, 8, 18, 20, 23, 44, 52
 H, I, J, B, A, E, C, F, D, G, K, L

17
 HUFFMAN CODES
Huffman coding uses a variable-length code to compress the file.

Huffman codes are prefix codes, which means that all bit patterns
are unambiguous.
 HUFFMAN CODING / HUFFMAN TREES
 Huffman algorithm is a method of building an extended binary tree
with a minimum weighted path length from a set of given weights
 It is an encoding algorithm for lossless data compression
 Most frequently used symbols have shorter code to be represented in a
message
 The main aim is to minimize the length of the encoded message by
assigning a shorter bit string to the frequently occurring symbols in the
message
 It follows a bottom up approach for coding

19
 HUFFMAN CODING / HUFFMAN TREES
 Consider an example of encoding A to H as:
A 000 C 010 E 100 G 110
B 001 D 011 F 101 H 111
With this code, the message:
“BACADAEAFABBAAAGAH”
is encoded as the string of 54 bits:

“0010000100000110001000001010000010010000000001100001
11”
 But if we can assign shorter code for the frequent symbols as:
A0 C 1010 E 1100 G
1110
B 100 D 1011 F 1101 H 1111
The same message can be encoded as the string of only 42 bits

100010100101101100011010100100000111001111
20
 HUFFMAN CODING / HUFFMAN TREES
 Note that the codes have been designed in such a way that no complete code
for any symbol is the beginning (or prefix) of the code for another symbol.
 Such a code is called a prefix code.
 In the example above, A is encoded by 0 and B is encoded by 100, so no
other symbol can have a code that begins with 0 or with 100
 Huffman Coding method is one of the best ways to create such variable
length prefix codes for the symbols in any message

21
ALGORITHM FOR CREATING HUFFMAN TREES
1. Form a frequency list of all the symbols in descending or ascending order
2. Locate two symbols from the list with least frequencies (weight)
3. Create a parent node as for these two symbols for which the weight is the
sum of weights of its two child nodes
4. Remove the two child from the list and add the newly created parent node
into the list in sorted order of weight
5. Repeat from step 2 until there is only one node left in the tree

22
 CODE FROM A HUFFMAN TREE
 For evaluating the code for each symbol after the completion of
Huffman Tree:
1. Initialize a code string for the symbol as NULL
2. Starting from the node climb up to the root node
3. If the left branch is climbed, append ‘0’ as the starting character
of the code string
4. If the right branch is climbed, append ‘1’ as the starting character
of the code string

23
HUFFMAN CODE (EXAMPLE)

24
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

25
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

26
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

27
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

28
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

29
HUFFMAN CODE (EXAMPLE – STEP BY STEP)

30
M-WAY SEARCH TREE (MULTI WAY TREE)
 A Binary Tree is the one in which there is exactly one (i.e 2-1)
key in a node and two children.
 Similarly an m-way search tree is a tree in which
1. The nodes hold between 1 to m-1 distinct keys
2. The keys in each node are sorted
3. A node with k values has k+1 subtrees, where the subtrees may
be empty.
4. Each node can have 0 to m subtrees
5. Hence m is the maximum degree possible for the tree
6. Values less than the leftmost key value are inserted in leftmost
child whereas values greater than the rightmost key value are
inserted in rightmost child
7. Each subtree of m-way tree is again an m-way tree
 An m-way tree is not the perfectly balance tree hence it
may not be always efficient to perform operations on such
31
tree
M-WAY SEARCH TREE (MULTI WAY TREE)

3-way Search Tree

32

A multi way Tree of order 5

M-WAY SEARCH TREE (MULTI WAY TREE)

4-way Search Tree

33
B-TREES

A B-tree of order; m=5.

Min entry : Ceiling|5/2| - 1 = 2 entries.
Max entry: 5 – 1 = 4 entries.
Min subtrees : Ceiling|5/2|=3
Max subtrees: 5 34
B-TREE
 A B-tree of order m is a multiway search tree in which:
1. The root has at least two subtrees unless it is the only node
in the tree.
2. Each nonroot and each nonleaf node have at most m
subtrees and at least m/2 subtrees. M is the order of the tree
3. The number of keys in each nonroot and each nonleaf node
is one less than the number of its nonempty children.
4. A leaf node has at least (m-1)/2 and at most m-1 entries
5. All leaves are on the same level.
 These restrictions make B-trees always at least half full,
have few levels, and remain perfectly balanced.

35
B-TREE

A 3-way B-Tree

A 5-way B-Tree

Note: Compare the rules of B-Tree mentioned in earlier slide and determine
whether the above mentioned trees are B-Tree or not.
36
B-TREE (INSERTION)
 We have to take an account of not violating the rules of B-tree
while inserting data
 Insertions are generally done at leaf node
 Algorithm is as follows:
1. Start
2. Search tree to find the node where the has data to be inserted
3. If node is not full, insert the data into the node in a sorted
order
4. If node is full, split the node into two,
i. Find the median value from the node data and the data to be inserted
ii. Push the median upwards into the parent node
iii. If the parent node also is full, split the parent node as well using the
same procedure
iv. Repeat from step i. until either space is found for the data to be
37
inserted or a new node is created
B-TREE (INSERTION)

Fig: An order 3 B-tree insertion example for

sequence of data: 1, 2, 3, 4, 5, 6, 7

38
B-TREE (INSERTION)
 Consider another example for B-Tree of order 5
CNGAHEKQMFWLTZDPRXYS
 Order 5 means that a node can have a maximum of 5 children and 4 keys
 All nodes other than the root must have a minimum of 2 keys
 Step 1:
 The first 4 letters get inserted into the same node

 Step 2:
 When we try to insert the H, we find no room in this node, so we split it
into 2 nodes, moving the median item G up into a new root node

39
B-TREE (INSERTION)
 Step 3:
 Inserting E, K, and Q proceeds without requiring any splits

 Step 4:
 Inserting M requires a split. Note that M happens to be the median key and so is
moved up into the parent node.

40
B-TREE (INSERTION)
 Step 5:
 The letters F, W, L, and T are then added without needing any split

 Step 6:
 When Z is added, the rightmost leaf must be split. The median item T is moved up
into the parent node

41
B-TREE (INSERTION)
 Step 7:
 The insertion of D causes the leftmost leaf to be split. D happens to be the median
key and so is the one moved up into the parent node. The letters P, R, X, and Y are
then added without any need of splitting

 Step 8:
 Finally, when S is added, the node with N, P, Q, and R splits, sending the median Q
up to the parent. However, the parent node is full, so it splits, sending the median M
up to form a new root node
42
B-TREE (INSERTION)
 Final B-Tree will look like

43
 B-Tree Insertion

m=5
• B-tree grows from the bottom up.
• When the node is full, this condition is
called as overflow.
• Overflow requires that the node be split
into two nodes and median entry is
pushed up, the tree grows one level.

Figure 10-5
B-Tree Insertion
B-TREE (INSERTION - QUESTIONS)
 Insert the following data for constructing a B-Tree of order 5:
 10, 20, 50, 60, 40, 80, 100, 70, 130, 90, 30, 120, 140, 25, 35, 160, 180
 Create a B-Tree of order 5 from following data:
 1, 7, 6, 2, 11, 4, 8, 13, 10, 5, 19, 9, 18, 24, 3, 12, 14, 20, 21, 16
 Construct a 3-way B-Tree from the data:
 11, 12, 13, 14, 15, 16
 Create a 3 order B-Tree from the given sequence of data:
 8, 14, 2, 15, 3, 1, 12, 6, 5

47
RED BLACK TREES
 A red-black tree is a binary search tree with one extra bit of
storage per node: its color, which can be either RED or BLACK.
 By constraining the node colors on any simple path from the root
to a leaf, red-black trees ensure that no such path is more than
twice as long as any other, so that the tree is approximately
balanced.

48
RED BLACK TREES
 Each node of the tree now contains the attributes color, key, left,
right, and p.
 If a child or the parent of a node does not exist, the corresponding
pointer attribute of the node contains the value NIL.
 We shall regard these NILs as being pointers to leaves (external
nodes) of the binary search tree and the normal, key-bearing
nodes as being internal nodes of the tree.

49
RED BLACK TREES
 A red-black tree is a binary tree that satisfies the following red-black
properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain
the same number of black nodes.

50