Delete large number of nodes from RedBlack Tree Causes Infinite Loop

Question

I have been working on a RedBlack Tree implementation in C (Red Black Tree Node Insertion Overwrites Previously Added Node) and have run into an issue where after a large number of deletions (~1000+ to ~2000+), it gets stuck in an infinite loop.

RB delete code:

typedef struct TreeNode TreeNode;
struct TreeNode {
  TreeNode *parent;
  TreeNode *child[2];
  COLOR color;
  U64 blockSize; // 'key'
  void *data;
};

typedef struct Tree Tree;
struct Tree {
  TreeNode *root;
  TreeNode *nil; 
};

... 
void transplant(Tree *tree, TreeNode *u, TreeNode *v) {
  if (u->parent == tree->nil) {
    tree->root = v;
  } else if (u == u->parent->left) {
    u->parent->left = v;
  } else {
    u->parent->right = v;
  }
  
  v->parent = u->parent;
}

void delete_fix(Tree *tree, TreeNode *x) {
  TreeNode *w = tree->nil;
  while (x != tree->root && x->color == BLACK) {
    if (x == x->parent->left) {
      w = x->parent->right;
      
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        left_rotate(tree, x->parent);
        w = x->parent->right;
      }
      
      if (w->left->color == BLACK && w->right->color == BLACK) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->right->color == BLACK) {
          w->left->color = BLACK;
          w->color = BLACK;
          right_rotate(tree, w);
          w = x->parent->right;
        }
        
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->right->color = BLACK;
        left_rotate(tree, x->parent);
        
        x = tree->root;
      }
    } else {
      w = x->parent->left;
      
      if (w->color == RED) {
        w->color = BLACK;
        x->parent->color = RED;
        right_rotate(tree, x->parent);
        w = x->parent->left;
      }
      
      if (w->right->color == BLACK && w->left->color == BLACK) {
        w->color = RED;
        x = x->parent;
      } else {
        if (w->left->color == BLACK) {
          w->right->color = BLACK;
          w->color = BLACK;
          left_rotate(tree, w);
          w = x->parent->left;
        }
        
        w->color = x->parent->color;
        x->parent->color = BLACK;
        w->left->color = BLACK;
        right_rotate(tree, x->parent);
        
        x = tree->root;
      }
    }
  }
  
  x->color = BLACK;
}

void delete_node(Tree *tree, TreeNode *z) {
  if (tree != NIL && z != tree->nil && z != tree->nil) {
    TreeNode *x = tree->nil, *y = z;
    COLOR yOgColor = y->color;
    
    if (z->left == tree->nil) {
      x = z->right;
      transplant(tree, z, z->right);
    } else if (z->right == tree->nil) {
      x = z->left;
      transplant(tree, z, z->left);
    } else {
      y = minimum(tree, z->right);
      yOgColor = y->color;
      x = y->right;
      if (y->parent == z) {
        x->parent = y;
      } else {
        transplant(tree, y, y->right);
        y->right = z->right;
        y->right->parent = y;
      }
      
      transplant(tree, z, y);
      y->left = z->left;
      y->left->parent = y;
      y->color = z->color;
    }
    if (yOgColor == BLACK) {
      delete_fix(tree, x);
    }
  }
}

TreeNode *minimum(Tree *t, TreeNode *x) {
  while (x->left != t->nil) {
    x = x->left;
  }
  
  return (x);
}

I have narrowed down where it hits an infinite loop, but the main culprit must be in the rest of the delete_node implmentation:

TreeNode *minimum(Tree *t, TreeNode *x) {
  while (x->left != t->nil) {
    x = x->left;
  }
  
  return (x);
}

Driver Code

U64 myrandom(U64 range) {
  U64 num;
  num = rand() % range;
  return num;
}

void print_inorder(FILE *file, Tree *t, TreeNode *n) {
  if (n != t->nil) {
    print_inorder(file, t, n->left);
    fprintf(file, "%llu \n", n->blockSize);
    print_inorder(file, t, n->right);
  }
}

