Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++
#include"stdafx.h"
#include "avlTree.h"
using namespace std;
#define INSERT 1
#define DELETE 2
 
avlNode* allocAvlNode (avlNodeData *val)
{
    avlNode *node;
 
    node = (avlNode*)malloc(sizeof(avlNode));
    node->data = val;
    node->data->rc = 1;
    node->height = 0;
    node->lChild = NULL;
    node->rChild = NULL;
    node->parent = NULL;
    return node;
}
 
avlNode* newAvlTree (avlNodeData *val)
{
    avlNode *root = NULL;
 
    root = allocAvlNode(val);
    return root;
}
 
void freeNodeData (avlNodeData **data);
void freeAvlNode (avlNode **node, void (*freeNodeData)(avlNodeData **data))
{
    if ((*node)->data->rc <= 1)
        freeNodeData(&((*node)->data));
    else
        --((*node)->data->rc);
    free(*node);
    *node = NULL;
    return;
}
 
int getHeight (avlNode *node)
{
    int h_lChild = (node->lChild) ?  node->lChild->height + 1: 0;
    int h_rChild = (node->rChild) ?  node->rChild->height + 1: 0;
 
    return ((h_lChild >= h_rChild) ? h_lChild : h_rChild);
}
 
void leftRotate (avlNode **node)
{
    avlNode *father = (*node)->parent;
    avlNode *rChild = (*node)->rChild;
    avlNode *grandSon = rChild->lChild;
    avlNode *tmp = *node;
 
    if (father) {
        if (father->lChild == *node)
            father->lChild = rChild;
        else
            father->rChild = rChild;
        rChild->parent = father;/**node gets changed at this point, because of the recursive nature of avlTree_fixup*/
    } else
        rChild->parent = NULL;
    rChild->lChild = tmp;
    tmp->rChild = grandSon;
    if (grandSon != NULL)
        grandSon->parent = tmp;
    tmp->parent = rChild;
    /*update heights*/
    tmp->height = getHeight(tmp);
    rChild->height = getHeight(rChild);
 
    return;
}
 
void rightRotate (avlNode **node)
{
    avlNode *father = (*node)->parent;
    avlNode *lChild = (*node)->lChild;
    avlNode *grandSon = lChild->rChild;
    avlNode *tmp = *node;
 
    if (father) {
        if (father->lChild == *node)
            father->lChild = lChild;
        else
            father->rChild = lChild;
        lChild->parent = father;
    } else
        lChild->parent = NULL;
    lChild->rChild = tmp;
    tmp->lChild = grandSon;
    if (grandSon != NULL)
        grandSon->parent = *node;
    tmp->parent = lChild;
    /*update heights*/
    tmp->height = getHeight(tmp);
    lChild->height = getHeight(lChild);
 
    return;
}
 
inline int balanceFactor (avlNode *node)
{
    int h_lChild = (node->lChild) ?  node->lChild->height + 1: 0;
    int h_rChild = (node->rChild) ?  node->rChild->height + 1: 0;
 
    return h_rChild - h_lChild;
}
 
avlNode* getRoot(avlNode *node)
{
    if (node->parent)
        return getRoot(node->parent);
    else
        return node;
}
 
void avlTree_fixup (avlNode **node, int action)
{
    int bf = 0;
    int ht = -1;
    avlNode *father = NULL;
 
    if (*node == NULL)
        return;
    ht = getHeight(*node);
    (*node)->height = ht;
    bf = balanceFactor(*node);
    if (bf == 0 && action == 1) /*for the case of insertion - no change in height*/
        return;
    if (bf == 0 && action == 2) {/*for the case of deletion*/
        avlTree_fixup(&((*node)->parent), action);
        return;
    }
    if (bf == 1 || bf == -1) {/*=> that one node has been added to the right/left subtree, can disturb the balancing at the parent*/
        if (action == 1) {
            avlTree_fixup(&((*node)->parent), action);
            return;
        }
        else /*no change in height*/
            return;
    }
    if (bf == 2) {
        int bf_rChild = balanceFactor((*node)->rChild);
        if (bf_rChild == 1) {
            avlNode *tmp = (*node)->rChild;
            leftRotate(node);
            /*node is now by itself set to parent of node before
             * rotation*/
            if (action == 1)
                avlTree_fixup(node, action);
            else
                avlTree_fixup(&((*node)->parent), action);
            return;
        } else if (bf_rChild == -1) {
            rightRotate(&((*node)->rChild));
            (*node)->height = getHeight(*node);
            if (action == 1)
                leftRotate(&((*node)->parent));
            else
                leftRotate(node);
            avlTree_fixup(&((*node)->parent), action);
            return;
        } else if (bf_rChild == 0) {/*for the case of deletion*/
            leftRotate(node);
            avlTree_fixup(&((*node)->parent), action);
            return;
        }
    } else if (bf == -2) {
        int bf_lChild = balanceFactor((*node)->lChild);
        if (bf_lChild == -1) {
            rightRotate(node);
            /*node is now by itself set to parent of node before
             * rotation*/
            if (action == 1)
                avlTree_fixup(node, action);
            else
                avlTree_fixup(&((*node)->parent), action);
            return;
        } else if (bf_lChild == 1) {
            leftRotate(&((*node)->lChild));
            (*node)->height = getHeight(*node);
            if (action == 1)
                rightRotate(&((*node)->parent));
            else
                rightRotate(node);
            avlTree_fixup(&((*node)->parent), action);
            return;
        } else if (bf_lChild == 0) {/*for the case of deletion*/
            rightRotate(node);
            avlTree_fixup(&((*node)->parent), action);
            return;
        }
    }
}
 
/*cmp is the function pointer provided by the user
 * return codes of cmp expected by the insert function
 * key1 = key2 return 0
 * key1 < key2 return 1
 * key1 > key2 return 2
 * */
void add (avlNode **root, avlNodeData *val, int (*cmp)(void *key1, void *key2))
{
    avlNode *node = NULL;
    avlNode *tmp = NULL;
    int dir = 0;
 
    if (!(*root)) {
        *root = newAvlTree(val);
        (*root)->parent = NULL;
        //return *root;
        return;
    }
    if (cmp(val->key, (*root)->data->key) <= 1) {
        tmp = (*root)->lChild;
        dir = 1;
    } else {
        tmp = (*root)->rChild;
        dir = 2;
    }
    if (tmp == NULL) {
        tmp = allocAvlNode(val);
        tmp->parent = *root;
        if (dir == 1) {
            (*root)->lChild = tmp;
            avlTree_fixup(root, INSERT);
        } else {
            (*root)->rChild = tmp;
            avlTree_fixup(root, INSERT);
        }
    } else
        add(&tmp, val, cmp);
 
    //return ((*root)->parent) ? (*root)->parent : *root;
    return;
}
 
avlNode* insert (avlNode **root, avlNodeData *val, int (*cmp)(void *key1, void *key2))
{
    add(root, val, cmp);
    return getRoot(*root);
}
 
avlNode* search (avlNode *root, avlNodeData *val, int (*cmp)(void *key1, void *key2))
{
    if (root == NULL)
        return NULL;
    if (cmp(val->key, root->data->key) == 0)
        return root;
    else if (cmp(val->key, root->data->key) == 1)
        return search(root->lChild, val, cmp);
    else
        return search(root->rChild, val, cmp);
}
 
void replace (avlNode **src, avlNode **dest)
{
    avlNode *father = (*src)->parent;
 
    if (*dest != NULL)
        (*dest)->parent = (*src)->parent;
    if (father->lChild == *src)
        father->lChild = *dest;
    else
        father->rChild = *dest;
 
    return;
}
 
void removeNode (avlNode **node, void (*freeNodedata)(avlNodeData **data))
{
    avlNode *child = NULL;
    avlNode *father = NULL;
 
    father = (*node)->parent;
    if ((*node)->lChild != NULL)
        child = (*node)->lChild;
    else if ((*node)->rChild != NULL)
        child = (*node)->rChild;
    else
        child = NULL;
 
    replace(node, &child);
    avlTree_fixup(&((*node)->parent), DELETE);
    freeAvlNode(node, freeNodedata);
 
    return;
}
 
avlNode* largestInSubtree (avlNode *root)
{
    if (!(root->rChild))
        return root;
    return largestInSubtree(root->rChild);
}
 
avlNode* smallestInSubtree (avlNode *root)
{
    if (!(root->lChild))
        return root;
    return smallestInSubtree(root->lChild);
}
 
avlNode* deleteNode (avlNode **root, avlNodeData *val, int (*cmp)(void *key1, void *key2), void (*freeNodedata)(avlNodeData **data))
{
    avlNode *target = NULL;
    avlNode *toRemove = NULL;
 
    target = search(*root, val, cmp);
    if (!target)
         return;                //////////////////////////////////////////////////////////////////////////////////////////// 0 khodam gozashtam

    if (target->lChild != NULL)
        toRemove = largestInSubtree(target->lChild);
    else if (target->rChild != NULL)
        toRemove = smallestInSubtree(target->rChild);
    else
        toRemove = target;
    if (target != toRemove) {
        ++(toRemove->data->rc);
        target->data = toRemove->data;
    }
    removeNode(&toRemove, freeNodeData);
 
    return getRoot(*root);;
}
 

avlNode* locate (avlNode *root, avlNodeData *val, int (*cmp)(void *key1, void *key2))
{
    return search(root, val, cmp);
}
 
void inorder (avlNode *root, void (*display)(avlNodeData *nodeData))
{
    if (root == NULL)
        return;
 
    inorder(root->lChild, display);
    display(root->data);
    inorder(root->rChild, display);
    return;
}
 
void postorder (avlNode *root, void (*display)(avlNodeData *nodeData))
{
    if (root == NULL)
        return;
 
    postorder(root->lChild, display);
    postorder(root->rChild, display);
    display(root->data);
    return;
}
 
void preorder (avlNode *root, void (*display)(avlNodeData *nodeData))
{
    if (root == NULL)
        return;
 
    display(root->data);
    preorder(root->lChild, display);
    preorder(root->rChild, display);
    return;
}
Posted 27-Jan-13 8:47am
Edited 27-Jan-13 9:28am
v2
Comments
jibesh at 27-Jan-13 14:18pm
   
You havent told about your problem? do you think someone could run the whole code dump to identify the problem for you. no I doubt that. please tell what's the problem you are facing so that it will help others to look around the code where the actual problem exists than going through all these code.
 
You can use the Improve Question link to update your question.
mahla.r_1993 at 27-Jan-13 14:23pm
   
i have an error in ( avlNode* deleteNode )
in this part ,
error C2561: 'deleteNode' : function must return a value
 
what must i do?
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

Each function that claims to return a value must return a value.
Your function claims to return a pointer to avlNode, but your code simply says ... return;....
That return statement must return some value, but you don't give any.
 
Invent one that makes sense at that point (maybe 0 or NULL?) and return that value (e.g. return 0; or return NULL; or something else that fits your designed logic of that function).
 
Cheers
Andi
  Permalink  
Comments
mahla.r_1993 at 27-Jan-13 14:35pm
   
i write return null
and after that i get these error :
 
error LNK1120: 1 unresolved externals
 
error LNK2019: unresolved external symbol "void __cdecl freeNodeData(struct avl_nodeData * *)" (?freeNodeData@@YAXPAPAUavl_nodeData@@@Z) referenced in function "struct avl_node * __cdecl deleteNode(struct avl_node * *,struct avl_nodeData *,int (__cdecl*)(void *,void *),void (__cdecl*)(struct avl_nodeData * *))" (?deleteNode@@YAPAUavl_node@@PAPAU1@PAUavl_nodeData@@P6AHPAX2@ZP6AXPAPAU2@@Z@Z)
 
what is wrong?
Andreas Gieriet at 27-Jan-13 14:45pm
   
You struggle from one problem to the other, that's the problem.
1) I assume NULL, not null.
2) you did not give the needed libraries to the linker to link your used externals.
Please refer to your compiler documentation on how to tell what libraries (or object files) to link too (assuming you know in which libraries/object files define the avl... types).
Andi
mahla.r_1993 at 27-Jan-13 15:24pm
   
i dont understand what i must do:(
Andreas Gieriet at 27-Jan-13 15:31pm
   
How do you call the compiler? There is some file missing for the linker.
Show the compiler call. If you do not understand this question: in what IDE and environment do you work?
Or maybe, the call to freeNodeData is the wrong name or not passing the right type/number of arguments, or ...?
Andi
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

I agree with solution #1 (but Andreas didn't identify the API with the problem). avlNode* deleteNode(...) needs to return a value on the 5th line just before the "////" comment. Instead of "return;" you need "return 'something';" to make the compiler happy.
 
As for the linker errors, you likely have something different between the .h and .cpp files. This could be due to an obvious difference, or an undefined symbol or misdefined symbol that changes link options (ie. __cdecl, __declspec(dllexport), ...). If you have multiple execution units (.exe, dll(s)) my bet is on a missing dllexport spec.
  Permalink  
v2
Comments
mahla.r_1993 at 27-Jan-13 17:46pm
   
tnx but now , what can i do ?
H.Brydon at 27-Jan-13 19:33pm
   
Looking at the info in your replies to solution #1, there is a linker problem with "void __cdecl freeNodeData(struct avl_nodeData * *)". You have a header for this in your code above but you haven't provided an implementation. What does the function look like?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 400
1 Sergey Alexandrovich Kryukov 329
2 Afzaal Ahmad Zeeshan 264
3 BillWoodruff 245
4 CPallini 195
0 OriginalGriff 5,560
1 DamithSL 4,476
2 Maciej Los 3,942
3 Kornfeld Eliyahu Peter 3,480
4 Sergey Alexandrovich Kryukov 3,175


Advertise | Privacy | Mobile
Web03 | 2.8.141216.1 | Last Updated 27 Jan 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100