Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What does the AVL stand for in AVL tree?

An AVL tree is the same as a self-balancing binary search tree. What does AVL stand for? Does it have to do with the name of the inventor?

like image 469
Jing Ma Avatar asked Jun 17 '16 10:06

Jing Ma


2 Answers

It is the name of the inventors like you guessed. From wiki:

AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis

Their names spell the acronym, AVL.

like image 53
Idos Avatar answered Sep 28 '22 03:09

Idos


An AVL tree is another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.

Reference https://www.cs.auckland.ac.nz/software/AlgAnim/AVL.html

like image 24
madhan kumar Avatar answered Sep 28 '22 05:09

madhan kumar