AVL trees confusion about height

1
votes

AVL tree examples

I'm so confused about AVL trees. My textbook says "An AVL tree is a BST with a height balance property and specific operations to rebalance the tree when a node is inserted or removed. This section discusses the balance property; another section discusses the operations. A BST is height balanced if for any node, the heights of the node's left and right subtrees differ by only 0 or 1." Do they mean left and right or something? Is it cause on the second one, from A - F would have a height of two? From A to C then C to E then E to F. I'm so confused, originally I thought they meant height up and down. Which would give left side a height of three, and right side a height of two

1
javaavl-tree
You seem to be missing the pictures, so we have no clue what A-F really is. However, you can refer this blog skerritt.blog/avl – isopropylcyanide
Thanks, lemme check it out – Abdulahad Ghuman
I think the wording is misleading. A BST is height balanced if for all nodes, the heights of the node's left and right subtrees differ by only 0 or 1. For the second example, the node "C" violates this requirement (its left subtree has a height of 2, its right subtree has a height of 0). This single violation of the balance requirement means that the whole tree is not an AVL tree. – Thomas Kläger

1 Answers

0
votes

Simply We can say if the particular node's left side maximum edges ( a long walk until we reach the leaf node) l and right side maximum edges r and if they satisfied the following equation

| l - r  | <= 1

then that node is balanced. If all nodes in BST are balanced, then that BST is balanced one.

In your AVL tree example,

Each letter you can check as below

  1. D --> |2 - 1| = 1 balanced node
  2. C --> |1 - 0| = 1 balanced node
  3. A --> |0 - 0| = 0 balanced node
  4. E --> |0 - 0| = 0 balanced node

In your not AVL tree example

  1. D --> |3 - 2| = 1 balanced node
  2. C --> |2 - 0| = 2 not balanced node
  3. E --> |0 - 1| = 1 balanced node
  4. A --> |0 - 1| = 1 balanced node
  5. B --> |0 - 0| = 0 balanced node
  6. F --> |0 - 0| = 0 balanced node

When we have at least one unbalanced node which means the BST is not balanced.