cid acdea91b5f6c29b2034544baebe1222ebdb4dfddf66bbe854c3e79fb55945d8d · original · open access · via wikipedia
Title: AVL tree Authors: Venue: Wikipedia Year: unknown Canonical: wiki:avl-tree URL: https://en.wikipedia.org/wiki/AVL_tree Collector: wikipedia OA: true ABSTRACT In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by not more than one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.