int main(void) {
  
  srand(time(NULL));
  
  printf("Hello Tree\n");
  Tree tree = {0};
  TreeNode nil = {0};
  
  nil.parent = NIL;
  nil.left = &nil;
  nil.right = &nil;
  nil.color = BLACK;
  nil.blockSize = 0;
  
  tree.nil = tree.root = &nil;
  Tree *ptr = &tree;
  
  LARGE_INTEGER frequency;
  LARGE_INTEGER start;
  LARGE_INTEGER end;
  double interval;
  
  QueryPerformanceFrequency(&frequency);
  QueryPerformanceCounter(&start);
  
  
  TreeNode nodes[20000];
  
  for (int i = 0; i < 20000; i++) {
    TreeNode n = {0};
    n.parent = NIL;
    n.left = NIL;
    n.right = NIL;
    n.color = BLACK;
    n.blockSize = myrandom(UINT_FAST64_MAX);
    
    nodes[i] = n;
  }
  
  QueryPerformanceCounter(&start);
  for (int i = 0; i < 20000; i++) {
    insert_node(ptr, &nodes[i]);
  }
  QueryPerformanceCounter(&end);
  interval = (double) (end.QuadPart - start.QuadPart) / frequency.QuadPart;
  FILE *preDelFilePtr = fopen("rb_test_pre_delete.txt", "wb");
  fprintf(preDelFilePtr, "************************\n");
  fprintf(preDelFilePtr, "*      pre delete      *\n");
  fprintf(preDelFilePtr, "************************\n");
  fprintf(preDelFilePtr, "* time spent: %f *\n", interval);
  fprintf(preDelFilePtr, "************************\n");
  print_inorder(preDelFilePtr, ptr, ptr->root);
  
  
  frequency.QuadPart = 0;
  start.QuadPart = 0;
  end.QuadPart = 0;
  interval = 0;
  QueryPerformanceCounter(&start);
  for (int i = 0; i <= 10000; i++) {
    U64 removeIndex = myrandom(20000); 
    if (&nodes[removeIndex] != ptr->nil)
    {
      delete_node(ptr, &nodes[removeIndex]);
    }
  }
  QueryPerformanceCounter(&end);
  interval = (double) (end.QuadPart - start.QuadPart) / frequency.QuadPart;
  FILE *postDelFilePtr = fopen("rb_test_post_delete.txt", "wb");
  fprintf(postDelFilePtr, "************************\n");
  fprintf(postDelFilePtr, "*     post delete      *\n");
  fprintf(postDelFilePtr, "************************\n");
  fprintf(postDelFilePtr, "* time spent: %f *\n", interval);
  fprintf(postDelFilePtr, "************************\n");
  print_inorder(postDelFilePtr, ptr, ptr->root);
  
  fclose(preDelFilePtr);
  fclose(postDelFilePtr);
  
  return 0;
}

So far, I have tried adding some checks at the beginning of the minimum function as well, but that didn't solve the issue either.

Any help or comments would be appreciated!

UPDATE:

Below is the updated full source which now uses NULL instead of tree->nil to represent a leaf node.

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>


#include "rb.h"


U64 myrandom(U64 range) {
  U64 num;
  num = rand() % range;
  return num;
}

void print_inorder(FILE *file, Tree *t, TreeNode *n) {
  if (n != NULL) {
    print_inorder(file, t, n->left);
    fprintf(file, "%llu \n", n->blockSize);
    print_inorder(file, t, n->right);
  }
}

int main(void) {
  
  srand(time(NULL));
  
  printf("Hello Tree\n");
  Tree tree = {0};
  Tree *ptr = &tree;
  

  TreeNode nodes[20000];
  
  for (int i = 0; i < 20000; i++) {
    TreeNode n = {0};
    n.parent = NULL;
    n.left = NULL;
    n.right = NULL;
    n.color = BLACK;
    n.blockSize = myrandom(UINT_FAST64_MAX);
    
    nodes[i] = n;
  }
  
 
  FILE *preDelFilePtr = fopen("rb_test_pre_delete.txt", "wb");
  fprintf(preDelFilePtr, "************************\n");
  fprintf(preDelFilePtr, "*      pre delete      *\n");
  print_inorder(preDelFilePtr, ptr, ptr->root);
  
  
  FILE *postDelFilePtr = fopen("rb_test_post_delete.txt", "wb");
  fprintf(postDelFilePtr, "************************\n");
  fprintf(postDelFilePtr, "*     post delete      *\n");
  print_inorder(postDelFilePtr, ptr, ptr->root);
  
  fclose(preDelFilePtr);
  fclose(postDelFilePtr);
  
  return 0;
}

rb.h

#ifndef RB_H
#define RB_H


#include <inttypes.h>

typedef enum COLOR { BLACK, RED } COLOR;

#ifndef U64_TYPE
#define U64_TYPE
typedef uint_fast64_t U64;
#endif

typedef struct TreeNode TreeNode;
struct TreeNode {
  TreeNode *parent;
  TreeNode *child[2];
  COLOR color;
  U64 blockSize; // 'key'
  void *data;
};

typedef struct Tree Tree;
struct Tree {
  TreeNode *root;
};

#define LEFT 0
#define RIGHT 1
#define left child[LEFT]
#define right child[RIGHT]

void left_rotate(Tree *tree, TreeNode *node);
void right_rotate(Tree *tree, TreeNode *node);
void insert_fix(Tree *tree, TreeNode *node);
void insert_node(Tree *tree, TreeNode *toInsert);
void transplant(Tree *tree, TreeNode *n1, TreeNode *n2);
void delete_fix(Tree *tree, TreeNode *node);
void delete_node(Tree *tree, TreeNode *node);
TreeNode *maximum(TreeNode *node);
TreeNode *minimum(TreeNode *node);

void left_rotate(Tree *tree, TreeNode *node) {
  if (tree != NULL && node != NULL) {
    TreeNode *rightChild = node->right;
    node->right = rightChild->left;
    
    if (rightChild->left != NULL) {
      rightChild->left->parent = node;
    }
    
    rightChild->parent = node->parent;
    
    if (node->parent == NULL) {
      tree->root = rightChild;
    } else if (node == node->parent->left) {
      node->parent->left = rightChild;
    } else {
      node->parent->right = rightChild;
    }
    
    rightChild->left = node;
    
    node->parent = rightChild;
  }
}

void right_rotate(Tree *tree, TreeNode *node) {
  if (tree != NULL && node != NULL) {
    TreeNode *leftChild = node->left;
    node->left = leftChild->right;
    
    if (leftChild->right != NULL) {
      leftChild->right->parent = node;
    }
    
    leftChild->parent = node->parent;
    
    if (node->parent == NULL) {
      tree->root = leftChild;
    } else if (node == node->parent->right) {
      node->parent->right = leftChild;
    } else {
      node->parent->left = leftChild;
    }
    
    leftChild->right = node;
    
    node->parent = leftChild;
  }
}

void insert_fix(Tree *tree, TreeNode *z) {
  // iterate until z is not the root and z's parent color is red
  if (z->parent != NULL)
  {
    while (z != tree->root && z->parent != NULL && z->parent->color == RED) {
      if (z->parent->parent != NULL)
      {
        if (z->parent == z->parent->parent->left &&
            z->parent->parent->right != NULL) {
          TreeNode *y = z->parent->parent->right;
          {
            if (y->color == RED) {
              z->parent->color = BLACK;
              y->color = BLACK;
              z->parent->parent->color = RED;
              z = z->parent->parent;
            } else {
              if (z == z->parent->right) {
                z = z->parent;
                left_rotate(tree, z);
              }
              z->parent->color = BLACK;
              z->parent->color = RED;
              right_rotate(tree, z->parent->parent);
            }
          }
        } else if (z->parent == z->parent->parent->right &&
                   z->parent->parent->left != NULL) {
          TreeNode *y = z->parent->parent->left;
          if (y->color == RED) {
            z->parent->color = BLACK;
            y->color = BLACK;
            z->parent->parent->color = RED;
            z = z->parent->parent;
          } else {
            if (z == z->parent->left) {
              z = z->parent;
              right_rotate(tree, z);
            }
            z->parent->color = BLACK;
            z->parent->color = RED;
            left_rotate(tree, z->parent->parent);
          }
        } else {
          break;
        }
      } else {
        break;
      }
    }
    tree->root->color = BLACK;
  }// keep root always black
}

void insert_node(Tree *tree, TreeNode *z) {
  if (tree != NULL) {
    TreeNode *y = NULL;
    TreeNode *x = tree->root;
    
    while (x != NULL) {
      y = x;
      
      if (z->blockSize < x->blockSize) {
        x = x->left;
      } else {
        x = x->right;
      }
    }
    
    z->parent = y;
    
    if (y == NULL) {
      tree->root = z;
    } else if (z->blockSize < y->blockSize) {
      y->left = z;
    } else {
      y->right = z;
    }
    
    z->left = NULL;
    z->right = NULL;
    z->color = RED;
    insert_fix(tree, z);
  }
}

