Gokaraju Rangaraju Institute of Engineering and Technology

Department of Computer Science and Engineering

Year/Semester : II / I Academic year: 2015-16

SUB:ADS THROUGH C++

Tutorial Sheet: UNIT V-1

BALANCED SEARCH TREES
Short answer questions
[Link] red black trees
[Link] of avl trees with red black tree
[Link] does a red black tree ensures balance
[Link] that height of redblack trees of n nodes is 2log(n+)
[Link] are the properties of red black trees
[Link] is splay tree
[Link] are the roatations of the splay tree
[Link] dfs algorithm
[Link] bfs algorithm
Descriptive questions/Programs/Experiments
[Link] B Trees And its operations?
[Link] Red-Black tree? Define operations of Red-Black trees?
[Link] the implementation of insert operation with an example?
[Link] is Splay Tree? Describe its operations in detail?

Tutor Faculty HOD

1
 Gokaraju Rangaraju Institute of Engineering and Technology
Department of Computer Science and Engineering

Year/Semester : II / I Academic year: 2015-16

Tutorial Sheet:V-1 Question & Answers

SHORT ANSWER QUESTIONS
[Link] red black trees
Ans:Most of the BST operations (e.g., search, max, min, insert, delete..etc) take O(h) time where
h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary
tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion,
then we can guarantee an upper bound of O(Logn) for all these operations. The height of a Red
Black tree is always O(Logn) where n is the number of nodes in the tree
[Link] of avl trees with red black tree
Ans:The AVL trees are more balanced compared to Red Black Trees, but they may cause more
rotations during insertion and deletion. So if your application involves many frequent insertions
and deletions, then Red Black trees should be preferred. And if the insertions and deletions are
less frequent and search is more frequent operation, then AVL tree should be preferred over Red
Black Tree.
[Link] does a red black tree ensures balance
Ans:A simple example to understand balancing is, a chain of 3 nodes is not possible in red black
tree. We can try any combination of colors and see all of them violate Red-Black tree property.
A chain of 3 nodes is nodes is not possible in Red-Black Trees.
Following are NOT Red-Black Trees
30 30 30
/ \ / \ / \
20 NIL 20 NIL 20 NIL
/\ / \ / \
2
10 NIL 10 NIL 10 NIL
Violates Violates Violates
Property 4. Property 4 Property 3
Following are different possible Red-Black Trees with above 3 keys
20 20
/ \ / \
10 30 10 30
/ \ / \ / \ / \
NIL NIL NILNIL NIL NIL NIL NIL
[Link] that height of redblack trees of n nodes is 2log(n+)
Ans:This can be proved using following facts:
1) For a general Binary Tree, let k be the minimum number of nodes on all root to NULL paths,
then n >= 2k – 1 (Ex. If k is 3, then n is atleast 7). This expression can also be written as k<=
2Log2(n+1)
2) From property 4 of Red-Black trees and above claim, we can say in a Red-Black Tree with n
nodes, there is a root to leaf path with at-most Log2(n+1) black nodes.
3) From property 3 of Red-Black trees, we can claim that the number black nodes in a Red-Black
tree is at least ⌊ n/2 ⌋ where n is total number of nodes.
From above 2 points, we can conclude the fact that Red Black Tree with n nodes has height <=
2Log2(n+1)
In this post, we introduced Red-Black trees and discussed how balance is ensured. The hard part
is to maintain balance when keys are added and removed. We will soon be discussing insertion
and deletion operations in coming posts on Red-Black tree.
[Link] are the properties of red black trees
Ans: the properties of red black trees are
1. A node is either red or black.
2. The root is black. (This rule is sometimes omitted. Since the root can always be changed
from red to black, but not necessarily vice versa, this rule has little effect on analysis).
3. All leaves (NIL) are black. All leaves are of the same color as the root.
4. The parent of a red node is black.

3
 5. Every path from a given node to any of its descendant NIL nodes contains the same
