функция_удаления_в_дереве

[Alexander1205]

В данной программе реализовано почти все,кроме фунции удаления,которую я так и не смог реализовать. Руководствуюсь методами:
-если это лист, то просто удаляем.
-если элемент имеет левое поддерево, "поднимаем" из него максимальное.
-если только правое поддерево:
-либо "поднимаем" из него минимальный
-либо просто "пропускаем" удаляемый..Вопрос: А верен ли этот алгоритм?
Коллеги, если кто подскажет идею функции удаления, буду премного благодарен.

#include<iostream>
using namespace std;
 
class Node
{
        public:
                int data;
                Node *parent,*left,*right;
                Node(int v = 0)
                {
                        data = v;
                        parent = NULL;
                        left = NULL;
                        right = NULL;
                }
 
};
 
class Tree
{
private:
        Node *root;
public:
        Tree()
        {
                root = NULL;
        }
 
        void Print(Node *n);
        void Add(int value);
        Node* GetRoot();
        Node* Search(int key);
        Node* Min(Node *n);
        Node* Max(Node *n);
        Node* Next(Node *n);
        Node* Prev(Node *n);
        void Del(Node *n);
        void DelALL();
        ~Tree(){DelALL;}
 
 
};
 
void Tree::Print(Node *n)
{
        if(n)
        {
                Print(n->left);
                cout<<n->data<<" ";
                Print(n->right);
        }
}
 
void Tree::Add(int value)
{
        Node *n = new Node(value);
        Node *target = NULL;
        Node *tmp = root;
        while(tmp)
        {
                target = tmp;
                if(n->data<tmp->data)
                        tmp = tmp->left;
                else
                        tmp = tmp->right;
        }
        n->parent = target;
        if(!target)
                root = n;
        else if (target->data>n->data)
                target->left = n;
        else
                target->right = n;
}
Node* Tree::GetRoot()
{
        return root;
}
Node* Tree::Search(int key)
{
        Node *tmp = root;       
        {
                while(tmp && key!=tmp->data)
                {
                        if(key<tmp->data)
                                tmp = tmp->left;
                        else
                                tmp = tmp->right;
                }
        }
        return tmp;
}
Node* Tree::Min(Node *n)
{
        if(n)
        {
                while(n->left)
                        n = n->left;
        }
        return n;
}
Node* Tree::Max(Node *n)
{
        if(n)
        {
                while(n->right)
                        n = n->right;
        }
        return n;
}
 
Node* Tree::Next(Node *n)
{
        Node *tmp = NULL;
        if(n)
        {
                if(n->right)
                        return Min(n->right);
                tmp = n->parent;
                while(tmp->right==n&& tmp)
                {
                        n =tmp;
                        tmp = tmp->parent;
                }
        }
        return tmp;
}
 
Node* Tree::Prev(Node *n)
{
        Node *tmp = NULL;
        if(n)
        {
                if(n->left)
                        return Max(n->left);
                tmp = n->parent;
                while(tmp->left==n&& tmp)
                {
                        n = tmp;
                        tmp = tmp->parent;
                }
        }
        return tmp;
}
 
//void Tree::Del(Node *n)
 
 
 
 
 
 
 
void main()
{
        Tree T;
        int data[20];   
        for(int i = 0;i<20;i++)
        T.Add(rand()%100);
        T.Print(T.GetRoot());
        if(T.Search(34))
                cout<<"\n34 in our tree!\n";
        else
                cout<<"\n34 is not found!\n";
        cout<<"\n";
        cout<<T.Min(T.GetRoot())->data<<" is minimum!\n";
        cout<<T.Max(T.GetRoot())->data<<" is maximum!\n";
        cout<<"\n";
        cout<<T.Next(T.Min(T.GetRoot()))->data<<" is next after minimum!\n";
        cout<<T.Prev(T.Max(T.GetRoot()))->data<<" is previous before maximum!\n";
        
}

Эти прототипы функций пока можно закомментить

//void Del(Node *n);
//void DelALL();
//~Tree(){DelALL;}

[Kukurudza]

		public:
			void delete_element_with_key( T1 key )							//	удаление элемента (оболочка)
			{
				_clear_list();												//	удаляем список указателей
				_num = 0;
				_delete_element_with_key( key, _root );
			};

		private:
			void _delete_element_with_key( T1 key, node<T1, T2>* root )
			{
				node<T1, T2> * pointer = root;
				node<T1, T2> * parent  = NULL;

				while (pointer != NULL && pointer -> key != key)	
				{
						parent = pointer;
						++_num;
						if (key < pointer -> key)
								pointer = pointer -> left;
						else
								pointer = pointer -> right;
				}

				if (pointer != NULL)
				{
					if ( parent == NULL )
					{
						if ( pointer -> left == NULL && pointer -> right == NULL )					//	если нет ни одного из детей
						{
							delete _root;															//	удаляем вершину. обнуляем указатель
							_root = NULL;
							_size = 0;
							return;
						};

						if ( pointer -> left == NULL && pointer -> right != NULL )					//	если нет левого потомка но есть правый
						{
							parent = _root;
							_root = _root -> right;													//	то корнем дерева теперь будет правый потомок
							delete parent;															//	старый корень удаляем
							--_size;
							return;
						};

						if ( pointer -> right == NULL && pointer -> left != NULL )					//	если нет правого потомка но есть левый
						{
							parent = _root;
							_root = _root -> left;													//	то корнем дерева теперь будет левый потомок
							delete parent;															//	старый корень удаляем
							--_size;
							return;
						};

						if ( pointer -> right != NULL && pointer -> left != NULL )					//	если есть оба потомка
						{
							if ( pointer -> right -> left == NULL )									//	причем левый потомок правый корня не существует
							{
								node<T1, T2>* removed = pointer -> right;							//	то удалим правого потомка от корня
								pointer -> element = pointer -> right -> element;					//	при этом переписав правого потомка в корень
								pointer -> key = pointer -> right -> key;
								pointer -> right = pointer -> right -> right;
								delete removed;														//	удаляем правого потомка
								--_size;
								return;
							}
							else																	//	если левый потомок правого потомка существует
							{
								node<T1, T2>* mostLeft = pointer -> right;
								node<T1, T2>* mostLeftParent = pointer;
		                        
								while (mostLeft -> left != NULL)									//	то ищем самый маленький элемент в правом поддереве (самый маленький элемент в правом поддереве это самый левый потомок)
								{
										mostLeftParent = mostLeft;
										mostLeft = mostLeft->left;
								}
		 
								pointer -> key = mostLeft -> key;									//	переписываем данные этого потомка в корень
								pointer -> element = mostLeft -> element;
								mostLeftParent -> left = mostLeft -> right;							//	если у этого элемента были правые потомки то сохраняем их
								delete mostLeft;													//	и удаляем самый маленький элемент из правого поддерева (сохранили его в корень ранее)
								--_size;
								return;
							};
						};
					};

					//	аналогично как с корнем
					if ( pointer -> left == NULL && pointer -> right == NULL )					//	если нет ни одного из детей
					{
						if ( parent -> left == pointer ) parent -> left = NULL;
						else parent -> right = NULL;
						delete pointer;
						--_size;
						return;
					};

					if ( pointer -> left == NULL && pointer -> right != NULL )					//	если нет левого потомка но есть правый
					{
						if ( parent -> left == pointer ) parent -> left = pointer -> right;
						else parent -> right = pointer -> right;
						delete pointer;
						--_size;
						return;
					};

					if ( pointer -> right == NULL && pointer -> left != NULL )
					{
						if ( parent -> left == pointer ) parent -> left = pointer -> left;
						else parent -> right = pointer -> left;
						delete pointer;
						--_size;
						return;
					};

					if ( pointer -> right != NULL && pointer -> left != NULL )
					{
						if ( pointer -> right -> left == NULL )
						{
							node<T1, T2>* removed = pointer -> right;
							pointer -> element = pointer -> right -> element;
							pointer -> key = pointer -> right -> key;
							pointer -> right = pointer -> right -> right;
							delete removed;
							--_size;
						}
						else
						{
							node<T1, T2>* mostLeft = pointer -> right;
							node<T1, T2>* mostLeftParent = pointer;
	                        
							while (mostLeft -> left != NULL)
							{
									mostLeftParent = mostLeft;
									mostLeft = mostLeft->left;
							}
	 
							pointer -> key = mostLeft -> key;
							pointer -> element = mostLeft -> element;
							mostLeftParent -> left = mostLeft -> right;
							delete mostLeft;
							--_size;
						};
						return;
					};
				};
			};

работает точно правильно. поразбирайся еще в коде

[Alexander1205]

Ни фига себе кодик))...Спасибо, конечно! Если б чуть покороче, я еще не настолько крут в этом, деревья только на днях начали изучать.

[Kukurudza]

он длинный только потому что там отдельно для корня дерева и для не корня
если напишешь свой, работающий точно правильно, скинь сюда

[casekey]

деревья описаны во многих учебниках (авл, двоичные, 2-3). Например у Ахо или Вирта

[CodeNOT]

Тоже когда-то работал с деревьями, правда поиска и сбалансированными деревьями, вот тебе процедура удаления:

/*процедура удаления*/
void Delete_(tree element,TMemo * Memo1)
{
 tree HelpRb1, HelpRb2;
    if (!element || element == NIL) return; //если удаляемый эелемент пуст то ничего неделаем
    if (element->left == NIL || element->right == NIL)//если потомки удаляемого элемента пусты то инициализируем HelpRb
     {
        HelpRb2 = element;
     }
    else
    {
        HelpRb2 = element->right; //иначе присваиваем правого потока HelpRb2
        while (HelpRb2->left != NIL) //Начинаем искать самый левый жэлемент в правом поддереве
        {
                 HelpRb2 = HelpRb2->left;
        }
    }
    if (HelpRb2->left != NIL) //если самый левый эелемент не равен NIL то присваиваем его HelpRb1
    {
        HelpRb1 = HelpRb2->left;
    }
    else
    {
        HelpRb1 = HelpRb2->right;//иначе присваиваем правый эелемент
    }
    HelpRb1->parent = HelpRb2->parent; //переносим родителей
    if (HelpRb2->parent)
    {
        if (HelpRb2 == HelpRb2->parent->left)//если HelpRb2 равняется узловому листу родителя HelpRb2
        {
            HelpRb2->parent->left = HelpRb1;//то левому листовому узловому листу присваиваем HelpRb1
        }
        else
        {
            HelpRb2->parent->right = HelpRb1;//Иначе присваиваем правому
        }
    }
    else
    {
        root = HelpRb1;
    }
    if (HelpRb2 != element)
    {
        element->data = HelpRb2->data; //меняем местами ключи
    }

    if (HelpRb2->color == 0)
    {
        Balance_del(HelpRb1);//вызываем процедуру балансировки
    }
        Memo1->Lines->Add("Листовой узел удален \n");
    delete(HelpRb2);
 }
//---------------------------------------------------------------------------
/*функция поиска удаляемого узла*/
tree Find_Del_(int key)
{        //функция индиетична поиску, только вернет указатель на удаляемый эелемент
        tree find_element=root;
            while(find_element!=NIL)
            {
                if(compEQ(key,find_element->data))
                {
                        return (find_element);
                }
                else
                {
                        find_element=compLT(key,find_element->data) ? find_element->left : find_element->right;

                }
            }
            return (0);
}

[Kukurudza]

если у него дерево не сбалансировано, старания напрасны, эти функции насколько я знаю бесполезны. а в STL какой контейнер на основе дерева кто в курсе?

[CodeNOT]

http://www.cplusplus.com/reference/stl/