Блог

По какой-то странной причине мое дерево BST на самом деле работает не так, как ожидалось, это код, который я создал:

 #include lt;stdio.hgt; #include lt;time.hgt; #include lt;stdlib.hgt; #include lt;limits.hgt;  //Creating the main structure of the main BST Tree struct treeNode{  int key; //The key of the node  struct treeNode *leftChild; //The left child of the node  struct treeNode *rightChild; //The right child of the node  struct treeNode *parent; //The parent of the node };  //Function for implementing and creating a new node in the BST struct treeNode* newNode(int x){  struct treeNode *n;  n = malloc(sizeof(struct treeNode));  n-gt;key = x;  n-gt;leftChild = NULL;  n-gt;rightChild = NULL;  n-gt;parent = NULL;   return n;  }  //Function for finding the minimun value in a treeNode struct treeNode* BSTTreeMin(struct treeNode *root){    if(root-gt;leftChild == NULL){  return root; //if the left child is nil, return the root  }  else{  return BSTTreeMin(root-gt;leftChild); //otherwise we repeform the same operation on the left child  } }  //Function for searching a specific node in the BST struct treeNode* BSTTreeSearch(struct treeNode *root,int x){  if(root == NULL || root-gt;key == x){  return root; //if root corresponds to key then the element x is found   }  if(x lt; root-gt;key){  return BSTTreeSearch(root-gt;leftChild, x); // in the case where the element x is smaller than root--gt;key then it searches the left child  }  else{  return BSTTreeSearch(root-gt;rightChild, x);// in the opposite case, it searches the right child  } }  //function for inserting a new key in the BST struct treeNode* BSTTreeInsert(struct treeNode *root, struct treeNode *z){  struct treeNode *y = NULL;  struct treeNode *x = root;  while(x != NULL){  y = x;  if(z-gt;key lt;= x-gt;key){  x = x-gt;leftChild;  }  else{  x = x-gt;rightChild;  }  }  z-gt;parent = y;  if(y == NULL){  root = z;  }  else if(root != NULL amp;amp; z-gt;key lt;= y-gt;key){  y-gt;leftChild = z;  }  else{  y-gt;rightChild = z;  } }  struct treeNode* BSTTreeTransplant(struct treeNode *root, struct treeNode *u, struct treeNode *v){  if(u-gt;parent == NULL){  root = v;  }  else if(u == u-gt;parent-gt;leftChild){  u-gt;parent-gt;leftChild = v;  }  else{  u-gt;parent-gt;rightChild = v;  }  if(v != NULL){  v-gt;parent = u-gt;parent;  } } //function for delete a node in a BST struct treeNode* BSTTreeDelete(struct treeNode *root, struct treeNode *z){  if(z-gt;leftChild == NULL){  BSTTreeTransplant(root, z, z-gt;rightChild);  }  else if(z-gt;rightChild == NULL){  BSTTreeTransplant(root, z, z-gt;leftChild);  }  else{  struct treeNode *y = BSTTreeMin(z-gt;rightChild);  if(y-gt;parent != z){  BSTTreeTransplant(root, y, y-gt;rightChild);  y-gt;rightChild = z-gt;rightChild;  y-gt;rightChild-gt;parent = y;  }  BSTTreeTransplant(root, z, y);  y-gt;leftChild = z-gt;leftChild;  y-gt;leftChild-gt;parent = y;  } }  //Function for emptying a BST void BSTTreeDeallocate(struct treeNode *root){  if(root == NULL){  return;  }  BSTTreeDeallocate(root-gt;leftChild);  BSTTreeDeallocate(root-gt;rightChild);  free(root); }  //function that checks if the Bst is valid (antagonistic function) int isValidBstHelper(struct treeNode *root, int low, int high) {  return root == NULL ||   (root-gt;key gt;= low amp;amp; root-gt;key lt;= high amp;amp;  isValidBstHelper(root-gt;leftChild, low, root-gt;key) amp;amp;  isValidBstHelper(root-gt;rightChild, root-gt;key, high));  }  //function that initiate the validity check of the Bst int isValidBst(struct treeNode *root) {  return isValidBstHelper(root, INT_MIN, INT_MAX); }  //Main experiment function for this program, calculating the time for inserting, deleting and searching nodes in our BST double SingleExperiment(int max_keys,double max_search,double max_delete,int max_instances){  double t_tot = 0;  int i;  int key;  double search;  double delete;   for(i = 1; i lt;= max_instances; i  ){  clock_t start_t, end_t;    srand(0);  struct treeNode *root;  root = newNode(rand()); // Initializing the root of the tree   struct treeNode *i = newNode(rand());  struct treeNode *d = newNode(rand());   start_t = clock();  for(key = 1; key lt;= max_keys; key  ){  BSTTreeInsert(root,i); //Starting with the insertion of the nodes  }  for(search = 1; search lt;= max_search; search  ){  BSTTreeSearch(root, rand()); //Following by the searching of the nodes  }  for(delete = 1; delete lt;= max_delete; delete  ){  BSTTreeDelete(root, d); //Finally, the deletion of the nodes  }   end_t = clock();  double t_elapsed = (double)(end_t - start_t); //Calculation of the time elapased  t_tot  = t_elapsed; //Adding the time to the total time   //inorder(root); //checks if the BST is in order --gt; prints an ordered array   //Checking if the Bst is valid  if (isValidBst(root)) {  printf("The tree is a valid BST n");  } else {  printf("The tree is NOT a valid BST n");  }   BSTTreeDeallocate(root); //Emptying the tree   }  return t_tot/max_keys; //Returning the average time }  //main function (represents the experiment function) int main(void){   int min_keys = 5;  int max_keys = 10;  int max_instances = 5;  int percentage_search = 60;  int keys;  int seed = 0;  //setting up the main parameters for the experiment   printf("Binary Search Tree n");  for(keys = min_keys; keys lt;= max_keys; keys = keys  1){  srand(seed);  double max_search = keys * percentage_search / 100;  double max_delete = keys - max_search;   double time = SingleExperiment(keys,max_search,max_delete,max_instances);  printf("%d %fn",keys,time);//printing the time associate to each key value    seed = seed  1;  }   return 0;  }  