void transplant(Tree *tree, TreeNode *u, TreeNode *v) {
  if (v != NULL)
  {
    if (u->parent == NULL) {
      tree->root = v;
    } else if (u == u->parent->left) {
      u->parent->left = v;
    } else {
      u->parent->right = v;
    }
    
    v->parent = u->parent;
  }
}

void delete_fix(Tree *tree, TreeNode *x) {
  TreeNode *w = NULL;
  if (x != NULL)
  {
    while (x != tree->root && x->color == BLACK) {
      if (x->parent != NULL)
      {
        if (x == x->parent->left) {
          w = x->parent->right;
          
          if (w->color == RED) {
            w->color = BLACK;
            x->parent->color = RED;
            left_rotate(tree, x->parent);
            w = x->parent->right;
          }
          
          if (w->left != NULL && w->right != NULL)
          {
            if (w->left->color == BLACK && w->right->color == BLACK) {
              w->color = RED;
              x = x->parent;
            } else {
              if (w->right != NULL)
              {
                if (w->right->color == BLACK) {
                  w->left->color = BLACK;
                  w->color = BLACK;
                  right_rotate(tree, w);
                  w = x->parent->right;
                }
              }
              w->color = x->parent->color;
              x->parent->color = BLACK;
              w->right->color = BLACK;
              left_rotate(tree, x->parent);
              
              x = tree->root;
            }
          }
        } else {
          w = x->parent->left;
          
          if (w->color == RED) {
            w->color = BLACK;
            x->parent->color = RED;
            right_rotate(tree, x->parent);
            w = x->parent->left;
          }
          
          if (w->left != NULL && w->right != NULL)
          {
            if (w->right->color == BLACK && w->left->color == BLACK) {
              w->color = RED;
              x = x->parent;
            } else {
              if (w->left->color == BLACK) {
                w->right->color = BLACK;
                w->color = BLACK;
                left_rotate(tree, w);
                w = x->parent->left;
              }
              
              w->color = x->parent->color;
              x->parent->color = BLACK;
              w->left->color = BLACK;
              right_rotate(tree, x->parent);
              
              x = tree->root;
            }
          }
        }
      } else {
        break;
      }
    }
    
    x->color = BLACK;
  }
}

void delete_node(Tree *tree, TreeNode *z) {
  if (tree != NULL && z != NULL && z != NULL) {
    TreeNode *x = NULL, *y = z;
    COLOR yOgColor = y->color;
    
    if (z->left == NULL) {
      x = z->right;
      transplant(tree, z, z->right);
    } else if (z->right == NULL) {
      x = z->left;
      transplant(tree, z, z->left);
    } else {
      y = minimum(z->right);
      yOgColor = y->color;
      x = y->right;
      if (x != NULL)
      {
        if (x->parent != NULL && y->parent == z) {
          x->parent = y;
        } else {
          transplant(tree, y, y->right);
          y->right = z->right;
          y->right->parent = y;
        }
      }
      transplant(tree, z, y);
      y->left = z->left;
      y->left->parent = y;
      y->color = z->color;
    }
    if (yOgColor == BLACK) {
      delete_fix(tree, x);
    }
  }
}

TreeNode *maximum(TreeNode *x) {
  while (x->right != NULL) {
    x = x->right;
  }
  
  return (x);
}

TreeNode *minimum(TreeNode *x) {
  while (x->left != NULL) {
    x = x->left;
  }
  
  return (x);
}

#endif //RB_H

Answer 1

I found that there are errors in the logic for insertion, so this needs to be solved first. But instead of trying to find all the mistakes in the insertion and deletion logic, I thought to rewrite it from scratch, also taking a slightly different approach on the following:

• Don't create nodes in the main program, but have the tree-related functions take values instead of nodes, and have them create, find & dispose nodes as needed.

• Benefit from the child array to use the same code for left/right mirror scenarios.

• Add a function to print the tree with indentation, so there is some visual feel of the tree structure

