Talk:Data Structures/Trees

From Wikibooks, the open-content textbooks collection

[edit] balance

"A balanced binary search tree according to the following specification: The height difference between any two sibling nodes must not exceed one."

Shouldn't this rather be:

"A balanced binary search tree according to the following specification: The height difference between any two leaf nodes must not exceed one."

Note that any two sibling nodes always have the same parent and are on the same level, so the height difference between them will never exceed zero.

YES! I think you are right! Anyone revise it? I am a newbie. Visame (talk) 19:59, 3 May 2008 (UTC)

Are you talking about AVL trees in particular, or balanced binary search trees in general?

Alas, this module's definition of "height" and "depth" seem confusing.

The sentence you quoted above was the old definition of an AVL tree on this page.

Today I changed the AVL definition on this page to:

AVL: A balanced binary search tree according to the following specification: the heights of the two child subtrees of any node differ by at most one.

(I copied that sentence from w: AVL tree).

Does the following technically qualify as a "balanced" AVL tree, even though it has leaves on 3 different levels?

         E 4
        / \
       /   \
      /     \
     /       \
    B 2       H 3
   / \       / \
  /   \     /   \
 A 0  C 1  F 1   J 2
       \   \    / \
       D 0 G 0 I 0 K 1
                    \
                     L 0

The letter is the value stored in the node; the number is the "height" of that node.

Leaves always have a height of 0, right?

I'm assuming that the "height of the left subtree of a node" that doesn't have a left child is "-1".

Is there a name for the kind of binary trees where every level is full of nodes, except possibly the "deepest" level? --DavidCary (talk) 21:33, 2 September 2008 (UTC)