Subjects | Gate Vidyalay

AVL Tree Insertion | Insertion in AVL Tree

Data Structures

AVL Tree-

Before you go through this article, make sure that you have gone through the previous article on AVL Trees.

We have discussed-

AVL trees are self-balancing binary search trees.
In AVL trees, balancing factor of each node is either 0 or 1 or -1.

In this article, we will discuss insertion in AVL tree.

Insertion in AVL Tree-

Insertion Operation is performed to insert an element in the AVL Tree.

To insert an element in the AVL tree, follow the following steps-

Insert the element in the AVL tree in the same way the insertion is performed in BST.
After insertion, check the balance factor of each node of the resulting tree.

Now, following two cases are possible-

Case-01:

After the insertion, the balance factor of each node is either 0 or 1 or -1.
In this case, the tree is considered to be balanced.
Conclude the operation.
Insert the next element if any.

Case-02:

After the insertion, the balance factor of at least one node is not 0 or 1 or -1.
In this case, the tree is considered to be imbalanced.
Perform the suitable rotation to balance the tree.
After the tree is balanced, insert the next element if any.

Also Read- AVL Tree Properties

Rules To Remember-

Rule-01:

After inserting an element in the existing AVL tree,

Balance factor of only those nodes will be affected that lies on the path from the newly inserted node to the root node.

Rule-02:

To check whether the AVL tree is still balanced or not after the insertion,

There is no need to check the balance factor of every node.
Check the balance factor of only those nodes that lies on the path from the newly inserted node to the root node.

Rule-03:

After inserting an element in the AVL tree,

If tree becomes imbalanced, then there exists one particular node in the tree by balancing which the entire tree becomes balanced automatically.
To re balance the tree, balance that particular node.

To find that particular node,

Traverse the path from the newly inserted node to the root node.
Check the balance factor of each node that is encountered while traversing the path.
The first encountered imbalanced node will be the node that needs to be balanced.

To balance that node,

Count three nodes in the direction of leaf node.
Then, use the concept of AVL tree rotations to re balance the tree.

PRACTICE PROBLEM BASED ON AVL TREE INSERTION-

Problem-

Construct AVL Tree for the following sequence of numbers-

50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48

Solution-

Step-01: Insert 50

Step-02: Insert 20

As 20 < 50, so insert 20 in 50’s left sub tree.

Step-03: Insert 60

As 60 > 50, so insert 60 in 50’s right sub tree.

Step-04: Insert 10

As 10 < 50, so insert 10 in 50’s left sub tree.
As 10 < 20, so insert 10 in 20’s left sub tree.

Step-05: Insert 8

As 8 < 50, so insert 8 in 50’s left sub tree.
As 8 < 20, so insert 8 in 20’s left sub tree.
As 8 < 10, so insert 8 in 10’s left sub tree.

To balance the tree,

Find the first imbalanced node on the path from the newly inserted node (node 8) to the root node.
The first imbalanced node is node 20.
Now, count three nodes from node 20 in the direction of leaf node.
Then, use AVL tree rotation to balance the tree.

Following this, we have-

Step-06: Insert 15

As 15 < 50, so insert 15 in 50’s left sub tree.
As 15 > 10, so insert 15 in 10’s right sub tree.
As 15 < 20, so insert 15 in 20’s left sub tree.

To balance the tree,

Find the first imbalanced node on the path from the newly inserted node (node 15) to the root node.
The first imbalanced node is node 50.
Now, count three nodes from node 50 in the direction of leaf node.
Then, use AVL tree rotation to balance the tree.

Following this, we have-

Step-07: Insert 32

As 32 > 20, so insert 32 in 20’s right sub tree.
As 32 < 50, so insert 32 in 50’s left sub tree.

Step-08: Insert 46

As 46 > 20, so insert 46 in 20’s right sub tree.
As 46 < 50, so insert 46 in 50’s left sub tree.
As 46 > 32, so insert 46 in 32’s right sub tree.

Step-09: Insert 11

As 11 < 20, so insert 11 in 20’s left sub tree.
As 11 > 10, so insert 11 in 10’s right sub tree.
As 11 < 15, so insert 11 in 15’s left sub tree.

Step-10: Insert 48

As 48 > 20, so insert 48 in 20’s right sub tree.
As 48 < 50, so insert 48 in 50’s left sub tree.
As 48 > 32, so insert 48 in 32’s right sub tree.
As 48 > 46, so insert 48 in 46’s right sub tree.

To balance the tree,

Find the first imbalanced node on the path from the newly inserted node (node 48) to the root node.
The first imbalanced node is node 32.
Now, count three nodes from node 32 in the direction of leaf node.
Then, use AVL tree rotation to balance the tree.

Following this, we have-

This is the final balanced AVL tree after inserting all the given elements.

To gain better understanding of AVL Tree Insertion,

Watch this Video Lecture

Next Article- Heap Data Structure

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Parse Tree | Derivations | Automata

Theory of Automata & Computation

Parse Tree-

The process of deriving a string is called as derivation.
The geometrical representation of a derivation is called as a parse tree or derivation tree.

1. Leftmost Derivation-

The process of deriving a string by expanding the leftmost non-terminal at each step is called as leftmost derivation.
The geometrical representation of leftmost derivation is called as a leftmost derivation tree.

Example-

Consider the following grammar-

S → aB / bA

S → aS / bAA / a

B → bS / aBB / b

(Unambiguous Grammar)

Let us consider a string w = aaabbabbba

Now, let us derive the string w using leftmost derivation.

Leftmost Derivation-

S → aB

→ aaBB (Using B → aBB)

→ aaaBBB (Using B → aBB)

→ aaabBB (Using B → b)

→ aaabbB (Using B → b)

→ aaabbaBB (Using B → aBB)

→ aaabbabB (Using B → b)

→ aaabbabbS (Using B → bS)

→ aaabbabbbA (Using S → bA)

→ aaabbabbba (Using A → a)

2. Rightmost Derivation-

The process of deriving a string by expanding the rightmost non-terminal at each step is called as rightmost derivation.
The geometrical representation of rightmost derivation is called as a rightmost derivation tree.

Example-

Consider the following grammar-

S → aB / bA

S → aS / bAA / a

B → bS / aBB / b

(Unambiguous Grammar)

Let us consider a string w = aaabbabbba

Now, let us derive the string w using rightmost derivation.

Rightmost Derivation-

S → aB

→ aaBB (Using B → aBB)

→ aaBaBB (Using B → aBB)

→ aaBaBbS (Using B → bS)

→ aaBaBbbA (Using S → bA)

→ aaBaBbba (Using A → a)

→ aaBabbba (Using B → b)

→ aaaBBabbba (Using B → aBB)

→ aaaBbabbba (Using B → b)

→ aaabbabbba (Using B → b)

NOTES

For unambiguous grammars, Leftmost derivation and Rightmost derivation represents the same parse tree.
For ambiguous grammars, Leftmost derivation and Rightmost derivation represents different parse trees.

Here,

The given grammar was unambiguous.
That is why, leftmost derivation and rightmost derivation represents the same parse tree.

Leftmost Derivation Tree = Rightmost Derivation Tree

Also Read- Ambiguous Grammar

Properties Of Parse Tree-

Root node of a parse tree is the start symbol of the grammar.
Each leaf node of a parse tree represents a terminal symbol.
Each interior node of a parse tree represents a non-terminal symbol.
Parse tree is independent of the order in which the productions are used during derivations.

Yield Of Parse Tree-

Concatenating the leaves of a parse tree from the left produces a string of terminals.
This string of terminals is called as yield of a parse tree.

PRACTICE PROBLEMS BASED ON DERIVATIONS AND PARSE TREE-

Problem-01:

Consider the grammar-

S → bB / aA

A → b / bS / aAA

B → a / aS / bBB

For the string w = bbaababa, find-

Leftmost derivation
Rightmost derivation
Parse Tree

Solution-

1. Leftmost Derivation-

S → bB

→ bbBB (Using B → bBB)

→ bbaB (Using B → a)

→ bbaaS (Using B → aS)

→ bbaabB (Using S → bB)

→ bbaabaS (Using B → aS)

→ bbaababB (Using S → bB)

→ bbaababa (Using B → a)

2. Rightmost Derivation-

S → bB

→ bbBB (Using B → bBB)

→ bbBaS (Using B → aS)

→ bbBabB (Using S → bB)

→ bbBabaS (Using B → aS)

→ bbBababB (Using S → bB)

→ bbBababa (Using B → a)

→ bbaababa (Using B → a)

3. Parse Tree-

Whether we consider the leftmost derivation or rightmost derivation, we get the above parse tree.
The reason is given grammar is unambiguous.

Problem-02:

Consider the grammar-

S → A1B

A → 0A / ∈

B → 0B / 1B / ∈

For the string w = 00101, find-

Leftmost derivation
Rightmost derivation
Parse Tree

Solution-

1. Leftmost Derivation-

S → A1B

→ 0A1B (Using A → 0A)

→ 00A1B (Using A → 0A)

→ 001B (Using A → ∈)