number of black nodes. (The uniform number of black nodes in the paths from root to
leaves is called the black-height of the red–black tree.)
[Link] is splay tree
Ans:A splay tree is a self-adjusting binary search tree with the additional property that recently
accessed elements are quick to access again. It performs basic operations such as insertion, look-
up and removal in O(log n) amortized time. For many sequences of non-random operations,
splay trees perform better than other search trees, even when the specific pattern of the sequence
is unknown
[Link] are the roatations of the splay tree
Ans:Zig Rotation (Right Rotation)
Zag Rotation (Left Rotation)
Zig-Zag (Zig followed by Zag)
Zag-Zig (Zag followed by Zig)
Zig-Zig
Zag-Zag
[Link] dfs algorithm
Ans:The algorithm is as follows:
DFS(Graph G,vertex v):
For all edges e incident to the start vertex v do:
1) If e is unexplored
a) Let e connect v to w.
b) If w is unexplored, then
i) Label e as a discovery edge
ii) Recursively call DFS(G,w)
else
iii) Label e as a back edge
[Link] bfs algorithm
Ans:BFS(G,s):
1) Let L0 be empty
2) Insert s into L0.

4
3) Let i = 0
4) While Li is not empty do the following:
A) Create an empty container Li+1.
B) For each vertex v in Li do
i) For all edges e incident to v
a) if e is unexplored, mark endpoint w.
b) if w is unexplored
Mark it.
Insert w into Li+1.
Label e as a discovery edge.
else
Label e as a cross edge.
C) i = i+1

LONG ANSWERS

1. Define B Trees And its operations?

Ans:

 Multi-way trees are tree data structures with more than two branches at a node. The data
structures of m-way search trees, B trees and Tries belong to this category of tree
structures.
 AVL search trees are height balanced versions of binary search trees, provide efficient
retrievals and storage operations. The complexity of insert, delete and search operations
on AVL search trees id O(log n).
 Applications such as File indexing where the entries in an index may be very large,
maintaining the index as m-way search trees provides a better option than AVL search
trees which are but only balanced binary search trees.
 While binary search trees are two-way search trees, m-way search trees are extended
binary search trees and hence provide efficient retrievals.
 B trees are height balanced versions of m-way search trees and they do not recommend
representation of keys with varying sizes.
 Tries are tree based data structures that support keys with varying sizes.
Definition: A B tree of order m is an m-way search tree and hence may be empty. If non empty,
then the following properties are satisfied on its extended tree representation:
i. The root node must have at least two child nodes and at most m child nodes.
ii. All internal nodes other than the root node must have at least |m/2 | non empty child
nodes and at most m non empty child nodes.

5
 [Link] number of keys in each internal node is one less than its number of child nodes and
these keys partition the keys of the tree into sub trees.
iv. All external nodes are at the same level.
Example:
F K O B tree of order 4

Level 1

C D G M N P Q W

S T X Y Z
Level 3

Insertion
For example construct a B-tree of order 5 using following numbers.
3, 14, 7, 1, 8, 5, 11, 17, 13, 6, 23, 12, 20, 26, 4, 16, 18, 24, 25, 19
The order 5 means at the most 4 keys are allowed. The internal node should have at least 3 non
empty children and each leaf node must contain at least 2 keys.
Step 1: Insert 3, 14, 7, 1

1 3 7 14

Step 2: Insert 8, Since the node is full split the node at medium 1, 3, 7, 8, 14

1 3 8 14

6
Step 3: Insert 5, 11, 17 which can be easily inserted in a B-tree.

1 3 5 8 11 14 17

Step 4: Now insert 13. But if we insert 13 then the leaf node will have 5 keys which is not
allowed. Hence 8, 11, 13, 14, 17 is split and medium node 13 is moved up.

7 13

1 3 5 8 11 14 17

Step 5: Now insert 6, 23, 12, 20 without any split.

7 13

1 3 5 6 8 11 12 14 17 20 23

7
 Step 6: The 26 is inserted to the right most leaf node. Hence 14, 17, 20, 23, 26 the node is split
and 20 will be moved up.
7 13 20

1 3 5 6 8 11 12 14 17 23 26

Step 7: Insertion of node 4 causes left most node to split. The 1, 3, 4, 5, 6 causes key 4 to move
up. Then insert 16, 18, 24, 25.

4 7 13 20

1 3 5 6 8 11 12 14 16 17 18 23 24 25 26

Step 8: Finally insert 19. Then 4, 7, 13, 19, 20 needs to be split. The median 13 will be moved up
to from a root node.
The tree then will be -

13

4 7 17 20

1 3 Thus the5 B tree

6 is constructed.
8 11 12 14 16 18 19 23 24 25 26
8
 Deletion
