大量删除红黑树节点导致死循环

问题描述 投票：0回答：1

我一直在用 C 实现 RedBlack Tree（Red Black Tree Node Insertion Overwrites Previously Added Node）并且遇到了一个问题，在大量删除（~1000+ 到 ~2000+）之后，它得到陷入无限循环。

RB删除代码：


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);
}

我已经缩小了它遇到无限循环的地方，但罪魁祸首一定是在 

delete_node
实施的其余部分：

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

司机代码

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;
}

到目前为止，我也尝试在

minimum
函数的开头添加一些检查，但这也没有解决问题。

如有任何帮助或意见，我们将不胜感激！

更新：

下面是更新后的完整源代码，现在使用 

NULL
而不是 
tree->nil
来表示叶节点。

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
c algorithm data-structures avl-tree red-black-tree
1个回答
0
投票

我发现插入的逻辑有错误，所以需要先解决这个问题。但是我没有试图找出插入和删除逻辑中的所有错误，而是想从头开始重写它，并在以下方面采取了稍微不同的方法：

  • 不要在主程序中创建节点，而是让与树相关的函数采用 values 而不是节点，并让它们根据需要创建、查找和处理节点。

  • 受益于 

    child
    阵列对左/右镜像场景使用相同的代码。

  • 添加缩进打印树的功能，这样在视觉上有点树结构的感觉

  • 添加一个函数来验证树是否是有效的红黑树，包括检查：

    • 父子链接的一致性（一个节点的父节点应该有一个子节点）
    • BST 属性（节点的键分隔其子树的范围）
    • 红色属性（红色节点不能有红色父节点）
    • 黑色属性（从给定节点到其子树中任何叶子的每条路径必须具有相同数量的黑色节点）

代码如下：

#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;
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.