[go: up one dir, main page]
Scribd
Upload
80 views6 pages

Lab 7

This document is a lab note on AVL trees from a Data Structures and Algorithms course. It begins with an introduction to AVL trees, noting they are balanced binary search trees. It then covers key aspects of AVL trees like node structure, checking balance factors, and four types of rotations (left, right, left-right, right-left) used to rebalance the tree during insertions and deletions. The document provides code examples for functions like checking balance, rotation types, and rebalancing the tree. It concludes by assigning exercises for students to complete an AVL tree implementation.

Uploaded by

Nguyễn Quang Lợi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
80 views6 pages

Lab 7

This document is a lab note on AVL trees from a Data Structures and Algorithms course. It begins with an introduction to AVL trees, noting they are balanced binary search trees. It then covers key aspects of AVL trees like node structure, checking balance factors, and four types of rotations (left, right, left-right, right-left) used to rebalance the tree during insertions and deletions. The document provides code examples for functions like checking balance, rotation types, and rebalancing the tree. It concludes by assigning exercises for students to complete an AVL tree implementation.

Uploaded by

Nguyễn Quang Lợi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Ton Duc Thang University

Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

Lab 7
AVL Tree
Quang D. C.
dungcamquang@tdtu.edu.vn

November 15, 2021

Note
In the previous lab, we learned how to build up a BST. And in this tutorial, we
continue to extend Binary Search Tree to the Balanced Binary Search Tree, one of
them called AVL Tree.

Part I
Classwork
In this part, lecturer will:

• Summarize the theory related to this lab.

• Instruct the lesson in this lab to the students.

• Explain the sample implementations.

Responsibility of the students in this part:

• Students practice sample exercises with solutions.

• During these part, students may ask any question that they don’t understand or
make mistakes. Lecturers can guide students, or do general guidance for the whole
class if the errors are common.

1. What is AVL Tree?


AVL is the abbreviation of the Russian authors Adelson-Velskii and Landis (1962)
who defined the balanced tree.
An AVL tree is the same as a binary search tree, except that for every node, the
height of the left and right subtrees can differ only by 1 (and an empty tree has a height
of -1)1 . This difference is called Balance Factor. When the Balance Factor > 1, the tree
will be rebalanced.
1 https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1176/lectures/20-BinarySearchTrees/20-

BinarySearchTrees.pptx

dungcamquang@tdtu.edu.vn 1
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

Figure 1: AVL tree

2. Node of a AVL tree


In this lab, we add one more attribute which is called height to the Node class (same
with BST). This attribute will help us access the height of the node faster.
1 public class Node{
2 Integer key;
3 Node left , right ;
4 int height ;
5
6 public Node( Integer key){
7 this.key = key;
8 this. height = 0;
9 this.left = this. right = null;
10 }
11 }
In AVL class:
1 public int height (Node node){
2 if (node == null)
3 return -1;
4 return node. height ;
5 }

3. Check balance factor


A Balance Factor of a AVL tree is defined by the height difference of the left subtree
and the right subtree.
1 private int checkBalance (Node x) {
2 return height (x.left) - height (x. right );
3 }

4. Rotation
The insert or delete operation may make the AVL tree come to imbalance. A simple
modification of the tree, called rotation, can restore the AVL property. We have 4 types

dungcamquang@tdtu.edu.vn 2
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

of rotation corresponding to 4 violation cases that make the tree imbalance.

4.1. Left rotation


When a new node is inserted into a AVL tree and makes it a right-right-unbalanced-
tree. The tree can be re-balanced using left rotation as following:

Figure 2: Left rotation

This is the code of left rotation:


1 private Node rotateLeft (Node x) {
2 Node y = x. right ;
3 x. right = y.left;
4 y.left = x;
5 x. height = 1 + Math.max( height (x.left), height (x. right ));
6 y. height = 1 + Math.max( height (y.left), height (y. right ));
7 return y;
8 }

4.2. Right rotation


When a new node is inserted into a AVL tree and make it a left-left-unbalanced-tree.
The tree can be re-balanced using right rotation as following:

Figure 3: Right rotation

1 private Node rotateRight (Node x) {


2 // your turn
3 }

dungcamquang@tdtu.edu.vn 3
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

4.3. Left-Right rotation


When a new node is inserted into a AVL tree and make it a left-right-unbalanced-
tree. The tree can be re-balanced using left-right rotation.

Figure 4: Left-Right rotation

First, we perform a left rotation on node A (the left subtree of C).

Figure 5: Left-Right rotation

This makes A come to the left subtree of B. And B replaces A to become the left
subtree of C.

Figure 6: Left-Right rotation

Now, node C is remaining unbalanced but it has become case left-left-unbalanced-


tree and right rotation can be used to balance the tree.

4.4. Right-Left rotation


When a new node is inserted into a AVL tree and make it a right-left-unbalanced-
tree. The tree can be re-balanced using right-left rotation.

dungcamquang@tdtu.edu.vn 4
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

Figure 7: Right-Left rotation

First, we perform a right rotation on node C (the left subtree of A).

Figure 8: Right-Left rotation

This makes C come to the right subtree of B. And B replaces C to become the right
subtree of A.

Figure 9: Right-Left rotation

Now, node A is remaining unbalanced but it has become case right-right-unbalanced-


tree and left rotation can be used to balance the tree.

5. Balance
This is the code to re-balance the tree:
1 private Node balance (Node x) {
2 if ( checkBalance (x) < -1) {
3 if ( checkBalance (x. right ) > 0) {
4 x. right = rotateRight (x. right );
5 }
6 x = rotateLeft (x);
7 }

dungcamquang@tdtu.edu.vn 5
Ton Duc Thang University
Faculty of Information Technology Data Structures and Algorithms, Fall 2021-2022

8 else if ( checkBalance (x) > 1) {


9 if ( checkBalance (x.left) < 0) {
10 x.left = rotateLeft (x.left);
11 }
12 x = rotateRight (x);
13 }
14 return x;
15 }

Part II
Excercise
Responsibility of the students in this part:

• Complete all the exercises with the knowledge from Part I.

• Ask your lecturer if you have any question.

• Submit your solutions according to your lecturer requirement.

Exercise 1
Complete the class to build the AVL tree. You can re-use the BST code in the
previous lab (insertion, deletion).
THE END

dungcamquang@tdtu.edu.vn 6

You might also like