Consider a B-tree 13

4 7 17 20

1 3 5 6 8 11 12 14 16 18 19 23 24 25 26

Delete 8, then it is very simple.

13

4 7 17 20

1 3 5 6 11 12 14 16 18 19 23 24 25 26

Now we will delete 20, the 20 is not in a leaf node so we will find its successor which is 23,
Hence 23 will be moved up to replace 20.

13

4 7 17 23
9
 Next we will delete 18. Deletion of 18 from the corresponding node causes the node with only
one key, which is not desired (as per rule 4) in B-tree of order 5. The sibling node to immediate
right has an extra key. In such a case we can borrow a key from parent and move spare key of
sibling up.
13

4 7 17 24

1 3 5 6 11 12 14 16 19 23 25 26

Now delete 5. But deletion of 5 is not easy. The first thing is 5 is from leaf node. Secondly this
leaf node has no extra keys nor siblings to immediate left or right. In such a situation we can
combine this node with one of the siblings. That means remove 5 and combine 6 with the node 1,
3. To make the tree balanced we have to move parent’s key down. Hence we will move 4 down
as 4 is between 1, 3, and 6. The tree will be-

10
 13

7 17 24

1 3 4 6 11 12 14 16 19 23 25 26

But again internal node of 7 contains only one key which not allowed in B-tree. We then will try
to borrow a key from sibling. But sibling 17, 24 has no spare key. Hence we can do is that,
combine 7 with 13 and 17, 24. Hence the B-tree will be

7 13 17 24

1 3 4
Searching 6 11 12 14 16 19 23 25 26

The search operation on B-tree is similar to a search to a search on binary search tree. Instead of
choosing between a left and right child as in binary tree, B-tree makes an m-way choice.
Consider a B-tree as given below.

13

11

4 7
17 20
1 3

If we want to search 11 then

i. 11 < 13 ; Hence search left node
ii. 11 > 7 ; Hence right most node
iii. 11 > 8 ; move in second block
iv. node 11 is found
The running time of search operation depends upon the height of the tree. It is O(log n).

Height of B-tree

The maximum height of B-tree gives an upper bound on number of disk access. The maximum
number of keys in a B-tree of order 2m and depth h is

1 + 2m + 2m(m+1) + 2m(m+1)2 + . . .+ 2m(m+1)h-1

h= 1 + ∑ 2m(m+1)i-1

i=1

The maximum height of B-tree with n keys

log m+1 n = O(log n)

2m

2. Define Red-Black tree? Define operations of Red-Black trees?

Ans:

12
 Definition: Red-Black tree is a binary search tree in which every node is colored with either
red or black. It is a type of self-balancing binary search tree. It has a good efficient worst case
running time complexity. The Red-black tree satisfies all the properties of binary search tree
in addition to that it satisfies following additional properties-

1. The root and the external nodes are always black nodes.
2. [Red Condition] No two red nodes can occur consecutively on the path from the root
node to an external node.
3. [Black Condition] The number of black nodes on the path from the root node to an
external node most be the same for all external nodes.
Since the color of the node is same as the color of the edge from which the node emanates, the
Red and Black Conditions may be expressed in terms of the edges as well. The Red Condition
could be alternatively defined as no two red pointers or edges can occur consecutively on a path
from the root node to an external node. The black condition could be redefined as all paths from
the root node to external nodes must have the same number of black pointers. Besides the above
mentioned conditions, all pointers linking internal nodes with the external nodes must be black.

The number of black nodes or edges on the path from a node to an external node is called the
rank of the node. The rank of all external nodes is 0.

Representation:

While representing a red black tree color of every node and pointer colors are shown. The leaf
nodes are simply NULL nodes.

70

40
90
13

30
80 100
 50

NULL NULL
NULL NULL
NULL
NULL

The Red-Black tree shown in above given figure has black nodes that are shaded in black and un
shaded nodes are Red nodes. Similarly the leaves are black and all are NULL pointers only. The
pointers to black node are black pointers which are shown by thick lines remaining are red
pointers. But in practice, we explicitly mention the color of nodes. The above given Red-Black
tree follows all the properties of Red-Black tree-

1. It is a binary search tree.

