AVL Tree

[bob89]

I know that there are plenty of open source implemenations of AVL trees out there but I was wondering if it is possible to have a AVL that has repeat entries. I want to use one so I can search records by various fields. Eg I would have one for forename and then a forename would have a unique ID with it that I could then load up the whole record. The problem is that forename isnt unique.
If it is possible could someone point me to a simple open source implementation.

[Narue]

This library is written in C, but it allows duplicates. The duplicate check is actually an extra step for insertion because proper duplicate handling falls out of the usual binary search tree insertion logic.

Keep in mind that the above library treats duplicates as a stack. When searching and deleting, the first match will be the result. You may want to change that so that all matches are returned, or something similar. It really depends on your needs, but the changes are easy and minimal.

[bob89]

I want it so that all nodes of a certain search key are returned. I have to admit that my knowledge of C or C++ is pretty basic. Any pointers on how to change it and even how to use it are welcome

[Narue]

I'll save myself quite a bit of typing and link you to some general information that will help you understand the library better as well as binary search trees and AVL trees in general:

Binary Search Trees Part 1
AVL Trees

The easiest way to get all of the duplicates is to perform a traversal (any kind of traversal) and add the node to a vector when you find a match:

// Based on the tutorial code for simplicity
vector<jsw_node*> find_matches ( jsw_tree *tree, int data )
{
    vector<jsw_node*> result;
    jsw_node *it = tree->root;
    stack<jsw_node*> up;
 
    if ( it == 0 )
        return;
 
    up.push ( it );
 
    while ( !up.empty() ) {
        it = up.top();
        up.pop();

        if ( it->data == data )
            result.push_back ( it );
 
        if ( it->link[1] != 0 )
            up.push ( it->link[1] );

        if ( it->link[0] != 0 )
            up.push ( it->link[0] );
    }

    return result;
}

[Danish Emerald]

I m written a code for avl tree in C++ ,include insertion,deletion,searching,finding height of tree etc, very easy to understand ,perfect for for beginners
if u want it mail me at SNIP

[arkoenig]

Is there a reason that you are insisting on an AVL tree rather than just a data structure that will use an order relation to store values in a way that will keep equals together? Because if you just need the latter, you should be able to get std::set (or perhaps std::multiset) to do what you want by defining an appropriate comparison function.

[paladin.lone]

Here is a link which does as you were asking, it detects duplicates when inserting and before balancing.
http://www.refcode.net/2013/02/balanced-avl-binary-search-trees.html, hopefully this helps.

Here is the insert routine:

//Insert i into the tree t, duplicate will be discarded
//Return a pointer to the resulting tree.                 
Tree * insert(int value, Tree * t) 
{
  Tree * new_node;
  if (t == NULL) 
  {
    new_node = (Tree *) malloc (sizeof (Tree));
    if (new_node == NULL) 
    {
     return t;
    }

    new_node->element = value;
    new_node->height = 0;
    new_node->left = new_node->right = NULL;
    return new_node;
  }
  else if (value < t->element) 
  {
    t->left = insert(value, t->left);
    if (height(t->left) - height(t->right) == 2)
    {
      if (value < t->left->element)
      {
        t = single_rotation_with_left(t);
      }
      else
      {
        t = double_rotation_with_left(t);
      }
    }
  } 
  else if (value > t->element) 
  {
    t->right = insert(value, t->right);
    if (height(t->right) - height(t->left) == 2)
    {
      if (value > t->right->element)
      {
        t = single_rotation_with_right(t);
      }
      else
      {
        t = double_rotation_with_right(t);
      }
    }
   } 
  //else duplicate, ignore it

  t->height = MAX(height(t->left), height(t->right)) + 1;
  return t;
}

Here is the search routine:

Tree *find(int elem, Tree *t)
{
  if (t == NULL)
  {
    return NULL;
  }

  if (elem < t->element)
  {
    return find(elem, t->left);
  }
  else if (elem > t->element)
  {
    return find(elem, t->right);
  }
  else
  {
    return t;
  }
}