Generic Data Structures and Algorithms in Go: An Applied Approach Using Concurrency, Genericity and Heuristics

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2022

R. WienerGeneric Data Structures and Algorithms in Gohttps://doi.org/10.1007/978-1-4842-8191-8_10

10. AVL Trees

Richard Wiener¹  

(1)

Colorado Springs, CO, USA

 

In the previous chapter, we introduced the binary search tree. In such a tree, each node contains a key that is larger than all the keys in its left subtree and smaller than all the keys in its right subtree. Duplicate keys are not allowed.

In building a binary search tree, the balance is dependent on the order in which keys are inserted. For example, if the keys are inserted in ascending order, the search tree resembles a linked list with its nodes to the right of the root node.

In 1962, two Russian mathematicians, ...