• Add a function to verify that the tree is a valid red-black tree, including checks of:

  • The consistency of parent-child links (a node's parent should have the node as a child)
  • The BST property (a node's key separates the ranges of its sub trees)
  • The red property (a red node cannot have a red parent)
  • The black property (every path from a given node to any leaf in its sub tree must have the same number of black nodes)

Here is the code:

#include <inttypes.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

typedef enum COLOR { BLACK, RED } COLOR;

#ifndef U64_TYPE
#define U64_TYPE
typedef uint_fast64_t U64;
#endif

typedef struct TreeNode TreeNode;
struct TreeNode {
  TreeNode *parent;
  TreeNode *child[2];
  COLOR color;
  U64 blockSize; // 'key'
  void *data;
};

typedef struct Tree Tree;
struct Tree {
  TreeNode *root;
};

int child_side(TreeNode *node) { // Return 1 when the node is its parent right-child, 0 otherwise
    return node->parent && node->parent->child[1] == node;
}

void set_child(Tree *tree, TreeNode *node, int side, TreeNode *child) {
    if (node) {
        node->child[side] = child;
    } else {
        tree->root = child;
    }
    if (child) {
        child->parent = node;
    }
}

void rotate(Tree *tree, TreeNode *node, int side) {
    TreeNode *risingChild = node->child[1-side]; // the child that will move one level up
    set_child(tree, node, 1-side, risingChild->child[side]);
    set_child(tree, node->parent, child_side(node), risingChild);
    set_child(tree, risingChild, side, node);
}

void insert_fix(Tree *tree, TreeNode *node) {
    TreeNode *parent = node->parent;
    node->color = parent ? RED : BLACK;
    if (parent && parent->color == RED) { // red violation
        tree->root->color = BLACK;
        // We have a red-violation as both node and its parent are red.
        TreeNode *grandparent = parent->parent; // Guaranteed to be not NULL
        int side = child_side(parent);
        TreeNode *uncle = grandparent->child[1-side];
        if (uncle && uncle->color == RED) {
            // Parent and Uncle are red
            parent->color = uncle->color = BLACK;
            return insert_fix(tree, grandparent); // repeat using recursion
        }
        // Uncle is black (or NULL)
        if (node == parent->child[1-side]) { // Node is inner grandchild?
            // Node is inner grandchild: turn it into an outer-grandchild configuration 
            rotate(tree, parent, side); // Node is lifted above parent
            node = parent; // swap the naming of the rotated nodes, so node is the lower one
            parent = node->parent;
        }
        // Node is outer grandchild
        rotate(tree, grandparent, 1-side);
        parent->color = BLACK;
        grandparent->color = RED;
    }
}

TreeNode* create_node(U64 blockSize) {
    TreeNode *node = malloc(sizeof(*node));
    node->parent = node->child[0] = node->child[1] = node->data = NULL;
    node->color = BLACK;
    node->blockSize = blockSize;
    return node;
}

TreeNode* find_node(Tree *tree, U64 blockSize) {
    TreeNode *node = NULL;
    TreeNode *curr = tree->root;
    
    while (curr != NULL) {
        node = curr;
        if (node->blockSize == blockSize) {
            break;
        }
        curr = curr->child[blockSize > curr->blockSize];
    }
    return node;
}

void insert_value(Tree *tree, U64 blockSize) {
    TreeNode *leaf = find_node(tree, blockSize);
    // Duplicates not allowed (we could, but then better combine in one node)
    if (!leaf || leaf->blockSize != blockSize) {
        TreeNode *node = create_node(blockSize);
        set_child(tree, leaf, leaf && blockSize > leaf->blockSize, node);
        insert_fix(tree, node);
    }
}

TreeNode *minimum(TreeNode *node) {
    while (node->child[0]) {
        node = node->child[0];
    }
    return node;
}

TreeNode* swap_content(TreeNode *a, TreeNode *b) {
    // Swap data
    void *data= a->data;
    a->data = b->data;
    b->data = data;
    // Swap key
    U64 blockSize = a->blockSize;
    a->blockSize = b->blockSize;
    b->blockSize = blockSize;
    return b;
}

void free_node(TreeNode *node) {
    free(node->data);
    free(node);
}

void delete_fix(Tree *tree, TreeNode *parent, int side) {
    if (!parent) {
        return;
    }
    
    TreeNode *sibling = parent->child[1-side]; // has black height >= 1
    TreeNode *close_nephew = sibling->child[side];

    if (sibling->color == RED) {
        // Case D3: Sibling is red
        rotate(tree, parent, side);
        parent->color = RED;
        sibling->color = BLACK;
        sibling = close_nephew;
        close_nephew = sibling->child[side];
    }
    // Sibling is black
    TreeNode *distant_nephew = sibling->child[1-side];
    if (distant_nephew && distant_nephew->color == RED) {
        // Case D6: distant nephew is red
        rotate(tree, parent, side);
        sibling->color = parent->color;
        parent->color = distant_nephew->color = BLACK;
        return;
    }
    // Distant nephew is not red
    sibling->color = RED; // common action for cases D2, D4, D5
    if (close_nephew && close_nephew->color == RED) {
        // Case D5: close nephew is red
        rotate(tree, sibling, 1-side);
        rotate(tree, parent, side);
        close_nephew->color = parent->color;
        parent->color = sibling->color = BLACK;
        return;
    }
    // Nephews are not red
    if (parent->color == BLACK) {
        // Case D2: Parent is black
        return delete_fix(tree, parent->parent, child_side(parent));
    }
    // Case D4: parent is red    
    parent->color = BLACK;
}

void delete_node(Tree *tree, TreeNode *node) {
    if (node->child[0] && node->child[1]) {
        node = swap_content(node, minimum(node->child[1]));
    }
    TreeNode *child = node->child[!node->child[0]];
    if (node->color == BLACK && child) {
        child->color = BLACK;
    }
    int side = child_side(node);
    set_child(tree, node->parent, side, child);
    if (node->color == BLACK && !child) {
        delete_fix(tree, node->parent, side);
    }
    free_node(node);
}

int delete_value(Tree *tree, U64 blockSize) {
    TreeNode *node = find_node(tree, blockSize);
    if (node) { // found
        delete_node(tree, node);
        return 1;
    }
    return 0;
}

/////////////////////////////////////////////////////////////////////////////////////////////////////

void print_inorder(Tree *t, TreeNode *n, int depth) {
  if (n != NULL) {
    print_inorder(t, n->child[1], depth + 1);
    printf("%*s%lu %c \n", 1+depth*2, " ", n->blockSize, n->color == BLACK ? 'B' : 'r');
    print_inorder(t, n->child[0], depth + 1);
  }
}

void print_tree(Tree *t) {
    print_inorder(t, t->root, 0);
}

int verify_subtree(TreeNode *node, U64 low, U64 high) {
    if (!node) {
        return 0; // OK. Return number of BLACK
    }
    if (node->blockSize < low || node->blockSize > high) {
        printf("node %lu violates BST property. window is (%lu,%lu).\n", node->blockSize, low, high);
        exit(1);
    }
    if (node->parent && node->parent->child[child_side(node)] != node) {
        printf("node %lu is not a child of its parent (inconsistency).\n", node->blockSize);
        exit(1);
    }
    if ((!node->parent || node->parent->color == RED) && node->color == RED) {
        printf("node %lu violates red property.\n", node->blockSize);
        exit(1);
    }
    int black_count1 = verify_subtree(node->child[0], low, node->blockSize);
    int black_count2 = verify_subtree(node->child[1], node->blockSize, high);
    if (black_count1 != black_count2) {
        printf("subtree %lu violates black property.\n", node->blockSize);
        exit(1);
    }
    return black_count1 + (node->color == BLACK);
}

void verify_tree(Tree *tree) {
    verify_subtree(tree->root, 0, 1000000);
}

void shuffle(U64 *array, size_t n) {
    size_t i;
    for (size_t i = 0; i < n - 1; i++) 
    {
      size_t j = i + rand() / (RAND_MAX / (n - i) + 1);
      U64 t = array[j];
      array[j] = array[i];
      array[i] = t;
    }
}

int main(void) {
    Tree tree = {0};
    srand(time(NULL));

    size_t n = 200;
    U64 array[n];
    for (U64 i = 0; i < n; i++) {
        array[i] = i;
    }
    shuffle(array, n);
    
    for (size_t i = 0; i < n; i++) {
        insert_value(&tree, array[i]);
        verify_tree(&tree);
    }
    print_tree(&tree);
    verify_tree(&tree);

    shuffle(array, n);

    for (size_t i = 0; i < n; i++) {
        if (!delete_value(&tree, array[i])) {
            printf("Did not find value %lu in the tree", array[i]);
            exit(1);
        }
        verify_tree(&tree);
    }
    print_tree(&tree);
    return 0;
}