результатом должно быть «дерево допустимо» для каждой итерации и общее время для каждого отдельного номера ключа. Всякий раз, когда я запускаю программу, она выводит только «Дерево двоичного поиска» и ничего больше. Не могли бы вы, пожалуйста, любезно помочь мне?

Заранее всем спасибо!

Основная проблема возникает в этом цикле:

 for(key = 1; key lt;= max_keys; key  ){  BSTTreeInsert(root,i);  }  

Игнорирование этого i является плохим выбором в качестве имени переменной для узла (оно уже используется в качестве переменной цикла), это приведет к повторной вставке одного и того же узла. Это означает, что вторая итерация этого цикла вставит узел, который уже находится в дереве. Это сделает узел его собственным дочерним (самоназвание). Как следствие, третья итерация этого цикла никогда не достигнет листа в дереве, так как он продолжает следовать этой ссылке на себя, бегая по кругу.

Быстрое решение состоит в том, чтобы вставлять новые узлы на каждой итерации:

 for(key = 1; key lt;= max_keys; key  ){  BSTTreeInsert(root, newNode(rand());  }  

Теперь это устраняет вашу проблему, но все же я хотел бы отметить, что остальная часть кода эксперимента на самом деле не очень полезна:

• BSTTreeSearch очень, очень вероятно, что функция будет вызываться со значениями, которые не встречаются в дереве, и не проверяется, действительно ли функция возвращает ожидаемый результат. Но тогда также должны быть положительные тесты-чтобы увидеть, действительно ли найдены значения, которые находятся в дереве.
• BSTTreeDelete вызывается повторно с одним и тем же узлом. Более того, этот узел никогда не вставлялся в дерево, поэтому эти вызовы никогда не удалят какой-либо узел из дерева.

Возможно, вы захотите улучшить это, но это выходит за рамки вашего вопроса.