Menu
The image above is from "Wikipedia's entry on AVL trees" which Wikipedia indicates is unbalanced. How is this tree not balanced already? Here's a quote from the article:
The balance factor of a node is the height of its right subtree minus the height of its left subtree and a node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.
Both the left and right subtrees have a height of 4. The right subtree of the left tree has a height of 3 which is still only 1 less than 4. Can someone explain what I'm missing?
620
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree then needs a right rotation. As depicted, the unbalanced node becomes the right child of its left child by performing a right rotation.
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.
In AVL trees, after each operation like insertion and deletion, the balance factor of every node needs to be checked. If every node satisfies the balance factor condition, then the operation can be concluded. Otherwise, the tree needs to be rebalanced using rotation operations.
An AVL tree does not create a perfectly balanced binary search trees. Instead it creates a height balanced binary search trees. A height balanced tree is either empty or the height of the left and right subtrees differ by no more than 1.
Node 76 is unbalanced, for example, because its right subtree is of height 0 and the left is of height 3.
156
To be balanced, every node in the tree must, either,
Or, if it has only one child, that child must be a leaf.
In the chart you posted, 9, 54 & 76 violate the last rule.
Properly balanced, the tree would look like:
Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76
UPDATE: (after almost 9 years, I created a cool online chart for the graph at draw.io)
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