→ 0010B (Using B → 0B)

→ 00101B (Using B → 1B)

→ 00101 (Using B → ∈)

2. Rightmost Derivation-

S → A1B

→ A10B (Using B → 0B)

→ A101B (Using B → 1B)

→ A101 (Using B → ∈)

→ 0A101 (Using A → 0A)

→ 00A101 (Using A → 0A)

→ 00101 (Using A → ∈)

3. Parse Tree-

Whether we consider the leftmost derivation or rightmost derivation, we get the above parse tree.
The reason is given grammar is unambiguous.

To gain better understanding about Derivations and Parse Tree,

Watch this Video Lecture

Next Article- Elimination of Left Recursion

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Set Theory Operators | Relational Algebra | DBMS

Database Management System

Relational Algebra Operators-

Before you go through this article, make sure that you have gone through the previous article on Introduction to Relational Algebra.

The operators in relational algebra are classified as-

In this article, we will discuss about Set Theory Operators.

Set Theory Operators-

Following operators are called as set theory operators-

Union Operator (∪)
Intersection Operator (∩)
Difference Operator (-)

Condition For Using Set Theory Operators

To use set theory operators on two relations,

The two relations must be union compatible.

Union compatible property means-

Both the relations must have same number of attributes.
The attribute domains (types of values accepted by attributes) of both the relations must be compatible.

Also read- Selection Operator and Projection Operator

1. Union Operator (∪)-

Let R and S be two relations.

Then-

R ∪ S is the set of all tuples belonging to either R or S or both.
In R ∪ S, duplicates are automatically removed.
Union operation is both commutative and associative.

Example-

Consider the following two relations R and S-

ID	Name	Subject
100	Ankit	English
200	Pooja	Maths
300	Komal	Science

Relation R

ID	Name	Subject
100	Ankit	English
400	Kajol	French

Relation S

Then, R ∪ S is-

ID	Name	Subject
100	Ankit	English
200	Pooja	Maths
300	Komal	Science
400	Kajol	French

Relation R ∪ S

2. Intersection Operator (∩)-

Let R and S be two relations.

Then-

R ∩ S is the set of all tuples belonging to both R and S.
In R ∩ S, duplicates are automatically removed.
Intersection operation is both commutative and associative.

Example-

Consider the following two relations R and S-

ID	Name	Subject
100	Ankit	English
200	Pooja	Maths
300	Komal	Science

Relation R

ID	Name	Subject
100	Ankit	English
400	Kajol	French

Relation S

Then, R ∩ S is-

ID	Name	Subject
100	Ankit	English

Relation R ∩ S

3. Difference Operator (-)-

Let R and S be two relations.

Then-

R – S is the set of all tuples belonging to R and not to S.
In R – S, duplicates are automatically removed.
Difference operation is associative but not commutative.

Example-

Consider the following two relations R and S-

ID	Name	Subject
100	Ankit	English
200	Pooja	Maths
300	Komal	Science

Relation R

ID	Name	Subject
100	Ankit	English
400	Kajol	French

Relation S

Then, R – S is-

ID	Name	Subject
200	Pooja	Maths
300	Komal	Science

Relation R – S

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Projection Operator | Relational Algebra | DBMS

Database Management System

Relational Algebra Operators-

Before you go through this article, make sure that you have gone through the previous article on Introduction to Relational Algebra.

The operators in relational algebra are classified as-

In this article, we will discuss about Projection Operator.

Projection Operator-

Projection Operator (π) is a unary operator in relational algebra that performs a projection operation.
It displays the columns of a relation or table based on the specified attributes.

Syntax-

π_{<attribute list>}(R)

Example-

Consider the following Student relation-

ID	Name	Subject	Age
100	Ashish	Maths	19
200	Rahul	Science	20
300	Naina	Physics	20
400	Sameer	Chemistry	21

Student

Then, we have-

Result for Query π_{Name, Age}(Student)-

Name	Age
Ashish	19
Rahul	20
Naina	20
Sameer	21

Result for Query π_{ID , Name}(Student)-

ID	Name
100	Ashish
200	Rahul
300	Naina
400	Sameer

Important Points-

Point-01:

The degree of output relation (number of columns present) is equal to the number of attributes mentioned in the attribute list.

Point-02:

Projection operator automatically removes all the duplicates while projecting the output relation.
So, cardinality of the original relation and output relation may or may not be same.
If there are no duplicates in the original relation, then the cardinality will remain same otherwise it will surely reduce.

Point-03:

If attribute list is a super key on relation R, then we will always get the same number of tuples in the output relation.
This is because then there will be no duplicates to filter.

Point-04:

Projection operator does not obey commutative property i.e.

π _<list2> (π _<list1>(R)) ≠ π _<list1> (π _<list2>(R))

Point-05:

Following expressions are equivalent because both finally projects columns of list-1

π _<list1> (π _<list2>(R)) = π _<list1>(R)

Point-06:

Selection Operator performs horizontal partitioning of the relation.
Projection operator performs vertical partitioning of the relation.

Point-07:

There is only one difference between projection operator of relational algebra and SELECT operation of SQL.
Projection operator does not allow duplicates while SELECT operation allows duplicates.
To avoid duplicates in SQL, we use “distinct” keyword and write SELECT distinct.
Thus, projection operator of relational algebra is equivalent to SELECT operation of SQL.

Next Article- Set Theory Operators in Relational Algebra

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Selection Operator | Relational Algebra | DBMS

Database Management System

Relational Algebra Operators-

Before you go through this article, make sure that you have gone through the previous article on Introduction to Relational Algebra.

The operators in relational algebra are classified as-

In this article, we will discuss about Selection Operator.

Selection Operator-

Selection Operator (σ) is a unary operator in relational algebra that performs a selection operation.
It selects those rows or tuples from the relation that satisfies the selection condition.

Syntax-

σ_{<selection_condition>}(R)

Examples-

Select tuples from a relation “Books” where subject is “database”

σ_{subject = “database”} (Books)

Select tuples from a relation “Books” where subject is “database” and price is “450”

σ_{subject = “database” ∧ price = “450”} (Books)

Select tuples from a relation “Books” where subject is “database” and price is “450” or have a publication year after 2010

σ_{subject = “database” ∧ price = “450” ∨ year >”2010″} (Books)

Important Points-

Point-01:

We may use logical operators like ∧ , ∨ , ! and relational operators like = , ≠ , > , < , <= , >= with the selection condition.

Point-02:

Selection operator only selects the required tuples according to the selection condition.
It does not display the selected tuples.
To display the selected tuples, projection operator is used.

Point-03:

Selection operator always selects the entire tuple. It can not select a section or part of a tuple.

Point-04:

Selection operator is commutative in nature i.e.

σ _{A ∧ B} (R) = σ _{B ∧ A} (R)

OR

σ _B(σ _A(R)) = σ _A(σ _B(R))

Point-05:

Degree of the relation from a selection operation is same as degree of the input relation.

Point-06:

The number of rows returned by a selection operation is obviously less than or equal to the number of rows in the original table.

Thus,

Minimum Cardinality = 0
Maximum Cardinality = |R|

Next Article- Projection Operation in Relational Algebra

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.

Category: Subjects

AVL Tree-

Insertion in AVL Tree-

Case-01:

Case-02:

Rules To Remember-

Rule-01:

Rule-02:

Rule-03:

PRACTICE PROBLEM BASED ON AVL TREE INSERTION-

Problem-

Solution-

Step-01: Insert 50

Step-02: Insert 20

Step-03: Insert 60

Step-04: Insert 10

Step-05: Insert 8

Step-06: Insert 15

Step-07: Insert 32

Step-08: Insert 46

Step-09: Insert 11

Step-10: Insert 48

Parse Tree-

1. Leftmost Derivation-

Example-

Leftmost Derivation-

2. Rightmost Derivation-

Example-

Rightmost Derivation-

NOTES

Properties Of Parse Tree-

Yield Of Parse Tree-

PRACTICE PROBLEMS BASED ON DERIVATIONS AND PARSE TREE-

Problem-01:

Solution-

1. Leftmost Derivation-

2. Rightmost Derivation-

3. Parse Tree-

Problem-02:

Solution-

1. Leftmost Derivation-

2. Rightmost Derivation-

3. Parse Tree-

Relational Algebra Operators-

Set Theory Operators-

Condition For Using Set Theory Operators

1. Union Operator (∪)-

Example-

Relation R

Relation S

Relation R ∪ S

2. Intersection Operator (∩)-

Example-

Relation R

Relation S

Relation R ∩ S

3. Difference Operator (-)-

Example-

Relation R

Relation S

Relation R – S

Relational Algebra Operators-

Projection Operator-

Syntax-

Example-

Student

Result for Query πName, Age(Student)-

Result for Query πID , Name(Student)-

Important Points-

Point-01:

Point-02:

Point-03:

Point-04:

Point-05:

Point-06:

Point-07:

Relational Algebra Operators-

Selection Operator-

Syntax-

Examples-

Result for Query π_{Name, Age}(Student)-

Result for Query π_{ID , Name}(Student)-