tailieunhanh - Data Structures and Algorithms - Chapter 7b: AVL Tree

AVLTree is: •A Binary Search Tree, •in which the heights of the left and right subtreesof the root differ by at most 1, and •the left and right subtreesare again AVLtrees. | AVL Tree DEFINITION AVL Tree is A Binary Search Tree in which the heights of the left and right subtrees of the root differ by at most 1 and the left and right subtrees are again AVL trees. 1 AVL Tree The name comes from the discoverers of this method son-Vel skii and . The method dates from 1962. 2 Balance factor Balance factor left_higher HL HR 1 equal_height HL HR right_higher HR HL 1 Hl Hr the height of left and right subtree In C enum Balance_factor left_higher equal_height right_higher