AVL Tree concepts and example

This tutorial covers the basics concepts of balanced tree in data structure it means avl tree. Different concepts of avl tree such as avl tree balance factor, avl tree example, different avl tree rotation with example have been explained.




What is AVL Tree ?


AVL stands for ADELSON, VELSKI AND LANDIS. It is a tree representation commonly known as ‘AVL TREE’.Here we have explained an avl tree example in the figure. AVL tree is just like a binary search tree(BST) but it is a balanced tree in data structure. Here the the term balanced is used in context of height it means AVL Tree is a height balanced tree.in data structure. It is heught balanced binary search tree.If in binary search tree, at every node avl tree balance factor is 1 or 0 or -1, then it is AVL tree.




Balancing factor of a node in VAL tree is calculated using this formula


Balancing factor = (height of left sub tree) – (height of right sub tree)


An avl tree example is given below




In the above avl tree example the balance factor of node A is 1 and balance factor of node B, C,Dand E is 0.

Why do we need AVL Trees?

If the height of binary search tree is h then most of the BST operations take O(h) time to perform. So if, we manage the height of the tree remains O(logn) after every insertion and deletion, then the upper bound will beO(logn) for all BSToperations.The height of an AVL tree is always O(logn) where n is the number of nodes in the tree. Hence, it has complexity of O(logn).







How can a tree be represented as AVL tree?

Let us take tree representation as




In the first representation, tree is balanced as it has left subtree height and right subtree same. In second representation node A and node B is balanced as they have avl tree balance factor as 0 and 1 respectively whereas, node C is not balanced, Hence complete tree is not balanced. Similarly, in case of third representation it is not a balanced tree in data


AVL Tree Rotations with Example


To make unbalanced tree as balanced tree we need to apply some rotations on the tree .Some avl tree rotations example are as follows

      1.      Left rotation
     2.      Right rotation
     3.      Left-Right rotation
     4.      Right-Left rotation

First and second rotations are single rotations and the next two rotations are double rotations.

NOTE:- To represent unbalanced tree we atleast need height as 2.

Left Rotation

When a node is inserted into the right subtree of the right sub tree then it become unbalanced. Then this problem is known as “RR- PROBLEM” and to make it balanced  we perform a left rotation. An avl tree rotation example for left rotation is explained below.

Left Rotation(RR Problem)



In our example, load factor of node A is 2 so it is  unbalanced as a node is inserted in the right subtree of A's right subtree. SO in order to make the tree balanced we perform the left rotation by making A the left-subtree of B.

Right Rotation

When a node is inserted in the left subtree of the left subtree of Root Node then it become unbalanced. This  problem is known as “LL-PROBLEM” and to balance this tree we perform a right rotation. An avl tree rotation example for right rotation is explained below.

Right Rotation(LL Problem)



As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.

LEFT RIGHT ROTATION(LR)

If we insert a node in right of left subtree of root node then it become unbalanced then we performed Left Right rotation. Here is avl tree rotation example for left right rotation.

As Shown in above figure When we insert a node in the right of node q then it become unbalanced. Here in this case we need to perform two rotation as shown in figure to meake the tree balanced.

RIGHT LEFT  ROTATION(RL)

When a new node is inserted in the left of right sub tree of node P as shown in following figure. Here also we need to perform two rotation. Here is avl tree rotation example for right left rotation.


In the next post we will learn about insertion and deletion in AVL Tree.

COMMENTS

Name

addressing modes types,1,advance-java,2,aktu entrance exam,1,aktu exam schedule,1,ASP,1,bare machine,1,base register and limit register,1,C Programming,12,C Plus Plus,1,C Programming,5,C Programming Questions,1,C programming study material for gate exam,7,Cache Memory,1,CBNST Program,1,Childcare,1,CJ,1,Cloud Computing,1,CN,1,Computer Architecture,2,Computer architecture based questions for gate exam,11,Computer Network,7,Computer Network Study Material,2,Computer network study material for gate,1,Computer Networks,7,Computer networks GATE Questions,1,Computer Science Study Material for Gate,14,computer science study material for gate exam,28,contiguous memory allocation,2,Core Java,3,cyber crime report,1,Cyber crime status,1,cybercrime and security,1,cybercrime examples,1,Data Structure,2,Data Structure Questions,1,Data Transmission Architecture,1,Data Transmission in wsn,1,DBMS,5,dbms question paper,1,DE,1,Digital Electronics,1,DS,4,Dynamic memory allocation in c,1,Electroencephalogram,1,file management in operating system notes,1,Gate 2017,5,Gate 2017 Admit card,1,Gate 2017 Exam Schedule,1,Gate 2017 Syllabus,1,gate cse study material,1,gate practice set,7,gate study material for computer science,12,Gate study material for computer science 2017,1,General,3,HCL Aptitude Test,1,HR Interview Questions,1,HTML,4,Important Date of Gate 2017 Exam,1,Information Security Policy,1,internal and external fragmentation,1,JDBC,2,JS,1,lagrange's interpolation formula,1,lagrange's interpolation formula examples,1,memory fragmentation,1,memory management,1,memory management questions and answer in os,1,Motivational,4,NCER,1,Numerical Techniques Lab,1,OOT,1,Operating System,10,Operating System Gate Questions,1,Operating System Objective Questions,4,Operating System Questions Bank,1,Operating system questions for gate,1,Operating System Study material,2,operating system study material for gate exam,13,Operating system tutorial,2,page swapping,1,paged memory allocation,1,paged memory allocation in operating system,1,Pointer in C,4,Process based question for gate,1,Regression testing,1,relocation in memory management,1,relocation registe,1,relocation register,1,resident monitor,1,resident monitor in operating system,1,routing table,1,Software Engineering,10,Software Engineering baes study material for gate,1,Software Quality Assurance,3,software verification methods,1,Stack,1,Structure in C,1,Study Material for gate Computer Science,7,swapping in memory management,1,swapping in operating system,1,TCS Code Vita,1,TCS Interview Questions,1,Technical Interview,1,Technical Questions from DBMS,1,Thrashing in Operating System,1,Threads concept in operating system,1,Tips to Learn Coding,1,Types of operating system,1,UML,1,What is process control block ?,1,what is software testing?,1,Wireless Sensor Network,3,worst fit algorithm for memory allocation,1,XML,2,
ltr
item
Computer Science Junction: AVL Tree concepts and example
AVL Tree concepts and example
This tutorial covers the basics concepts of balanced tree in data structure it means avl tree. Different concepts of avl tree such as avl tree balance factor, avl tree example, different avl tree rotation with example have been explained.
https://3.bp.blogspot.com/-hf9utC0x8Wc/XC6qsBvZ5LI/AAAAAAAABNQ/64r0-A5v9y0D2i_xR9nEYTW98wHC2FwXgCLcBGAs/s320/AVL_tree.jpg
https://3.bp.blogspot.com/-hf9utC0x8Wc/XC6qsBvZ5LI/AAAAAAAABNQ/64r0-A5v9y0D2i_xR9nEYTW98wHC2FwXgCLcBGAs/s72-c/AVL_tree.jpg
Computer Science Junction
https://www.computersciencejunction.in/2019/01/avl-tree-example.html
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/
https://www.computersciencejunction.in/2019/01/avl-tree-example.html
true
425357657003182083
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share. STEP 2: Click the link you shared to unlock Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy