Growing with the Web

Welcome!

My name is Daniel Imms and I'm a software engineer from Australia. I live in Seattle and work at Amazon on the Silk Web Browser. I use this blog as a platform to learn, revise and teach various software development topics.

AVL tree

Published
Tags:

The AVL tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, is a type of self-balancing binary search tree. The tree re-organises itself after every insert and delete so that the tree height is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.