Program crashes when inserting more numbers into BR Tree

[crowstorm]

So everything seemed to work fine until I wanted to generate bigger trees with random numbers.

When dealing with numbers from 0 do rand(), the program crashes at bigger arrays (id say 200 is likely to crash, 1000 always crashes) while random numbers from 0 to 9 work most of the time with array of 10, but crashes always at 50 and less.

There is probably something wrong with insertion but I cant figure this out. Would be grateful for help

#include <bits/stdc++.h>

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

enum Color {RED, BLACK};

struct Node
{
    int data;
    bool color;
    Node *left, *right, *parent;

    // Constructor
    Node(int data)
    {
       this->data = data;
       left = right = parent = NULL;
    }
};

// Class to represent Red-Black Tree
class RBTree
{
private:
    Node *root;
protected:
    void rotateLeft(Node *&, Node *&);
    void rotateRight(Node *&, Node *&);
    void fixViolation(Node *&, Node *&);
public:
    // Constructor
    RBTree() { root = NULL; }
    void insert(const int &n);
    void inorder();
    void levelOrder();
   // int heightHelper(Node * n);
   // int max(int x, int y);
    int height();
};

// A recursive function to do level order traversal
void inorderHelper(Node *root)
{
    if (root == NULL)
        return;

    inorderHelper(root->left);
    cout << root->data << "  ";
    inorderHelper(root->right);
}

/* A utility function to insert a new node with given key
   in BST */
Node* BSTInsert(Node* root, Node *pt)
{
    /* If the tree is empty, return a new node */
    if (root == NULL)
       return pt;

    /* Otherwise, recur down the tree */
    if (pt->data < root->data)
    {
        root->left  = BSTInsert(root->left, pt);
        root->left->parent = root;
    }
    else if (pt->data > root->data)
    {
        root->right = BSTInsert(root->right, pt);
        root->right->parent = root;
    }

    /* return the (unchanged) node pointer */
    return root;
}

// Utility function to do level order traversal
void levelOrderHelper(Node *root)
{
    if (root == NULL)
        return;

    std::queue<Node *> q;
    q.push(root);

    while (!q.empty())
    {
        Node *temp = q.front();
        cout << temp->data << "  ";
        q.pop();

        if (temp->left != NULL)
            q.push(temp->left);

        if (temp->right != NULL)
            q.push(temp->right);
    }
}

void RBTree::rotateLeft(Node *&root, Node *&pt)
{
    Node *pt_right = pt->right;

    pt->right = pt_right->left;

    if (pt->right != NULL)
        pt->right->parent = pt;

    pt_right->parent = pt->parent;

    if (pt->parent == NULL)
        root = pt_right;

    else if (pt == pt->parent->left)
        pt->parent->left = pt_right;

    else
        pt->parent->right = pt_right;

    pt_right->left = pt;
    pt->parent = pt_right;
}

void RBTree::rotateRight(Node *&root, Node *&pt)
{
    Node *pt_left = pt->left;

    pt->left = pt_left->right;

    if (pt->left != NULL)
        pt->left->parent = pt;

    pt_left->parent = pt->parent;

    if (pt->parent == NULL)
        root = pt_left;

    else if (pt == pt->parent->left)
        pt->parent->left = pt_left;

    else
        pt->parent->right = pt_left;

    pt_left->right = pt;
    pt->parent = pt_left;
}

