Help with AVL tree (balanced tree)
Author Message Help with AVL tree (balanced tree)

Hei everyone,

I'm working on a project in which I'm using a balanced tree (AVL tree).
The implementation is linked one (trough pointers), my question is the
following:

If having the key value of one of the nodes of the tree how can I find
the successor and the predecessor of this node.

As an example I have the following integers: 7 3 1 2 9 10 8, and I insert
them in that order into the tree.One important thing is that the tree is
sorted.So now if I would print the tree in an Inorder traversal I would get
1 2 3 7 8 9 10.Now let's say I want the successor and predecessor of 7 (which
are in this case 8 and 3), how can I find them???

Any help is welcome, thanks in advance.

Sat, 26 Aug 1995 21:21:42 GMT  Help with AVL tree (balanced tree)

Quote:
> I'm working on a project in which I'm using a balanced tree (AVL tree).
...
> If having the key value of one of the nodes of the tree how can I find
> the successor and the predecessor of this node.

My algorithm works for every binary tree; but you need in every node a
pointer to its father. To find the successor to a node, knowing its

1) If the node at address pN has a right child, store in pN its
2) If pN has a left child, store in pN its address; otherwise pN is
3) If the father of pN does not exist, the answer is that your node
is the last one of the tree.
4) If the father is at the right of pN (ie pN is its left child),

In C:

Node *NextRight(
Node *pN
){

/**
| Finds in the tree the node following, in ascending order,
| node pN (or NULL if pN is the last node).
| WARNING: pN MUST POINT TO A VALID NODE STRUCTURE.
**/

if (pN->right != NULL) {
pN = pN->right;
while (pN->left != NULL) pN = pN->left;
return pN;
}

while (pN->father != NULL   &&   pN->father->right == pN) {
pN = pN->father;
}
return pN->father;

Quote:
}

For the predecessor, act simmetrically.
Hope that helps...

From Italy,     Maurizio

- Only my opinions ... --------- (programmer since 1968) --------- HAM: I3NOO -
Maurizio Loreti - University of Padova - Department of Physics - Padova, Italy

Sun, 27 Aug 1995 18:01:34 GMT  Help with AVL tree (balanced tree)
Oops... I forgot:
Quote:
> 2) If pN has a left child, store in pN its address; otherwise pN is

2 bis) Repeat step 2

Altough that was clear in the source code :-)

From Italy,     Maurizio

Sun, 27 Aug 1995 18:09:12 GMT  Help with AVL tree (balanced tree)

*> Hei everyone,
*>
*> I'm working on a project in which I'm using a balanced tree (AVL tree).
*> The implementation is linked one (trough pointers), my question is the
*> following:
*>
*> If having the key value of one of the nodes of the tree how can I find
*> the successor and the predecessor of this node.
*>
*> As an example I have the following integers: 7 3 1 2 9 10 8, and I insert
*> them in that order into the tree.One important thing is that the tree is
*> sorted.So now if I would print the tree in an Inorder traversal I would get
*> 1 2 3 7 8 9 10.Now let's say I want the successor and predecessor of 7 (which
*> are in this case 8 and 3), how can I find them???
*>
*> Any help is welcome, thanks in advance.
*>

Here you go.  Should work, and docementation is provided.
Provided is routines to find an element, find the successor and
predecessor of an element...

Hope it helps...

-Jody

=======================

/*
* Assuming node structure similar to this...
*/

#define MAX_ITEMS       5
typedef struct _tag_AVL_NODE
{
int                   count;
struct _tag_AVL_NODE  *parent;
int                   item[MAX_ITEMS];
struct _tag_AVL_NODE  *child[MAX_ITEMS + 1];

Quote:
} AVL_NODE;

#define RIGHT_CHILD(node, index) ((node)->child[index + 1])
#define LEFT_CHILD(node, index) ((node)->child[index])
#define RIGHTMOST_CHILD(node) ((node)->child[node->count])
#define LEFTMOST_CHILD(node) ((node)->child)

/*
* Get the node pointer and the array index of the target
*
* Returns 0 if found.
*/
int
avl_find(AVL_NODE *node, int target, AVL_NODE **found_node,
int *found_index)
{
int   i;

/*
* If we are at the bottom, STOP!
*/
if (node == NULL)
{
return -1;
}

/*
* Search for the item among the local data objects.
*/
for (i = 0; i < node->count; i++)
{
/*
* We found it, return success!
*/
if (node->item[i] == target)
{
*found_node = node;
*found_index = i;
return 0;
}

/*
* The target value is less than the curent item, so go down
* the left subtree.
*/
else if (target < node->item[i])
{
return avl_find(LEFT_CHILD(node, i), target, found_node,
found_index);
}
}

/*
* To get here, the target value is bigger than all the ones in our
* local store, so traverse down the rightmost subtree.
*/
return avl_find(RIGHTMOST_CHILD(node), target, found_node,
found_index);

Quote:
}

/*
* Find the index of the child pointer <child> in the node <node>.
*/
static
int
find_ptr_index(AVL_NODE *node, AVL_NODE *child)
{
int   i;

for (i = 0; i < node->count + 1; i++)
{
if (node->child[i] == child)
{
return i;
}
}
return -1;

Quote:
}

/*
* Finds the least value in the sub-tree rooted by <node>.
*/
int
avl_least(AVL_NODE *node, AVL_NODE **found_node, int *found_index)
{
if (node == NULL)
{
return -1;
}

/*
* If my leftmost child is null, I'm at the bottom, so I return the
* first element in the array.
*/
if (LEFTMOST_CHILD(node) == NULL)
{
*found_node = node;
*found_index = 0;
return 0;
}

/*
* If I have children, then I'm not the least in my subtree.
*/
return avl_least(LEFTMOST_CHILD(node), found_node, found_index);

Quote:
}

/*
* Finds the greatest value in the sub-tree rooted by <node>.
*/
int
avl_greatest(AVL_NODE *node, AVL_NODE **found_node, int *found_index)
{
if (node == NULL)
{
return -1;
}

/*
* If my rightmost child is null, I'm at the bottom, so I return the
* last element in the array.
*/
if (RIGHTMOST_CHILD(node) == NULL)
{
*found_node = node;
*found_index = node->count - 1;
return 0;
}

/*
* If I have children, then I'm not the greatest in my subtree.
*/
return avl_greatest(RIGHTMOST_CHILD(node), found_node, found_index);

Quote:
}

/*
* Find the successor item of the current one
*
* Returns 0 if there is a successor, non zero if not.
*/
int
avl_successor(AVL_NODE *node, int index, AVL_NODE **found_node,
int *found_index)
{
if (node == NULL)
{
return -1;
}

/*
* If I have no right child, then I got to do some special dancing.
*/
if (RIGHT_CHILD(node, index) == NULL)
{
/*
* If there is another element in the array bigger than me, return
* that one since it is the next one bigger than me.
*/
++index;
if (index < node->count)
{
*found_node = node;
*found_index = index;
return 0;
}

/*
* There is not another element in this array bigger than me and
* I do not have any children.  That means that I have to go up
* to my parent.
*/
else
{
AVL_NODE  *parent;
int       n;

parent = node->parent;
while (parent != NULL)
{
/*
* Find the index in my parent's child array of my node pointer.
* Note that this index will also be the index of the next
* largest element in my parent's array.  If the index is valid
* for the node, return that value, else we need to go to my
* parent's parent.  This continues until we get to the top
* of the tree.  If we still haven't found it then we know
* that there is not a larger value in the tree.
*/
n = find_ptr_index(parent, node);
if (n < parent->count)
{
*found_node = parent;
*found_index = n;
return 0;
}
node = parent;
parent = node->parent;
}

/*
* It ain't there!
*/
return -1;
}
}

/*
* Otherwise, return the least element of my right child.
*/
return avl_least(RIGHT_CHILD(node, index), found_node, found_index);

Quote:
}

/*
* Find the predecessor item of the current one
*
* Returns 0 if there is a predecessor, non zero if not.
*/
int
avl_predecessor(AVL_NODE *node, int index, AVL_NODE **found_node,
int *found_index)
{
if (node == NULL)
{
return -1;
}

/*
* If I have no left child, then I got to do some special dancing.
*/
if (LEFT_CHILD(node, index) == NULL)
{
/*
* If there is another element in the array less than me, return
* that one since it is the immediate one less than me.
*/
if (index > 0)
{
*found_node = node;
*found_index = index - 1;
return 0;
}

/*
* There is not another element in this array less than me and
* I do not have any children.  That means that I have to go up
* to my parent.
*/
else
{
AVL_NODE  *parent;
int       n;

parent = node->parent;
while (parent != NULL)
{
/*
* Find the index in my parent's child array of my node pointer.
* Note that this index will also be the index of the next
* largest element in my parent's array.  Therefore, I need to
* adjust it down by one element.  If the new index is valid
* for the node, return that value, else we need to go to my
* parent's parent.  This continues until we get to the top
* of the tree.  If we still haven't found it then we know
* that there is not a larger value in the tree.
*/
n = find_ptr_index(parent, node) - 1;
if (n >= 0)
{
*found_node = parent;
*found_index = n;
return 0;
}
node = parent;
parent = node->parent;
}
return -1;
}
}

/*
* Otherwise, return the greatest value of my left child.
*/
return avl_greatest(LEFT_CHILD(node, index), found_node, found_index);

Quote:
}

--

Wed, 30 Aug 1995 08:58:53 GMT

 Page 1 of 1 [ 4 post ]

Relevant Pages