0

If it is possible could someone point me to a simple open source implementation.

Not Yet Answered # AVL Tree

Narue 5,707 Discussion Starter bob89 Narue 5,707 Danish Emerald arkoenig 340 paladin.lone Write a C program that should create a 10 element array of random integers (0 to 9). The program should total all of the numbers in the odd positions of the array and compare them with the total of the numbers in the even positions of the array and indicate ...

0

If it is possible could someone point me to a simple open source implementation.

0

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.

0

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

0

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;
}
```

0

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

*Edited 6 Years Ago by happygeek*: keep help on-site please

0

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.

0

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;
}
}
```

*Edited 3 Years Ago by paladin.lone*: added code

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

the function that I created to find the ...