Search code examples
javatreebinary-treeavl-treered-black-tree

Is this an AVL or Red-Black Tree?

image

I have a simple question, mainly due to my brain quitting on me. Could this be considered an AVL tree? Also could this be considered a Red-Black tree?

I believe that this would not be an AVL tree because it does not look properly balanced, but I am unsure if that is correct.

I am also unsure on if this is a Red-Black tree for the same reasoning.

Solution

  • According to wikipedia, AVL trees are a type of self-balancing binary search tree, where the difference in height from the root to any two leaves is at most one. In your case, the difference between the height of leaf "f" and that of leaf "m" is 2. Therefore, it is not an AVL tree.

    Red-Black trees store in each of their leaves the color information, Red or Black - I can't see any such information in your attached tree, so it is not a RB tree either.

    EDIT:

    According to sprinter's comment, the tree could be a RB tree with colors not shown as the distance to the deepest leaf is no more than twice the distance to the shallowest leaf.