AVL TREE
AVL Tree is a Binary Search Tree which can balance itself in order to avoid the worst case scenario of a BST. To balance the tree, we need to check the tree for their balance factor every time a data is inserted into the tree. Balance factor is found by simply subtracting the left child of a node with the right child of the node. In order to achieve balance, every balance factor in a tree must be made into either -1, 0, or 1. If a balance factor doesn't satisfy the condition, the middle-most child of all the children from the unbalanced node will be "dragged" onto the unbalanced node to create a balance, replacing it's parent node.
It will look a little something like this:
This is what a left unbalanced tree looks like. Like its name, it's a tree where an unbalance happens on the left side of the tree. A rotation from the left to the right is made to balance this problem. By making the middle (median) node from the unbalanced tree into a new root for the tree, it solves the unbalances as all the balance factors in the tree satisfies the condition of an AVL tree.
This is a right unbalanced tree. It's quite literally the same thing as the left unbalanced tree with the difference of it being unbalanced on the right side of the tree. Like the previous one, we also "rotate" the tree here to the left in order to balance the tree.