// This function fixes violations caused by BST insertion
void RBTree::fixViolation(Node *&root, Node *&pt)
{
    Node *parent_pt = NULL;
    Node *grand_parent_pt = NULL;

    while ((pt != root) && (pt->color != BLACK) &&
           (pt->parent->color == RED))
    {

        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;

        /*  Case : A
            Parent of pt is left child of Grand-parent of pt */
        if (parent_pt == grand_parent_pt->left)
        {

            Node *uncle_pt = grand_parent_pt->right;

            /* Case : 1
               The uncle of pt is also red
               Only Recoloring required */
            if (uncle_pt != NULL && uncle_pt->color == RED)
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }

            else
            {
                /* Case : 2
                   pt is right child of its parent
                   Left-rotation required */
                if (pt == parent_pt->right)
                {
                    rotateLeft(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                /* Case : 3
                   pt is left child of its parent
                   Right-rotation required */
                rotateRight(root, grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }

        /* Case : B
           Parent of pt is right child of Grand-parent of pt */
        else
        {
            Node *uncle_pt = grand_parent_pt->left;

            /*  Case : 1
                The uncle of pt is also red
                Only Recoloring required */
            if ((uncle_pt != NULL) && (uncle_pt->color == RED))
            {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            }
            else
            {
                /* Case : 2
                   pt is left child of its parent
                   Right-rotation required */
                if (pt == parent_pt->left)
                {
                    rotateRight(root, parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                /* Case : 3
                   pt is right child of its parent
                   Left-rotation required */
                rotateLeft(root, grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }

    root->color = BLACK;
}

// Function to insert a new node with given data
void RBTree::insert(const int &data)
{
    Node *pt = new Node(data);

    // Do a normal BST insert
    root = BSTInsert(root, pt);

    // fix Red Black Tree violations
    fixViolation(root, pt);
}

int heightHelper(Node * n){
        if ( n == NULL ){
            return -1;
        }
        else{
            return max(heightHelper(n->left), heightHelper(n->right)) + 1;
        }
    }

int max(int x, int y){
    if (x >= y){
        return x;
    }
    else{
        return y;
    }
}

// Function to do inorder and level order traversals
void RBTree::inorder()     {  inorderHelper(root);}
void RBTree::levelOrder()  {  levelOrderHelper(root); }
int RBTree::height() { heightHelper(root);}

// Driver Code
int main()
{

    srand ( time(0) );
    RBTree tree;
    RBTree tree2;


    int n = 100;

    int tab[n];

    for(int i = 0; i < n; i++){
        tab[i] = rand();
    }

    tree.insert(tab[0]);

    for(int i = 1; i < n; i++){
        tree.insert(tab[i]);
    }

    //second tree

    int m = 50;

    int tab2[m];

    for(int i = 0; i < m; i++){
        tab2[i] = rand()%10;
        cout << tab2[i] << endl;
        tree2.insert(tab2[i]);
    }

       tree2.insert(tab2[0]);

    for(int i = 1; i < m; i++){
        tree.insert(tab2[i]);
    }


    cout << endl;


    return 0;
}

[ne555]

$ gdb a.out
(gdb) run
6
0
1
1

Program received signal SIGSEGV, Segmentation fault.
0x000055555555abdc in RBTree::fixViolation (this=0x7fffffffe100, root=@0x7fffffffe100: 0x55555577aee0, 
    pt=@0x7fffffffdfd0: 0x55555577af10)
		while((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) {
(gdb) print *pt
$1 = {
  data = 1, 
  color = false, 
  left = 0x0, 
  right = 0x0, 
  parent = 0x0
}

notice that pt has no parent set.
looking at `.BSTInsert()', you don't handle duplicates

Node *BSTInsert(Node *root, Node *pt) {
	/* If the tree is empty, return a new node */
	if(root == NULL)
		return pt;

	/* Otherwise, recur down the tree */
	if(pt->data < root->data) {
		root->left = BSTInsert(root->left, pt);
		root->left->parent = root;
	} else if(pt->data > root->data) {
		root->right = BSTInsert(root->right, pt);
		root->right->parent = root;
	}
	//else pt->data == root->data, pt->parent not set

	/* return the (unchanged) node pointer */
	return root;
}

[dhayden]

Node's constructor needs to set the color.

[crowstorm]

And youre right, I overlooked the duplicates... When I was implementing AVL tree i didnt handle duplicates on purpose because they could eventually violate the AVL tree when parent and left + right are the same number. Somehow I thought that would be the same case, but no, RB tree has other rules, and thats the colors that matter, and those can be swapped. thank you