Как правильно вставить / удалить в двоичном дереве поиска на C?
https://stackoverflow.com/questions/676048
-
21-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я вроде как должен отложить свои предыдущие вопросы на C, потому что этот сейчас важнее...
Я уже закодировал функции insert и delete в моем двоичном дереве поиска, но функция delete является неполной.Есть пара вещей, в которых мне нужна помощь...
1) Хороша ли моя функция вставки или ее можно как-то улучшить?
2) В моей функции удаления отсутствует удаление узла как с левым, так и с правым дочерними элементами.За последние несколько часов я много искал, но не смог найти подходящего способа сделать это.
2.а) Как я должен удалить узел с 2 дочерними узлами?
2.б) Как и в первом вопросе, хороша ли функция удаления или ее можно улучшить?Я знаю, что это возможно, потому что я повторяю много кода в этих ifs, но я не вижу, как я могу это улучшить, мне тоже нужна помощь в этом.
typedef struct sClientProfile *ClientProfile;
typedef struct sClientTree *ClientTree;
typedef struct sClientProfile {
char *clientName;
int clientAge;
int clientNIF;
} nClientProfile;
typedef struct sClientTree {
ClientProfile clientProfile;
char *clientName;
ClientTree leftTree;
ClientTree rightTree;
} nClientTree;
void addClientToTree(ClientTree *cTree, ClientProfile cProfile) {
if(!*cTree) {
ClientTree new = (ClientTree)malloc(sizeof(nClientTree));
if(!new) {
perror("malloc");
}
new->clientName = strdup(cProfile->clientName);
new->clientProfile = cProfile;
new->leftTree = NULL;
new->rightTree = NULL;
*cTree = new;
} else {
if(strcmp((*cTree)->clientName, cProfile->clientName) > 0) {
addClientToTree(&(*cTree)->leftTree, cProfile);
} else {
addClientToTree(&(*cTree)->rightTree, cProfile);
}
}
}
void deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return;
int nCompare = strcmp((*cTree)->clientName, cName);
if(nCompare > 0) {
deleteClientFromTree(&(*cTree)->leftTree, cName);
} else if(nCompare < 0) {
deleteClientFromTree(&(*cTree)->rightTree, cName);
} else {
if(!(*cTree)->leftTree && !(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
cliPtr = NULL;
*cTree = NULL;
} else if(!(*cTree)->leftTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->rightTree;
} else if(!(*cTree)->rightTree) {
ClientTree cliPtr = *cTree;
free(cliPtr->clientProfile);
free(cliPtr);
cliPtr->clientProfile = NULL;
*cTree = (*cTree)->leftTree;
} else {
// MISSING DELETE CASE
}
}
}
Вы, вероятно, заметите, но позвольте мне просто сделать 2 замечания:
- Это дерево использует строки вместо обычного представления int.Вот почему я постоянно использую strcmp(), я думаю, что использую его правильно.
- Я не использую рекурсию, я скорее передаю указатель (в данном случае на указатель структуры) и работаю с этим.Как-то это выглядит более чисто, и в будущем я хочу вернуть значение успеха, если узел был удален.
ОБНОВЛЕНИЕ НИЖЕ:
Я уже сделал свою итеративную версию функции удаления, но мне не нравятся некоторые вещи в ней, возможно, их можно улучшить (или нет), но я не вижу, как.Я также попытался закодировать случай, когда он отсутствовал, удалив узел с 2 дочерними элементами, но он работает не так, как должен...
Я прокомментировал весь код, где, по моему мнению, код можно улучшить и в чем проблема.Я также назвал эти проблемы A, B (B больше нет), C и D, чтобы мы могли легко ссылаться на них.
bool deleteClientFromTree(ClientTree *cTree, char *cName) {
if(!cTree) return FALSE;
ClientTree currPtr = *cTree;
ClientTree prevPtr = NULL;
int nCompare;
while(currPtr) {
nCompare = strcmp(currPtr->clientName, cName);
if(nCompare > 0) {
prevPtr = currPtr;
currPtr = currPtr->leftTree;
} else if(nCompare < 0) {
prevPtr = currPtr;
currPtr = currPtr->rightTree;
} else {
/*
* A)
*
* The following cases have 3 lines in common, the free()
* calls and return statement. Is there anyway to improve
* this code and make it more compact?
*
* Of course, the printf's are to be removed...
*/
if(!prevPtr && !currPtr->leftTree && !currPtr->rightTree) {
printf("CASE #1\n");
*cTree = NULL;
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else if(!currPtr->leftTree || !currPtr->rightTree) {
printf("CASE #2\n");
if(prevPtr->leftTree == currPtr) {
prevPtr->leftTree = currPtr->rightTree;
} else {
prevPtr->rightTree = currPtr->leftTree;
}
free(currPtr->clientProfile);
free(currPtr);
return TRUE;
} else {
printf("CASE #3\n");
ClientTree tempPtr = currPtr->rightTree;
while(tempPtr->leftTree) {
tempPtr = tempPtr->leftTree;
}
/*
* C)
*
* This has a big problem...
*
* If you take a look at the ClientProfile structure,
* in the first post, you'll see two ints
* (clientNIF/clientAge) and one char* (clientName).
*
* The problem is that the following code line is only
* copying the integer data, not the string. For some
* reason, the string remains the old one.
*
* I tried to use strdup() directly on clientName like:
* currPtr->clientProfile->clientName = strdup(tempPtr->clientProfile->clientName);
* but it still doesn't work.
*
* Why everything is being copied but the strings?
*/
currPtr->clientProfile = tempPtr->clientProfile;
/*
* D)
*
* Is there anyway to not call the function itself
* and make the while loop once again and delete the
* corresponding leaf?
*/
return deleteClientFromTree(&currPtr->rightTree, tempPtr->clientProfile->clientName);
}
}
}
return FALSE;
}
Решение
Когда вы удаляете узел, вы должны что-то сделать с его дочерними элементами.
Если нет детей - нет проблем.Вы просто удаляете узел.
Если есть левый ребенок, тоже никаких проблем;вы удаляете узел и перемещаете его левый дочерний элемент на его место.
То же самое для правильного ребенка;просто переместите дочерний элемент на место удаленного узла.
Проблема возникает, когда вы хотите удалить узел, у которого есть как левые, так и правые дочерние элементы.Вы могли бы переместить левый или правый дочерний элемент на место удаленного узла, но что вы тогда будете делать с другим дочерним элементом и его поддеревом?
Решение заключается в следующем;вы находите логического преемника удаляемого узла.Под логическим преемником я подразумеваю следующее;допустим, у вас есть дерево, состоящее из целых чисел, и вы удаляете узел со значением 35, логический преемник является следующим по величине числом.Ya?если бы вы выполняли обход по порядку, это был бы элемент, к которому вы переходите после элемента, который вы удаляете.
Итак, есть простое правило, позволяющее найти логичного преемника;вы идете направо (у вас всегда есть право, потому что это тот случай, когда у вас двое детей), а затем идете как можно дальше налево.
Элемент, на котором вы заканчиваете, является логическим преемником.Он больше, чем удаленный элемент (вы перешли в самом начале, помните?), но это наименьший следующий по величине элемент.
Теперь у этого элемента ВСЕГДА есть только один дочерний элемент или его вообще нет - потому что вы зашли влево так далеко, как только могли, помните?таким образом, вы больше не можете идти влево - потому что там нет left - так что у этого элемента нет дочерних элементов или только правый дочерний элемент, и это означает, что он попадает в одну из легко отключаемых категорий (нет дочерних элементов или только один дочерний элемент).Так что отсоединение это элемент - это просто.
Теперь начинается самое интересное - подумайте об этом;если бы этот следующий по величине элемент находился в том же месте дерева, что и элемент, который вы хотите удалить, дерево по-прежнему было бы действительным и корректным - потому что все, что слева от каждого элемента, меньше, все, что справа, больше.
Итак, что вы делаете, это;вы копируете пользовательские данные из следующего по величине узла в удаляемый узел и удаляете этот следующий по величине узел (у него нет дочерних элементов или просто правильный дочерний элемент, поэтому его легко отсоединить и удалить).
И это все!
Итак, по сути - найдите своего логического преемника, отсоедините его от дерева и поместите его пользовательские данные в элемент, который вы на самом деле изначально удаляете (который вы затем, конечно, не удаляете, потому что он все еще физически является частью дерева).
Другие советы
Во-первых, вы упомянули, что не используете рекурсию, но у каждой функции есть логический путь, который вызывает саму себя.
Перейдем к вопросам:
1) Удалите рекурсию.Это может доставить вам массу неприятностей, если ваше дерево достаточно велико, чтобы взорвать ваш стек.Gcc имеет ограниченную поддержку хвостовой рекурсии, но я бы не стал на это рассчитывать.
2) Обычно, когда вы удаляете дочерний элемент с двумя узлами, вы перемещаете левый или правый узел в положение, в котором находился удаленный узел.(Это очень упрощенный случай, я предполагаю, что ваше дерево не сбалансировано)
2.b) В вашем коде удаления возникли некоторые проблемы.Я бы порекомендовал пройтись по нему с несколькими гипотетическими ситуациями.Для меня сразу же стало очевидным, что нужно освободить указатель, а затем отложить его:
free(cliPtr);
cliPtr->clientProfile = NULL;
Конечно, вы всегда можете побеспокоиться о стиле, как только определитесь с правильностью.
В идеале существует три случая удаления узла в BST:
Случай 1:
X has no children: remove X
Случай 2:
X has one children : Splice out X
Случай 3:
X has two children : swap X with its successor and follow case #1 or #2
Итак, для отсутствующего случая удаления:
Когда X (узел для удаления) имеет двух дочерних элементов, замените X на преемника X и следуйте варианту # 1 или варианту #2.Вы также можете заменить его предшественником, возможно, это будет хорошей альтернативой.
if ( X->left && X->right)
{
NODE *Successor = FindSuccessor(X);
X->data = Successor->data;
free(Successor);
}
этими двоичными кодами являются insert, delete, search и quit.Примеры:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Binary Tree {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
LinkedList ll = new LinkedList();
ll.add("\n"+"mai 0020");
ll.add("\n"+"king 0019");
ll.add("\n"+"maan 0002");
ll.add("\n"+"dimple 0024");
ll.add("\n"+"eman 0004");
ll.add("\n"+"lara 0005");
ll.add("\n"+"cute 0008");
ll.add("\n"+"irene 0011");
ll.add("\n"+"sheena 0030");
ll.add("\n"+"aisy 0003");
System.out.println("display: " + ll);
System.out.println("\n\n");
for(int c=0; c<=10; c++) {
System.out.println("select from: 1-insert, 2-delete," +
" 3-display, 4-search, 5-quit");
String x = br.readLine();
int y = Integer.parseInt(x);
switch (y) {
case 1: //inserting
System.out.println("input name");
String n= br.readLine();
System.out.println("input a list number");
String o = br.readLine();
int z = Integer.parseInt(o);
ll.add("\n"+n+" "+z);
break;
case 2: // delete
ll.removeFirst();
break;
case 3: //Display
System.out.println("\n\n"+"List of employee: " + ll);
System.out.println("\n\n");
break;
case 4: //search
System.out.println("\n");
System.out.println("Search");
System.out.println("first element of the Linkedlist is: "
+ ll.getFirst());
System.out.println("\n\n");
System.out.println("last element of linkedlist:"
+ ll.getLast());
break;
case 5: //quit
System.out.println("\n\n\n\n\n"
+ " Thank You Very Much!!!!!!!\n\n\n");
System.exit(0);
break;
}
}
}
}
int delete_value(Tree*&root,Tree*&find,Tree*&ptr,int numb){
if(find->value==number){
//the number exist in the root,so we should find the highest value inside the right brache and replace it with the root.
Tree*ptr2=NULL;
Tree*ptr3=NULL;//pointer pointing to the parent of the last element of ptr2.
ptr2=root->right;
while(ptr2!=NULL){
ptr3=ptr2;
ptr2=ptr2->left;
}
if(ptr2->right!=NULL){
ptr3->left=ptr2->right;
}
swap(ptr2->value,root->value);
delete ptr2;
ptr2=ptr3=NULL;
}
else{
while(find->value!=numb){
if(find->value!=numb){
ptr=find;
}
if(find->value < numb){
find=find->right;
return delete_value(root,find,ptr,numb);
}
else{
find=find->left;
return delete_value(root,find,ptr,numb);
}
}//end of while
}//end of else
//the pointer find is pointing at the element we want to delete.
//the pointer ptr is pointing at the element before the one's we want to delete.
//case 1:the element to delete don't have any children
if(find->right==NULL && find->left==NULL){
if(ptr->left=find){
ptr->left=NULl;
delete find;
}
else{
ptr->right=NULL;
delete find;
}
}//end of the first case.
//case 2:the element has one child it could be to the left or to the right.
//a-child to the right.
if( find->right!=NULL && find->left==NULL ){
Tree*ptr2=find->right;
while(ptr2!=NULL){
ptr2=ptr2->left;//find the highest value in the right branche and replace it with the delete element
}
swap(find->value,ptr2->value);
delete ptr2;
ptr2=NULL;
}
//b-child to the left.
if(find->right==NULL && find->left!=NULL){
Tree*ptr2=find->left;
//check wether the find element is to the right or to the left of ptr.
if(ptr->left==find){
ptr->left=ptr2;
delete find;
}
else{
ptr->right=ptr2;
delete find;
}
}//end of the second case.
//case3: the element has to children.
if(find->right!=NULL&&find->left!=NULL){
Tree*ptr2=find->left;
while(ptr2->right!=NULL){
ptr2=ptr2->right;
}
swap(ptr2->value,find->value);
delete ptr2;
ptr2=NULL;
}//end of case 3.
}//end of the function.
