Форум программистов, компьютерный форум CyberForum.ru

бинарное древо (удаление) - C++

Войти
Регистрация
Восстановить пароль
 
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
06.07.2009, 00:36     бинарное древо (удаление) #1
Ребята выручайте не как не могу понять алгоритм удаления из дерева. Кто нить может описать подробные коментарии к удалению узла у которого есть оба поддерева
или в нем где есть ошибка.
Зарание спс.
Код
struct tree *dtree(struct tree *root, char key)
{
  struct tree *p,*p2;

  if(!root) return root; /* вершина не найдена */

  if(root->info == key) { /* удаление корня */   ЭТО ПОНЯТНО
    /* это означает пустое дерево */
    if(root->left == root->right){
      free(root);
      return NULL;
    }
    /* или если одно из поддеревьев пустое */
    else if(root->left == NULL) {
      p = root->right;     ЧТО ДАЛЬШЕ С p ДЕЛАТЬ ПОСЛЕ СОХРАНЕНИЯ ???
      free(root);
      return p;
    }
    else if(root->right == NULL) {
      p = root->left;  [B]ЧТО ДАЛЬШЕ С p ДЕЛАТЬ ПОСЛЕ СОХРАНЕНИЯ ???[/B]
      free(root);        Этот же указатель надо записать в один из указателей  отца        или  я  ошибаюсь чтоб исключить root и сохранить левое поддерево.[/B]
      return p;       
    }                             
    /* или есть оба поддерева */
    else {
      p2 = root->right;  [B]ТУТ плз ПОДРОБНЫЕ КОМЕНТЫ ОСТАВЬТЕ.[/B]
      p = root->right;
      while(p->left) p = p->left;
      p->left = root->left;
      free(root);
      return p2;
    }
  }
  if(root->info < key) root->right = dtree(root->right, key);
  else root->left = dtree(root->left, key);
  return root;
}
Добавлено через 2 часа 15 минут 4 секунды
Я сделал удаление если у узла 2 поддерева. Оцените это будет гуд??
Код
else
  {
	Date<X> *temp = Head, *Old;
	 while(temp)
	  {
		if(temp->date < value)
		 {Old = temp; temp = temp->Right;}
	  else
		if(temp->date > value)
		 {Old = temp; temp = temp->Left;}
	  else
		 {
			Date<X> *Ptr = temp->Right;
			while(Ptr->Left)
			 {Ptr = Ptr->Left;}

			Ptr->Left = temp->Left;
			if(Old->date > value)
			 Old->Left = Ptr;
			else
			 Old->Right = Ptr;
			delete temp; return;
		 }

		}
	 }
Добавлено через 6 минут 55 секунд
Остались непонятки с одиночными подеревьями. То есть если
Код
else if(root->left == NULL) {
      p = root->right;     
      free(root);
Во всех случаях делается такая проверка если поддерво одно??
if(root->date > value)
	Old->Left = p;
else
          Old->Right = p;
Добавлено через 18 минут 24 секунды
Я сделал ребята гляньте ПЛЗ кто понимает правильно ли это будет и может где лишние условия есть. Учимся на ошибках.
Код
template<class X>
void Free<X>::del_free(X &value)
{

  if(!Head)
  {cout << "Дерево пустое." << endl; return;}
else
  if(Head && (Head->Left == Head->Right))
	{delete Head;}

  else
  {
	Date<X> *temp = Head, *Old;
	 while(temp)
	  {

		if(temp->date < value)
		 {Old = temp; temp = temp->Right;}
	  else
		if(temp->date > value)
		 {Old = temp; temp = temp->Left;}
	  else
		 {
		 Date<X> *Ptr2 = temp->Right, *Ptr1;

		  if(!temp->Left)
			{
			  Ptr1 = temp->Right; delete temp;
			  if(Old->date < value)
			  Old->Left = Ptr1;
			  else
			  Old->Right = Ptr1;
			  return;
			}
		 else
			if(!temp->Right)
			{
			 Ptr1 = temp->Left; delete temp;
			  if(Old->date < value)
			  Old->Left = Ptr1;
			  else
			  Old->Right = Ptr1;
			  return;

			}
		 else
		  {
			while(Ptr2->Left)
			 {Ptr2 = Ptr2->Left;}

			Ptr2->Left = temp->Left;
			if(Old->date > value)
			 Old->Left = Ptr2;
			else
			 Old->Right = Ptr2;
			delete temp; return;
		  }
		  }

		}
	 }

}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Юляшка
3 / 3 / 1
Регистрация: 14.12.2008
Сообщений: 30
06.07.2009, 00:44     бинарное древо (удаление) #2
Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации
Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.
Единственное,что могу дать так это теорию=) Я в деревьях не сильна...Мож поможет=)
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
06.07.2009, 00:57  [ТС]     бинарное древо (удаление) #3
Цитата Сообщение от Юляшка Посмотреть сообщение
Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации
Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.
Единственное,что могу дать так это теорию=) Я в деревьях не сильна...Мож поможет=)
СПС Юляшка за какую то помощь, но меня интересует мнение экспертов потому что вроде по алгаритму реализовано то что в теории ток сомнительно мне что много условий.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.07.2009, 05:08     бинарное древо (удаление) #4
C
1
2
3
4
5
6
struct tree *dtree(struct tree *root, char key)
{
  struct tree *p,*p2;
 
  if(!root) return root; /* вершина не найдена */
...
это с Шилдтовской книжки пример, алгоритмы он ещё хорошо объясняет, а кодирует ...
например, он когда видит пустой узел, он в него заходит и внутри определяет, что тот пустой, потом делает новый узел, поднимается и прицепляет его, при этом ему требуется в функцию прохода передавать кроме корня ещё и указатель на дочерний узел
на 503 странице в результате копирования кода, он стал так же получать имя ячейки редкого массива из структуры, которую он забыл передать в функцию (ну, то есть, мало того, что там нерационально передавать всю структуру, чтобы взять с неё только имя ячейки, так эта конструкция ещё и копировалась несколько раз как нормальная и в итоге ещё и к ошибке привела)
сортировка обменом типа

Код
void sort(int *a, int size)
{    
    int i, j, t;
    
    for (i = 0; i < size-1; i++)
        for (j = i+1; j < size; j++)
            if (a[i] > a[j])
                t = a[i], a[i] = a[j], a[j] = t;
}
там вообще в таком забубённом виде, куча переменных, использование их через индексы и ещё флажок состояния
ща напишу, это надо видеть

Код
/* Сортировка посредством выбора. */
void select(char *items, int count)
{
  register int a, b, c;
  int exchange;
  char t;
  
  for(a=0; a < count-1; ++a) {
    exchange = 0;
    c = a;
    t = items[a];
    for(b=a+1; b < count; ++b) {
      if(items[b] < t) {
        c = b;
        t = items[b];
        exchange = 1;
      }
    }
    if(exchange) {
      items[c] = items[a];
      items[a] = t;
    }
  }    
}
так что, я не знаю, сам Шилдт пишет эти коды или нет, но то, что он не запускал многие - это точно

он объяснял там алгоритм удаления узла, нужно взять левую ветвь узла и перецепить её в правую ветвь, а потом правую ветвь прикрепить на место этого узла и узел освободить
в правой ветви нужно спустится к самому левому листу и прицепить её там, видимо, в левый указатель
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
06.07.2009, 07:57  [ТС]     бинарное древо (удаление) #5
Цитата Сообщение от accept Посмотреть сообщение
так что, я не знаю, сам Шилдт пишет эти коды или нет, но то, что он не запускал многие - это точно
СПС за ответ.
Вот по ним мы и учимся и думаем не то мы недалекие не то они слишком умны.
Но все таки плз ваше мнение о моей функции. Не много ли там условий может какое я лишнее написал, чтоб для себя это сразу понять на этапе обучения.
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.07.2009, 11:57     бинарное древо (удаление) #6
Цитата Сообщение от Alexen
ЧТО ДАЛЬШЕ С p ДЕЛАТЬ ПОСЛЕ СОХРАНЕНИЯ ?
обрати внимание там дальше free и return p
она проверяет если одна ветвь пустая, то возвращает непустую
если же обе непустые, то перецепляет всё на одну и возвращает её
смысл в том, чтобы когда она спустится куда-то в глубину, чтобы она не меняла всё дерево, а просто там кусок в глубине поменяла и всё
просто при удалении узла его адрес становится больше не нужен, и вместо него нужно поместить адрес ветви
я б если писал, то написал бы функцию для перецепления ветвей и не заморачивался что и куда она там перецепляет прямо там, где идёт зачистка узла и возврат ветви - из-за этого такой сыр бор, что ничего не понятно
это выглядело бы
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct tree *dtree(struct tree *root, char key)
{
    void *leftson, *rightson;
    
    if (!root)
        return NULL;
 
    if(root->info != key) {
        if(root->info < key)
            root->right = dtree(root->right, key);
        else
            root->left = dtree(root->left, key);
        return root;
    }
    
    leftson = root->left;
    rightson = root->right;
    free(root);
 
    if (leftson && rightson)
        return MergeSons(leftson, rightson);
    else if (leftson)
        return leftson;
    else if (rightson)
        return rightson;
    else
        return NULL;
}
а функция перецепления принимает два узла и вешает левый на самый левый лист или правый на самый правый лист
в общем, здесь записано то же самое, только гораздо больше контроля и проще для развития, так как не запускал, 1% процент ошибки оставляем
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
06.07.2009, 13:32  [ТС]     бинарное древо (удаление) #7
accept, Глянь плз так будет норм ??
Код
template<class X>
void Free<X>::del_free(X &value)
{

  if(!Head)
  {cout << "Дерево пустое." << endl; return;}
else
  if(Head && (Head->Left == Head->Right))
	{Head = NULL; delete Head;}

  else
  {
	Date<X> *temp = Head, *Old;
	 while(temp)
	  {
		if(temp->date < value)
		 {Old = temp; temp = temp->Right;}
  else
		if(temp->date > value)
		 {Old = temp; temp = temp->Left;}
  else
	 {
		 if(!temp->Left)  {del_left(temp, Old, value);return;}
	  else
		 if(!temp->Right) {del_right(temp,Old, value);return;}
	  else
		{
		 del_two(temp,Old, value); return;
		}
	  }

	 }
  }

}

template<class X>
void Free<X>::del_left(Date<X> *temp,Date<X> *Old, X &value)
{
  Date<X> *Ptr1 = temp->Right; delete temp;
			  if(Old->date > value)
			  Old->Left = Ptr1;
			  else
			  Old->Right = Ptr1;
}


template<class X>
void Free<X>::del_right(Date<X> *temp, Date<X> *Old, X &value)
{
  Date<X> *Ptr1 = temp->Left; delete temp;
			  if(Old->date < value)
			  Old->Right = Ptr1;
			  else
			  Old->Left = Ptr1;
}

template<class X>
void Free<X>::del_two(Date<X> *temp, Date<X> *Old, X &value)
{
	Date<X> *Ptr2 = temp->Right;
			while(Ptr2->Left)
			 {Ptr2 = Ptr2->Left;}

			Ptr2->Left = temp->Left;
			if(Old->date > value)
			 Old->Left = Ptr2;
			else
			 Old->Right = Ptr2;
			delete temp; return;
 }
accept
4838 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
07.07.2009, 10:13     бинарное древо (удаление) #8
Код
{Head = NULL; delete Head;}
тут поменять очерёдность

Код
if(!temp->Left)  {del_left(temp, Old, value);return;}
а если ещё и !temp->Right ?

видишь
C
1
2
    if (leftson && rightson)
        return MergeSons(leftson, rightson);
здесь эта проверка проводится в первую очередь и, только если она не сработала, тогда остальные действия

ещё void'овые указатели применяются для поддержки общего вида дерева - это когда узлы бывают разные, а функции для работы с бинарным деревом применяются одни и те же
то есть, несмотря на то, что там они возвращаются неправильно, там они такие и остаются, надо функцию перевести на общий вид

вместо
C
1
struct tree *dtree(struct tree *root, char key)
C
1
void *dtree(void *root, char key)
C
1
    if(root->info == key)
C
1
    if(((struct tree *) root)->info == key)
для получения элементов можно написать специальную функцию, и так для каждого вида узла, а потом просто в функцию обработки дерева передать указатель на функцию обработки узла

таким образом дерево можно написать один раз, а видов узлов создавать сколько угодно и для них писать индивидуальные функции

C
1
2
3
4
struct tree1 {
    char key;
    struct tree1 *left, *right;
};
C
1
2
3
4
5
struct tree2 {
    char *s;
    int size;
    struct tree2 *left, *right;
};
C
1
2
3
4
struct tree3 {
    struct tree *root;
    struct tree3 *left, *right;
};
то есть, как видишь, для создания и заполнения каждого из этих узлов нужно применять совершенно различные алгоритмы, но при всём при этом можно иметь одну функцию поиска в дереве, одну функцию вывода дерева, одну функцию удаления дерева и одну функцию добавления/удаления любого элемента
итого пять функций, а не пятнадцать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2009, 13:36     бинарное древо (удаление)
Еще ссылки по теме:

Бинарное дерево поиска (удаление, добавление элемента) C++
C++ Бинарное с рекурсией
Соединение двух программ в одну (бинарное сложение и бинарное сравнение) C++
Бинарное дерево из слов и удаление узла C++
C++ Бинарное древо (реализовать структуру и обход веток с выводом на экран) - C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Alexen
5 / 5 / 0
Регистрация: 14.11.2008
Сообщений: 77
07.07.2009, 13:36  [ТС]     бинарное древо (удаление) #9
СПС в основном все понял. Главное понял смысл реализации а дальше разбить по функциям не проблема. Чтоб я без вас делал, ХОРОШО что есть где и кому подсказать.
Yandex
Объявления
07.07.2009, 13:36     бинарное древо (удаление)
Ответ Создать тему
Опции темы

Текущее время: 08:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru