Thread: Problem with balance red-black tree.

Good evening. I have some problem with balance of red-black tree.
In this code the first written-down value is appropriated to the value: root. And it doesn't participate in balancing.
Can you help me to insert node-"root" in function "insertion"(55 line) and "deletion"(178 line), which balance this tree. Thanks.

Code:

class RBTree
{
private:
    struct rbNode 
    {
        rbNode(int data);
        int data, color;
        struct rbNode *link[2];
    };
    rbNode *root;
    int depth;

public:
    enum nodeColor 
    {
        RED,
        BLACK
    };        

    RBTree();
    void insertion (int data);
    void deletion(int data);
    void searchElement(int data);
    void inorderTraversal();
    
    void Get(struct rbNode *node)
    {
        if (node)
        {
        Get(node->link[0]);
        printf("%d ", node->data);
        Get(node->link[1]);
        }
    }
};

RBTree::rbNode::rbNode( int _data )
{
    data = _data;
    color = RED;
    link[0] = link[1] = NULL;
}

RBTree::RBTree()
{ 
    root = NULL;
    depth = NULL;
}

void RBTree::insertion ( int data )
{
    struct rbNode *ptr, *newnode, *xPtr, *yPtr;
    int ht = 0, index;
    struct rbNode** stack; 
    stack = new rbNode*[depth];
    int* dir;
    dir = new int [depth];
    ptr = root; 
    if (!root)
    {
        root = new rbNode(data);
        depth = 1;
        return;
    }
    

    while (ptr != NULL)
    {
        if (ptr->data == data) 
        {
            printf("This data was insert earlier! \n");
            return;
        }
        index = (data - ptr->data) > 0 ? 1 : 0;        
        stack[ht] = ptr;
        ptr = ptr->link[index];
        dir[ht++] = index; 
    }

    stack[ht - 1]->link[index] = newnode = new rbNode(data);

    if ((ht + 1) > depth)
    {
        depth = ht + 1;
    }

    while ((ht >= 3) && (stack[ht - 1]->color == RED))
    {
        if (dir[ht - 2] == 0) 
        {
            yPtr = stack[ht - 2]->link[1];
            if (yPtr != NULL && yPtr->color == RED)
            {
                stack[ht - 2]->color = RED;
                stack[ht - 1]->color = yPtr->color = BLACK;
                ht = ht - 2;
            } 
            else 
            {
                if (dir[ht - 1] == 0) 
                {
                    yPtr = stack[ht - 1];
                } 
                else 

                {
                    xPtr = stack[ht - 1];
                    yPtr = xPtr->link[1];
                    xPtr->link[1] = yPtr->link[0];
                    yPtr->link[0] = xPtr;
                    stack[ht - 2]->link[0] = yPtr;
                }
                xPtr = stack[ht - 2];
                xPtr->color = RED;
                yPtr->color = BLACK;
                xPtr->link[0] = yPtr->link[1];
                yPtr->link[1] = xPtr;
                if (xPtr == root)
                {
                    root = yPtr;
                } 
                else 
                {
                    stack[ht - 3]->link[dir[ht - 3]] = yPtr;
                }
                break;
            }
        } 
        else 
        {
            yPtr = stack[ht - 2]->link[0];
            if ((yPtr != NULL) && (yPtr->color == RED)) 
            {
                stack[ht - 2]->color = RED;
                stack[ht - 1]->color = yPtr->color = BLACK;
                ht = ht - 2;
            } else 
            {
                if (dir[ht - 1] == 1) 
                {
                    yPtr = stack[ht - 1];
                } 
                else 
                {
                    xPtr = stack[ht - 1];
                    yPtr = xPtr->link[0];
                    xPtr->link[0] = yPtr->link[1];
                    yPtr->link[1] = xPtr;
                    stack[ht - 2]->link[1] = yPtr;
                }
                xPtr = stack[ht - 2];
                yPtr->color = BLACK;
                xPtr->color = RED;
                xPtr->link[1] = yPtr->link[0];
                yPtr->link[0] = xPtr;
                if (xPtr == root) 
                {
                    root = yPtr;
                } 
                else 
                {
                    stack[ht - 3]->link[dir[ht - 3]] = yPtr;
                }
                break;
            }
        }
    }
    delete []dir;
    delete []stack;
    root->color = BLACK;
}

void RBTree::deletion( int data )
{
    struct rbNode *ptr, *xPtr, *yPtr;
    struct rbNode *pPtr, *qPtr, *rPtr;
    int ht = 0, diff, i;
    struct rbNode** stack; 
    stack = new rbNode*[depth + 1];
    int* dir;
    dir = new int [depth + 1];

    enum nodeColor color;

    if (!root)
    {
        printf("Tree not available\n");
        return;
    }
    ptr = root;

    while (ptr != NULL)
    {
        if ((data - ptr->data) == 0)
            break;
        diff = (data - ptr->data) > 0 ? 1 : 0;
        stack[ht] = ptr;
        dir[ht++] = diff;
        ptr = ptr->link[diff];
    }

    if (ptr->link[1] == NULL)
    {
        if ((ptr == root) && (ptr->link[0] == NULL)) 
        {
            free(ptr);
            root = NULL;
        } 
        else 
            if (ptr == root) 
        {
            root = ptr->link[0];
            free(ptr);
        } 
        else 
        {
            stack[ht - 1]->link[dir[ht - 1]] = ptr->link[0];
        }
    } 
    else 
    {
        xPtr = ptr->link[1];
        if (xPtr->link[0] == NULL) 
        {
            xPtr->link[0] = ptr->link[0];
            color = (xPtr->color == 0) ? RED:BLACK;
            xPtr->color = ptr->color;
            ptr->color = color;

            if (ptr == root) 
            {
                root = xPtr;
            } 
            else 
            {
                stack[ht - 1]->link[dir[ht - 1]] = xPtr;
            }

            dir[ht] = 1;
            stack[ht++] = xPtr;
        } 
        else 
        {
            i = ht++;
            while (1) 
            {
                dir[ht] = 0;
                stack[ht++] = xPtr;
                yPtr = xPtr->link[0];
                if (!yPtr->link[0])
                    break;
                xPtr = yPtr;
            }

            dir[i] = 1;
            stack[i] = yPtr;
            if (i > 0)
                stack[i - 1]->link[dir[i - 1]] = yPtr;

            yPtr->link[0] = ptr->link[0];
            xPtr->link[0] = yPtr->link[1];
            yPtr->link[1] = ptr->link[1];

            if (ptr == root) 
            {
                root = yPtr;
            }

            color = (yPtr->color==0) ? RED:BLACK;
            yPtr->color = ptr->color;
            ptr->color = color;
        }
    }
    if (ht < 1)
        return;
    if (ptr->color == BLACK) 
    {
        while (1) 
        {
            pPtr = stack[ht - 1]->link[dir[ht - 1]];
            if (pPtr && pPtr->color == RED) 
            {
                pPtr->color = BLACK;
                break;
            }

            if (ht < 2)
                break;

            if (dir[ht - 2] == 0) 
            {
                rPtr = stack[ht - 1]->link[1];

                if (!rPtr)
                    break;

                if (rPtr->color == RED)
                {
                    stack[ht - 1]->color = RED;
                    rPtr->color = BLACK;
                    stack[ht - 1]->link[1] = rPtr->link[0];
                    rPtr->link[0] = stack[ht - 1];

                    if (stack[ht - 1] == root) 
                    {
                        root = rPtr;
                    } 
                    else 
                    {
                        stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                    }
                    dir[ht] = 0;
                    stack[ht] = stack[ht - 1];
                    stack[ht - 1] = rPtr;
                    ht++;

                    rPtr = stack[ht - 1]->link[1];
                }

                if ( (!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) 
                {
                    rPtr->color = RED;
                } 
                else 
                {
                    if (!rPtr->link[1] || rPtr->link[1]->color == BLACK) 
                    {
                        qPtr = rPtr->link[0];
                        rPtr->color = RED;
                        qPtr->color = BLACK;
                        rPtr->link[0] = qPtr->link[1];
                        qPtr->link[1] = rPtr;
                        rPtr = stack[ht - 1]->link[1] = qPtr;
                    }
                    rPtr->color = stack[ht - 1]->color;
                    stack[ht - 1]->color = BLACK;
                    rPtr->link[1]->color = BLACK;
                    stack[ht - 1]->link[1] = rPtr->link[0];
                    rPtr->link[0] = stack[ht - 1];
                    if (stack[ht - 1] == root) 
                    {
                        root = rPtr;
                    } 
                    else 
                    {
                        stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                    }
                    break;
                }
            } 
            else 
            {
                rPtr = stack[ht - 1]->link[0];
                if (!rPtr)
                    break;

                if (rPtr->color == RED) 
                {
                    stack[ht - 1]->color = RED;
                    rPtr->color = BLACK;
                    stack[ht - 1]->link[0] = rPtr->link[1];
                    rPtr->link[1] = stack[ht - 1];

                    if (stack[ht - 1] == root) 
                    {
                        root = rPtr;
                    } 
                    else 
                    {
                        stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                    }
                    dir[ht] = 1;
                    stack[ht] = stack[ht - 1];
                    stack[ht - 1] = rPtr;
                    ht++;

                    rPtr = stack[ht - 1]->link[0];
                }
                if ( (!rPtr->link[0] || rPtr->link[0]->color == BLACK) && (!rPtr->link[1] || rPtr->link[1]->color == BLACK)) 
                {
                    rPtr->color = RED;
                } 
                else 
                {
                    if (!rPtr->link[0] || rPtr->link[0]->color == BLACK) 
                    {
                        qPtr = rPtr->link[1];
                        rPtr->color = RED;
                        qPtr->color = BLACK;
                        rPtr->link[1] = qPtr->link[0];
                        qPtr->link[0] = rPtr;
                        rPtr = stack[ht - 1]->link[0] = qPtr;
                    }
                    rPtr->color = stack[ht - 1]->color;
                    stack[ht - 1]->color = BLACK;
                    rPtr->link[0]->color = BLACK;
                    stack[ht - 1]->link[0] = rPtr->link[1];
                    rPtr->link[1] = stack[ht - 1];
                    if (stack[ht - 1] == root) 
                    {
                        root = rPtr;
                    } 
                    else 
                    {
                        stack[ht - 2]->link[dir[ht - 2]] = rPtr;
                    }
                    break;
                }
            }
            ht--;
        }
    }
    delete[]stack;
    delete[]dir;
}

void RBTree::searchElement( int data ) 
{
    struct rbNode *temp = root;
    int diff;

    while (temp != NULL) 
    {
        diff = data - temp->data;
        if (diff > 0) 
        {
            temp = temp->link[1];
        } 
        else 
            if (diff < 0) 
            {
                temp = temp->link[0];
            } 
            else 
            {
                printf("Search Element Found!!\n");
                return;
            }
    }
    printf("Given Data Not Found in RB Tree!!\n");
    return;
}

void RBTree::inorderTraversal()
{
    Get(root);
    return;
}

int main() 
{
    int ch, data, time = clock();
    RBTree tree;
    while (1) 
    {
        printf("Time is: %d\n", time);
        printf("1. Insertion\t2. Deletion\n");
        printf("3. Searching\t4. Traverse\n");
        printf("5. Exit\nEnter your choice:");
        scanf("%d", &ch);
        switch (ch) 
        {
        case 1:
            printf("Enter the data to insert:");
            scanf("%d", &data);
            tree.insertion(data);
            break;
        case 2:
            printf("Enter the data to delete:");
            scanf("%d", &data);
            tree.deletion(data);
            break;
        case 3:
            printf("Enter the search element:");
            scanf("%d", &data);
            tree.searchElement(data);
            break;
        case 4:
            tree.inorderTraversal();
            printf("\n");
            break;
        case 5:
            exit(0);
        default:
            printf("You have entered wrong option!!\n");
            break;
        }
        printf("\n");
    }
    return 0;
}

You are leaking memory:

Code:

stack = new rbNode*[depth + 1];
int* dir;
dir = new int [depth + 1];
 
if (!root)
{
    printf("Tree not available\n");
    return;
}

Free allocated memory before exiting the function, or check the if condition first which is even simpler.