--- title: "Describe an AVL tree" subject: "Data Structure and Algorithm" chapter: 6 key: "semester_4/data_structure_and_algorithm:avl-describe" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-describe site: BCT Engineering --- # Describe an AVL tree Data Structure and Algorithm · Chapter 6: Trees - Asked in: 2073 Magh, 2 marks - Video: [Lec-58: Introduction to AVL Tree in Data Structure with Examples | All Imp Points of AVL](https://www.youtube.com/watch?v=E9DOBLNB-aE) — Gate Smashers - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/avl-describe - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-6 ## Question Describe an AVL tree. ## Short answer An AVL tree is a self-balancing BST where every node's balance factor (height difference of left and right subtrees) is -1,0 or +1. Any violation after insertion or deletion is corrected by single or double rotations, maintaining height O(log n) and all operations O(log n). ## Answer An **AVL tree** (Adelson-Velsky and Landis, 1962) is a self-balancing binary search tree in which, for every node, the heights of the left and right subtrees differ by at most one. - **Balance factor** = height(left) − height(right) ∈ {−1, 0, +1}. - It is a BST, so left keys < node < right keys, and in-order traversal gives sorted order. - After an insertion or deletion that makes a balance factor ±2, the tree is restored by single (LL, RR) or double (LR, RL) rotations. - Height of an AVL tree with n nodes is always O(log n) (at most about 1.44·log₂ n), so search, insertion and deletion take O(log n) even in the worst case. ```text 30 (bf +1) / \ 20 40 A valid AVL tree / 10 ``` Here node 20 has bf = +1 (left height 1, right height 0), node 30 has bf = +1 (left height 2, right height 1), and the leaves 10 and 40 have bf = 0, so the tree is balanced. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What defines an AVL tree? A. A BST where subtree heights of every node differ by at most one B. A BST where all leaves are red C. A complete binary tree D. A tree where left and right heights are equal Answer: A. It is a height-balanced BST. (Key point: Definition) 2. How is balance restored after an insertion makes a balance factor +-2? A. By deleting the root B. By single or double rotations C. By recolouring nodes D. By rebuilding the tree Answer: B. LL and RR use single rotations; LR and RL use double rotations. (Key point: Repair) 3. What are search, insert and delete costs in an AVL tree? A. O(n) worst case B. O(1) C. O(log n) even in the worst case D. O(n log n) Answer: C. Height is at most about 1.44 log2 n. (Key point: Complexity) ## Related in Data Structure and Algorithm - [AVL tree for month names](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-months) — Data Structure and Algorithm, chapter 6, asked 2× - [B-tree insertion algorithm; AVL of months](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abtree-insertion-avl-months) — Data Structure and Algorithm, chapter 6, asked 2× - [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6 - [AVL tree for 3, 2, 1, 4, 5, 6, 7, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-3-2-1-4) — Data Structure and Algorithm, chapter 6 - [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6 - [Advantages of AVL tree](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-advantage) — Data Structure and Algorithm, chapter 6