Introduction to Python Programming and Data Structures, 3rd Edition by Pearson

CHAPTER 20

AVL Trees

 

Objectives

• To know what an AVL tree is (§20.1).
• To understand how to rebalance a tree using the LL rotation, LR rotation, RR rotation, and RL rotation (§20.2).
• To know how to design the AVLTree class (§20.3).
• To insert elements into an AVL tree (§20.4).
• To implement node rebalancing (§20.5).
• To delete elements from an AVL tree (§20.6).
• To implement the AVLTree class (§20.7).
• To test the AVLTree class (§20.8).
• To analyze the complexity of search, insert, and delete operations in AVL trees (§20.9).

20.1 Introduction

Key Point

AVL Tree is a balanced binary search tree.

Chapter 19, “Binary Search Trees,” introduced ...