Really confused about AVL Tree

This is a discussion on Really confused about AVL Tree within the C Programming forums, part of the General Programming Boards category; Per wiki: In an AVL Tree, the heights of the two child subtrees of any node differ by at most ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    68

    Really confused about AVL Tree

    Per wiki: In an AVL Tree, the heights of the two child subtrees of any node differ by at most one;

    I am not getting this at all, I was going to post it yesterday before I went to sleep, but I figured I would wait & try to figure it out. I am totally stumped on this.

    My AVL Tree code builds a tree that looks like this:

    HERE

    Would it be breaking the definition since (struct 8->right) height is 0, and (23->right->right) height is 2? (difference of 2). Or do we not count (struct 8->right) height, since it does not exist?

    I used the code my professor provided, but I was thinking that 16 should be root of 8 & 42, 8 should be the root of 15 & 4, and 42 would be the root of 16 & 72.

    I compared the code with other AVL Tree code (in C++), and everything matched up for the most part (the max of 2 numbers was different, but that's short code).

  2. #2
    Registered User
    Join Date
    Feb 2009
    Posts
    68
    If anyone wants to know what the code looks like (note, I didn't include main because it's totally irrelevant, along with the readFile function, I get the correct pointer returned):

    Code:
    int Height(Position P)
    {
    	if(P == NULL)
    		return -1;
    	else
    		return P->Height;
    }
    
    
    
    AVLTree Insert(ElementType X, AVLTree T)
    {
    	if(T == NULL)
    	{
    		T = malloc(sizeof(struct AVLNode));
    		if(T==NULL)
    		{
    			printf("Fatal Error...Exiting!\n");
    			exit(1);
    		}
    		else
    		{
    			T->Element = X;
    			T->Height = 0;
    			T->Left = NULL;
    			T->Right = NULL;
    		}
    
    
    	}
    	else if(X < T->Element)
    	{
    		T->Left = Insert(X, T->Left);
    		if(Height(T->Left) - Height(T->Right) == 2)
    		{
    			if(X < T->Left->Element)
    				T = SingleRotateWithLeft(T);
    			else
    				T = DoubleRotateWithLeft(T);
    		}
    	}
    	else if(X > T->Element)
    	{
    		T->Right = Insert(X, T->Right);
    		if(Height(T->Right) - Height(T->Left) == 2)
    		{
    			if(X > T->Right->Element)
    				T = SingleRotateWithRight(T);
    			else
    				T = DoubleRotateWithRight(T);
    		}
    	}
    
    	T->Height = (Max(Height(T->Left), Height(T->Right)) + 1);
    	return T;
    }
    
    Position SingleRotateWithLeft(Position K2)
    {
    
    	Position K1;
    	K1 = K2->Left;
    	K2->Left = K1->Right;
    	K1->Right = K2;
    
    	K2->Height = (Max(Height(K2->Left), Height(K2->Right)) + 1);
    	K1->Height = (Max(Height(K1->Left), (K2->Height)) + 1);
    
    	return K1;
    }
    
    Position SingleRotateWithRight(Position K1)
    {
    	Position K2;
    	K2 = K1->Right;
    	K1->Right = K2->Left;
    	K2->Left = K1;
    
    	K1->Height = (Max(Height(K1->Left), Height(K1->Right)) + 1);
    	K2->Height = (Max(Height(K2->Right), (K1->Height)) + 1);
    
    	return K2;
    }
    
    
    Position DoubleRotateWithLeft(Position K3)
    {
     	K3->Left = SingleRotateWithRight(K3->Left);
    
    	return SingleRotateWithLeft(K3);
    }
    
    Position DoubleRotateWithRight(Position K1)
    {
     	K1->Right = SingleRotateWithLeft(K1->Right);
    
    	return SingleRotateWithRight(K1);
    }
    
    int Max(int x, int y)
    {
    	if(x < y)
    		return y;
    	return x;
    }

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,302
    Quote Originally Posted by madmax2006 View Post
    Would it be breaking the definition since (struct 8->right) height is 0, and (23->right->right) height is 2? (difference of 2). Or do we not count (struct 8->right) height, since it does not exist?
    Code:
          15
        /    \
      8        23
     /        /  \
    4        16   42
                   \
                    72
    The height of the node with 8 is one because there is one level of node(s) below it. The height of the node with 23 is two because there are two levels of node(s) below it. The image is of a valid AVL tree.
    Heights:
    (4) -> 0
    (16) -> 0
    (72) -> 0
    (8) -> 1
    (42) -> 1
    (23) -> 2
    (15) -> 3

    AVL trees don't guarantee absolutely optimal balancing. It would be too inefficient (take more work that it's worth) to rotate the tree into:
    Code:
          16
        /    \
      8        42
     / \      /  \
    4   15   23   72
    Only the search for one of the items out of seven gets a path one-node shorter, the other six remain the same.
    Last edited by iMalc; 02-27-2010 at 02:57 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 08:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21