A Demo of an AVL Tree

Introduction

This article presents a demo of an AVL Tree, which only describes inserting, removing, and searching a node. Originally, it was written with C, built by a DDK compiler, so it can be easily changed to adapt for a different driver.

Inserting a Node

There are two process to insert a node: First, the node is inserted into the tree as inserting it in a binary search tree. Second, balance the tree.

There are four rotate types to balance the tree. They are described in the following list:

  • LL-rotate
  • LR-rotate
  • RL-rotate
  • RR-rotate

Removing a Node

Removing a node is more complex than inserting one. You can find the theories about it on the Internet, so I needn't make any extra explanation about it here.

Program Usage

  1. Select the AvlTree->Demo to automatically generate an AVL Tree for viewing.
  2. Fill the edit box on the toolbar, and then select Insert or Remove. This will insert or remove the node from the tree.

Conclusion

By the way, please let me know if you have any questions or find bugs in the code!!



Downloads

Comments

  • SQUvFa XD Rt eMv aRMp nR

    Posted by RMxUxzMudH on 04/20/2013 02:18pm

    buy tramadol online tramadol withdrawal restless legs - cheap tramadol online

    Reply
  • insert same keywords

    Posted by roam04 on 08/22/2006 03:46am

    thanks to your sharing code for the AVL Tree code. in your code, if the Weight (pointer) is same or Weight->dwID is same, the node will be inserted only once. my question is ? How to modify the code to fulfill the following functions: 1. if Weight->dwID is same but Weight is not same , I want one new node could be inserted ? 2. when I use the find function, the function return two PAVL_NODE pointer , individually indicating the first and last elements within a range in the CAvlTree, in this range all elements has the same key words (dwID).

    Reply
  • Bug Report!!

    Posted by nowol79 on 02/09/2006 06:55am

    We updated remove a parent bug!! but we find another bug. Insert in TreeDemo 97,94,98,92,95,99,93,96 and then deleted 97, 94's bf is wrong!! because, 95(bf:0) 94(bf:1) 98(bf:0) 92(bf:-1) 96(bf:0) 99(bf:0) 93(bf:0) inserted(92~99) and deleted(97)after 94's bf must be "2"!! plz help bug fix!!^^

    • bugs update

      Posted by Polo.G.Z on 02/13/2006 11:28pm

      There is a bug on balancing tree after RLRotate and LRRotate.
      
      Please insert codes to line 640 and 655 in function CAvlTree::BalanceAfterRemove to fix the bug.
      
      if(Node->Parent)
      {
        if(Node->Parent->Left)
           BalanceAfterRemove(Node->Parent->Left);
        if(Node->Parent->Right)
           BalanceAfterRemove(Node->Parent->Right);
      }
      
      //////////////////////////////////////////////////
      BOOL CAvlTree::BalanceAfterRemove(PAVL_NODE Node)
      {
      	DWORD Height = Node->Height;
      	PAVL_NODE parent = Node->Parent;
      	BOOL bLeft = ((parent)&&(parent->Left == Node))?TRUE:FALSE;
      	
      	if((Node->Left)&&(Node->Right))
      	{
      		Node->bf = (char)(Node->Left->Height - Node->Right->Height);
      		Node->Height = (Node->Left->Height >= Node->Right->Height)
      			? (Node->Left->Height+1) : (Node->Right->Height+1);
      	}
      	else if(Node->Left)
      	{
      		Node->bf = (char)(Node->Left->Height+1);
      		Node->Height = Node->Left->Height+1;
      	}
      	else if(Node->Right)
      	{
      		Node->bf = (char)(-1 - Node->Right->Height);
      		Node->Height = Node->Right->Height+1;
      	}
      	else
      	{
      		Node->bf = 0;
      		Node->Height = 0;
      	}
      	
      	if(Node->bf == 2)
      	{
      		if(Node->Left->bf == 1)
      			LLRotate(Node);
      		else
      		{
      			LRRotate(Node);
      			if(Node->Parent)
      			{
      				if(Node->Parent->Left)
      					BalanceAfterRemove(Node->Parent->Left);
      				if(Node->Parent->Right)
      					BalanceAfterRemove(Node->Parent->Right);
      			}
      		}
      	}
      	else if(Node->bf == -2)
      	{
      		if(Node->Right->bf == -1)
      			RRRotate(Node);
      		else
      		{
      			RLRotate(Node);
      			if(Node->Parent)
      			{
      				if(Node->Parent->Left)
      					BalanceAfterRemove(Node->Parent->Left);
      				if(Node->Parent->Right)
      					BalanceAfterRemove(Node->Parent->Right);
      			}
      		}
      	}
      	
      	if(parent)
      	{
      		if(bLeft)
      		{
      			if(Height == parent->Left->Height)
      				return TRUE;
      		}
      		else
      		{
      			if(Height == parent->Right->Height)
      				return TRUE;
      		}
      	}
      	else
      	{
      		return TRUE;
      	}
      	
      	return BalanceAfterRemove(parent);
      }
      
      
      Thanks.
      Polo.G.Z

      Reply
    Reply
  • update

    Posted by Polo.G.Z on 05/20/2004 02:00am

    Thanks for Olaf's testing. Actually, there are some bugs on inserting/removing nodes from an AVL-tree. I have corrected it, and the files have been updated.

    Reply
  • qweawe

    Posted by bandonghanhhcm on 04/26/2004 09:44am

    awedawdawdawdawdw

    Reply
  • Additional Note

    Posted by usmarine on 03/04/2004 05:55am

    You should also mention why and when someone would benefit from using an AVL tree over a hash table or another type of tree algorithm. Also you should mention something about using a lazy delete method. In general the article was pretty good. You could have added template ability but oh well.

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Hurricane Sandy was one of the most destructive natural disasters that the United States has ever experienced. Read this success story to learn how Datto protected its partners and their customers with proactive business continuity planning, heroic employee efforts, and the right mix of technology and support. With storm surges over 12 feet, winds that exceeded 90 mph, and a diameter spanning more than 900 miles, Sandy resulted in power outages to approximately 7.5 million people, and caused an estimated $50 …

  • The impact of a data loss event can be significant. Real-time data is essential to remaining competitive. Many companies can no longer afford to rely on a truck arriving each day to take backup tapes offsite. For most companies, a cloud backup and recovery solution will eliminate, or significantly reduce, IT resources related to the mundane task of backup and allow your resources to be redeployed to more strategic projects. The cloud - can now be comfortable for you – with 100% recovery from anywhere all …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds