Tasapainokerroin

Tasapainokerroin, known in English as the balance factor, is a concept used in computer science, particularly in the context of self-balancing binary search trees like AVL trees. It is a numerical value assigned to each node within the tree that quantifies the difference in height between its left and right subtrees.

The tasapainokerroin is calculated by subtracting the height of the right subtree from the height of the left subtree. For a node to be considered balanced, its tasapainokerroin must fall within a specific range, typically -1, 0, or 1. A tasapainokerroin of -1 indicates that the left subtree is one level taller than the right subtree. A tasapainokerroin of 0 means both subtrees have the same height. A tasapainokerroin of 1 signifies that the right subtree is one level taller than the left.

When an insertion or deletion operation causes a node's tasapainokerroin to fall outside this permissible range, the tree's balancing mechanism is triggered. This involves a series of rotations (single or double) performed on the affected nodes and their ancestors to restore the tree's balanced state. Maintaining a low tasapainokerroin ensures that the tree remains approximately balanced, which is crucial for achieving logarithmic time complexity for search, insertion, and deletion operations. Without this balancing mechanism, binary search trees can degenerate into linked lists, leading to linear time complexity in the worst case.