2. The root node is black.
3. The children of red node are black.
4. No root to external node path has two consecutive red nodes (e.g. 70-90-80-88-NULL).
5. All the root to external node paths contain same number of black nodes (including root
and external node).
For e.g. : consider path 70-40-30-NULL and 70-90-80-88-NULL in both these paths 3 black
nodes are there. Similarly other paths are checked.

Insertion:

 Every new node which is to be inserted is marked red.

 Not every insertion causes imbalancing but if imbalancing occurs then that can be
removed depending upon the configuration of tree before new insertion made.
 To understand insertion operation, let us understand the configuration of tree by defining
following roles.

14
Let u is newly inserted node.

pu is the parent node of u.

gu is grand parent of u and parent node of pu

un is an uncle node of u i.e. it’s a right child of gu.

gu

pu un

The tree is said to be imbalanced if properties of Red-Black tree are violated.

 When insertion occurs, the new node is inserted in already balanced tree. If this insertion
causes any imbalancing then balancing of the tree is to be done at two levels:
-- atgrand parent level i.e. gu

-- at parent level i.e. pu

 The imbalacing is concerned with the color of grand parent’s child i.e. uncle node. If
uncle node is red then there are four cases.
1. LRr
2. LLr
3. RRr
4. RLr
1. LRr imbalance – The left child of gu is pu and u is right child of p u and un node(uncle node) is
red. gu

pu un
15

u
 RED RED

RED

2. LLr imbalance – The node puis a left child of gu and u is inserted as left child of p u. Node un is
red.

gu

pu un

3. RRr imbalance – The right child of node gu is node pu and u is inserted as right child of p u.
The un node is red.

gu

un 16 pu
4. RLr imbalance – The node pu is right child of gu and u is inserted as a left child of pu. The
uncle node un is red.

gu

un pu

To remove these imbalancing rotations are not required. Simply by changing the colors required
balancing can be obtained.

1. Removal of LRrimbalancing

Before color change note that if gu in given figures is root then there should not be any color
change of gu. (Because root is always black). But if g u happens to be red then the rebalancing can
be done as -

17
 gu

gu

pu un

pu un

1. Change color of pu from red to black.

2. Change color of un from red to black.
3. Change color of gu from black to red provided gu is not a root node.

2. Removal of LLrimbalancing

gu gu

pu un pu un

u u

1. Change color of pu from red to black.

2. Change color of un from red to black.

3. Change color of gu from black to red when gu is not a root node.

18
3. Removal of RRrimbalancing
gu

gu

un pu

un pu

1. Change color of pu from red to black.

2. Change color of un from red to black.

3. Change color of gu from black to red when gu is not a root node.

4. Removal of RLrimbalancing

gu
gu

un pu
un pu

u
u

1. Change color of pu from red to black.

2. Change color of un from red to black.

3. Change color of gu from black to red when gu is not a root node.

19
Now when other child of gu i.e. uncle node un is black then there arises four cases.

1. LRbimbalancing: The pu node is attached as a left child of g u and u is inserted as a right

child of pu. The node unis black.
gu

pn un

2. LLbimbalancing: The node pu is a left child of gu and u node is a left child of pu. The node unis
black.

gu

pu un

3. RRbimbalancing: The node pu is a right child of gu and node u is a right child of pu. The node
un is black.
gu

un 20 pu

u
4. RLbimbalancing : The node pu is a right child of node g u and node u is a right child of p u. The
node unis black. gu

un pu

As u node gets inserted rebalancing must be performed.

-LLb and RRb cases require single rotation followed by recoloring.

-LRband RLb cases require double rotation followed by recoloring.

Removing LLb and RRb imbalances

1. Apply single rotation of pu about gu.

2. Recolor pu to black and gu to red.

gu pu

21
pu un u pu
 balancing

Removal of LLbimbalancing

pu

gu

gu u
un pu

balancing
un
u

Removal of RRbimbalancing

Removing LRb and RLb imbalances

22
 1. Apply double rotation of u about pu followed by u about gu.
2. For LRb recolor u to black and recolor pu and gu to red.
3. For RLb recolor pu to black.

gu u

pn un pu gu

balancing
u un

Removal of LRbimbalancing

gu u

un pu gn pu

balancing
u un

Removal of RLbimbalancing

2. Define Red-Black tree? Give the implementation of insert operation with an

example?

23
 Ans:Example for insertion of elements in Red-Black tree

