Tugas

AVL Tree  AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where {\displaystyle n}n 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. AVL tree was made to simplify BST to make data gathering of one(AVL) easier than the other(BST) due to AVL nature to always having itself balanced. The AVL Tree is considered balanced if the total height of the right child subtracted by the total height of the right child is either 1,0, or -1 . AVL Rotation To balance itself, an AVL tree may perform the following four kinds of rotations − Left rotation Right rotation Left-Right rotation Right-Left rotation The first two rotations are single rotations and the next two rotations