Lesson 5 of 81960–19728 min
Trees and binary search trees
In 1962 two Soviet mathematicians, Georgy Adelson-Velsky and Evgenii Landis, published "An algorithm for the organization of information". It described a binary search tree that repaired its own shape after every insertion so that it could never grow lopsided. The structure is named after their initials: the AVL tree.
They needed it because an ordinary search tree has a nasty failure mode: feed it data that is already sorted and it degrades into a linked list, and every search becomes a walk from one end to the other.
The rest of this lesson is part of Pro
Create a free account to read the first lesson of every path, and go Pro for the rest.
Sources
- Algorithms, 4th edition, §3.2 Binary Search Trees — R. Sedgewick and K. Wayne, Princeton University
- Algorithms, 4th edition, §3.3 Balanced Search Trees — R. Sedgewick and K. Wayne, Princeton University
- 6.006 Introduction to Algorithms (Spring 2020): binary trees and AVL — MIT OpenCourseWare