Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [С/С++] Удаление из АВЛ-дерева 
:(
    Опции темы
DarkBob
Дата 14.5.2007, 13:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 28
Регистрация: 17.3.2007

Репутация: нет
Всего: нет
Нужна ф-ция
Пробовал сам написать. Но она не на всех деревьях правильно работает:
Код

node* find(int key,node* root)
{
    node* point=root;    
    while (point!=NULL)
    {
        st->add(point);
        if (point->k==key) return point;
        if (point->k<key) point=point->r;        
        else point=point->l;
    }
    return NULL;
    
}


void del(int key,node** root)
{
    bool f; //true-del left ////false del right
    node* point,*swap,*point2,*point3;
    node* fn=find(key,*root);//find pointer for deleting elements
    if (fn!=NULL)//node has founded
    {
        if (fn->l!=NULL&&fn->r!=NULL)//two links
        {
            point = fn->l;
            st->add(point);
            while (point->r!=NULL)
            {
                point=point->r;
                st->add(point);
            }
            fn->k=point->k;
            swap = st->getel(st->size()-1); //change links of previous of deleting element
            if (swap->l==point)//deleting element is right son
            {
                swap->l=point->l;
                f=false;
            }
            else //deliting element is left son
            {
                swap->r=point->l;
                f=true;
            }
            //pop deleting element from stack
            if (st->getel(st->size())==point) st->rem();
            delete point;            
        }
        else 
        {
            if (fn->r!=NULL)//point of grawing on the right
            {
                if (st->size()>=1) if (st->getel(st->size()-1)->l==fn) f=false;
                                   else f=true;                
                //change key
                fn->k=fn->r->k;
                //change links
                fn->l=fn->r->l;
                fn->b=fn->r->b;
                point=fn->r;
                fn->r=fn->r->r;
                if (st->getel(st->size())==point) st->rem();
                delete point;
                point=NULL;
            }
            else 
            {
                if (fn->l!=NULL)//point of grawing on the left
                {
                    point = fn->l;
                    st->add(point);
                    while (point->r!=NULL) //find replacing element
                    {                
                        point=point->r;
                        st->add(point);
                    }
                    fn->k=point->k;
                    swap = st->getel(st->size()-1);
                    //deleting element is left son                    
                    if (st->getel(st->size()-1)->l==point) f=false;
                    //else right
                    else f=true;                
                    if (swap->l==point)    swap->l=point->l;
                    else swap->r=point->l;
                    //pop deleting element from the stack
                    if (st->getel(st->size())==point) st->rem(); 
                    delete point;            
                    point=NULL;
                }
                else //terminal
                {
                    if (st->getel(st->size()-1)->l==fn) 
                    {//change parent left link
                        st->getel(st->size()-1)->l=NULL;
                        f=false;
                    }
                    else 
                    {//change parent left link
                        st->getel(st->size()-1)->r=NULL;
                        f=true;                
                    }
                    if (st->getel(st->size())==fn) st->rem();
                    delete fn;
                }
            }
        }

    }
        else
        {
                return;
        }
    ///////////////start balance//////////////////
    int i=0;//counter
    int sw;//temp for swap int
    //delete root terminal
    if (st->size()==0&&st->getel(0)->r==NULL&&st->getel(0)->l==NULL)
  {
    delete *root;
    *root=NULL;
  }
  else
    while (i<=st->size())
    {
        point2=st->getel(st->size()-i);
        //shorter on the left
        if ((f==false&&i==0)||point2->l==st->getel(st->size()-i+1)&&i!=0)
        {
            switch (point2->b)
            {
                case -1:                
                    {
                        point2->b=0;                            
                    }
                    break;
                case  0: 
                    {
                        point2->b=1;
                        st->clear();
                        return;
                    }
                    break;
                case  1: 
                    {    
                        point=point2->r;                    
                        if (point2->r->b>=0)//SRL
                        {                            
                            sw = point2->k;
                            point2->k=point->k;
                            point->k=sw;
                            point2->r=point->r;
                            point->r=point->l;
                            point->l=point2->l;
                            point2->l=point;                            
                            if (point->b==0)
                            {
                                point2->b=-1;
                                point->b=1;
                                st->clear();
                                return;
                            }
                            else 
                            {
                                point->b=0;
                                point2->b=0;
                            }
                        }
                        else//DRL 
                        {//value
                            point3=point->l;
                            sw=point2->k;
                            point2->k=point3->k;
                            point3->k=sw;
                            //links
                            point->l=point3->r;
                            point3->r=point3->l;
                            point3->l=point2->l;
                            point2->l=point3;                                    
                            //balance
                            if (point3->b==-1) 
                            {
                                point3->b=0;
                                point->b=1;                                
                            }
                            else 
                            {
                                if (point3->b==1)                            
                                {                                    
                                    point3->b=-1;
                                    point->b=0;
                                }
                                else 
                                {
                                    point3->b=0;
                                    point->b=0;
                                }
                            }
                            point2->b=0;
                        }
                    }
                    break;
            }
        }
        else
        {//shorter on the right
            switch (point2->b)
            {
                case -1:                
                    {
                        point=point2->l;
                        if (point2->l->b<=0)
                        {//SRR    
                            //swap value
                            sw = point2->k;
                            point2->k=point->k;
                            point->k=sw;
                            //swap links
                            point2->l=point->l;
                            point->l=point->r;
                            point->r=point2->r;
                            point2->r=point;
                            //correct balance
                            if (point->b==0)
                            {                                
                                point->b=-1;
                                point2->b=1;
                                st->clear();
                                return;
                            }
                            else 
                            {
                                point->b=0;
                                point2->b=0;                        
                            }
                        }
                        else  
                        {//DRR
                            point3=point->r;
                            //value
                            sw=point2->k;
                            point2->k=point3->k;
                            point3->k=sw;
                            //links
                            point->r=point3->l;
                            point3->l=point3->r;
                            point3->r=point2->r;
                            point2->r=point3;                        
                            //balance
                            if (point3->b==1) 
                            {
                                point3->b=0;
                                point->b=-1;                                
                            }
                            else 
                            {
                                if (point3->b==-1)
                                {
                                    point3->b=1;
                                    point->b=0;
                                }
                                else 
                                {                                
                                    point3->b=0;
                                    point->b=0;
                                }
                            }
                            point2->b=0;
                            }                            
                        }                    
                    break;
                case  0: 
                    {
                        point2->b=-1;
                        st->clear();
                        return;
                    }
                    break;
                case  1: 
                    {
                        point2->b=0;                        
                    }
                    break;
            }

        }

        i++;
    }
}




Это сообщение отредактировал(а) DarkBob - 14.5.2007, 13:28
PM MAIL WWW ICQ   Вверх
DarkBob
Дата 14.5.2007, 13:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 28
Регистрация: 17.3.2007

Репутация: нет
Всего: нет
Посмотрел у Вирта. Там на Паскале. Переписал, получилось так:
Код
bool Balance_L (node *p)
{
 node *p1, *p2;
 bool h;
 byte b1,b2;
 switch(p->b)
 {
    case -1:    p->b=0;
            break;
    case 0:    p->b=1;
            h=false;
            break;
    case 1:         p1=p->r;
            b1=p1->b;
    if (b1 >= 0)
    {
    // однократный RR-поворот
         if (p==tree1) tree1=p->r;
         p->r=p1->l;
         p1->l=p;
             if (b1 == 0)
        {
            p->b=1; p1->b=-1; h=false;
        }
             else
        {
            p->b=0; p1->b=0;
        }
              p=p1;
         }
         else
     {
     // 2-кратный RL-поворот
          if (p1==tree1) tree1=p1->r;
      p2=p1->l;
          b2=p2->b;
      p1->l=p2->r;
      p2->r=p1;
          p->r=p2->l;
      p2->l=p;
          if (b2==1)
        p->b=-1;
      else
        p->b=0;

          if (b2==-1)
        p1->b=1;
      else
        p1->b=0;
          p=p2; p2->b=0;
     }

 }
 return h;
}

bool Balance_R (node *p)
{
 node *p1,*p2;
 int b1,b2;
 bool h;
 switch(p->b)
 {
    case 1: p->b=0;
        break;
    case 0: p->b=-1;
        h=false;
        break;
    case -1:p1=p->l;
        b1=p1->b;
          if (b1 <= 0)
        {
        //однократный LL-поворот
               if (p==tree1) tree1=p->l;
               p->l=p1->r;
        p1->r=p;
                   if (b1 == 0)
                    {
                p->b=-1;
                p1->b=1;
                h=false;
            }
                    else
            {
                p->b=0;
                p1->b=0;
            }
              p=p1;
              }
           else
        {
        //2-кратный LR-поворот
               if (p1==tree1) tree1=p1->l;
               p2=p1->r;
        b2=p2->b;
               p1->r=p2->l;
        p2->l=p1;
               p->l=p2->r;
        p2->r=p;
                if (b2==-1)
            p->b=1;
        else
            p->b=0;
        if (b2==1)
            p1->b=-1;
        else
            p1->b=0;
               p=p2;
        p2->b=0;
        }
 }
 return h;
}

bool Del (node *r)
{
// h-false
  bool h;
  if (r->r !=NULL)
    {
        h=Del(r->r);
            if (h)
            h=Balance_R(r);
    }
  else
    {
        q->k=r->k;
        r=r->l;
        h=true;
    }
  return h;
}


bool Delete (int x,node *p)
{
  node *tmp;
  bool h;
 if (p==NULL)
    h=false;
 else
    if (x < p->k)
    {
        h=Delete(x,p->l);
           if (h)
            h=Balance_L(p);
    }
     else
        if (x > p->k)
        {
            h=Delete(x,p->r);
             if (h)
                h=Balance_R(p);
        }
           else
        {
        //удаление p
          q=p;
            if ((q->r==NULL)&&(q->l!=NULL))
                {
                p=q->l;
                                /*tmp=tree1;
                                while(tmp->k!=q->k)
                                {
                                        if (tmp->k<q->k)
                                                tmp=tmp->l;
                                        else

                                delete q; */
                h=true;
            }
            else
                if (q->l==NULL)
                {
                    p=q->r;
                    h=true;
                }
                     else
                {
                    h=Del(q->l);
                           if (h)
                        h=Balance_L(p);
                }

        }
        return h;
}



Работает аналогично первой. То есть непраильно.
PM MAIL WWW ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0906 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.