Insert key sequence is as given below.

40, 50, 70, 30, 42, 15, 20, 25, 27, 26, 60, 55

Construct Red-Black tree:

Initially insert node 40 with color red. Recolor this root node to black.

40 40

Insert 50

40

50

Insert 70

40 50
Recolor and rotate it

50
(RRbimbalancing)
40 70

70

Insert 30 50
50

40 70 40 70
24

30
30
 Recorecolor Pu,gu, and un

(LLrimbalacing)

Insert 42 Insert 15

50 50

40 70 40 70

30 42 30 42

15

Recolormarked nodes

(LLrimbalancing) 50

40 70

30 42

Insert15
20 50
50

40 70
40 70 25

20 42
30 42
 LRbimbalancing

hence rotate

20

Insert 25

Recolor these nodes

50

50
40 70

40 70

20 42
20 42

15 30
15 30
RLrimbalancing

25
25

Recolor these nodes

50
40

40 70
26 20 50

20 42
15 30
 Rotating about 40

Insert 27

40 40

20 50 20 50

15 30 15 27
42 70 RLb 42 70

25 25
30

27

Insert 26 Recolor marked nodes

27
 40 40

20 50 20 50

15 27 15 27
42 70 42 70

Recolor marked nodes

25 25
30 30

26 26

40

20 50

15 27
42 70

25
30

26

Insert 60

40

28
20 50
 40
Insert 55

20 50

15 27
42 70
Recolor(LLbimbalancing)

25
30 60

26
55

Delete 70
40

20 50
29

15 27
 70

Final Red-Black tree

3. What is Splay Tree? Describe its operations in detail?

Ans: SPLAY TREES

A splay tree is a self-balancing binary search tree with no explicit balance condition. The splay
tree has a property that recently accessed elements can be accessed quickly.

All normal operations that are performed on binary search tree are performed on splay tree. But
there is a special operation called splaying is performed on splay tree.

Splaying means arranging the elements of a tree in such a way that the most recently accessed
node will be placed as root of the tree. Various cases that arise are

1. Zig-zag step
2. Zig-zig step
3. Zig step

These are basically rotations applied for the node x. Zig means left and zag means right. Let ‘P’
be the parent node of ‘x’ and ‘g’ be the grand parent of x.

1. Zig-zag case (LR step)

g x

P D P g
30

A x A B C D
When x is a right child of node P and P is a left child of node g. Then the rearrangement is made
for most recently accessed node x.

The x becomes root, P becomes its left child and g becomes the right child. The Zig-zag step is
equivalent to rotation about x.

2. Zig-zig case (LL step)

A P

P D

B g
x C

C D
A B

The P node becomes right child of x and g becomes right child of P, where elements get
rearranged in zig-zig step.

3. Zigstep(L step)

P x

31

x C A P
When x is attached as a left child of P node then the rearrangement that is needed is of zig type.
In such a rearrangement P becomes right child of x node.

Splay Operations: Various operations supported by splay tree are

1. Splay
2. Find
3. Insert
4. Delete
The splay operation starts at splay node. The splay node is basically root of the binary search
tree.

During splay operation the splay node that is been selected is at the deepest level. To move this
node at root the sequence of splay steps are performed. When splay node reaches to root position
the sequence of splay step is empty. The splay steps involve various rotations such as zig-zag,
zig, zig-zig.

For example:Consider a tree as given below:

4 12

2 6 10 14

Now if we want to find node ‘3’. Then focus of splay operation consists of node being splayed
its parent and its grand parent.
1 3 5 7 9 11 13 15
The node involved in splay operation indicatezig-zag or LR rotation.

32
After performing this splay operation the tree becomes-

The marked nodes direct the zig or L rotation. Hence the splay tree becomes

4 12

2 6 10 14

1 3 5 7 9 11 13 15

4
2

The tree is
3

33
8
 3

2 8

1 4 12

6 10 14

5 7 9 11 13 15

Consider another example-

2
34

3
Now if splay node is 8 then the sequence of operations performed are –

This is called zig-zag or RR operation which is mirror operation of LL or zig-zig.

1
2 35

3
 Zag-zag 2

Zag-zag
3
g

p
5

7 7
4

1 6 6

8 8
Zag or R

3 operation 1

3
2 5

2 5
4
7
7
4

6
6

36