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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
BeRS777
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 9
#1

АВЛ деервья, реализация удаления - C++

08.02.2013, 18:12. Просмотров 309. Ответов 0
Метки нет (Все метки)

всем привет!
кто может помочь реализовать удаление всех четных элементов в АВЛ-дереве? сижу уже битый час пытаюсь и как-то безуспешно...

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include<iomanip>
 
using namespace std;
 
struct node // структура для представления узлов дерева
{
    int key;
    unsigned char height;
    node* left;
    node* right;
    node(int k) { key = k; left = right = 0; height = 1; }
};
 
unsigned char height(node* p)
{
    return p?p->height:0;
}
 
int bfactor(node* p)
{
    return height(p->right)-height(p->left);
}
 
void fixheight(node* p)
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr?hl:hr)+1;
}
 
node* rotateright(node* p) // правый поворот вокруг p
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}
 
node* rotateleft(node* q) // левый поворот вокруг q
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}
 
node* balance(node* p) // балансировка узла p
{
    fixheight(p);
    if( bfactor(p)==2 )
    {
        if( bfactor(p->right) < 0 )
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if( bfactor(p)==-2 )
    {
        if( bfactor(p->left) > 0  )
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // балансировка не нужна
}
 
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
    if( !p ) return new node(k);
    if( k<p->key )
        p->left = insert(p->left,k);
    else
        p->right = insert(p->right,k);
    return balance(p);
}
 
node* remove( node* p ) 
{
    if( !p ) return 0;
    if(  !( p->key % 2 ) )
    {
        p->left = remove(p->left);
        p->right = remove (p->right);
    }
    else 
    {
        node* q = p->left;
        node* r = p->right;
        delete p;
        q = r->left;
        return balance(r);
    }
    return balance(p);
}
 
void print( node * p, int s )
{
    if( p != NULL )
    {
        print( p->left, s + 1 );
        cout << setw( s * 10 ) << p->key << endl;
        print( p->right, s + 1 );
    }
}
 
void main()
{
    setlocale( LC_ALL, "rus" );
    node *root;
    int w;
    root=NULL;
    cout << "Введите число: ";
    cin >> w;
    while( !feof(stdin) )
    {
        root=insert(root, w);
        cout << "Введите число: ";
        cin >> w;
    }
    cout << "Дерево" << endl;
    print( root, 3 );
    cout << endl;
    remove( root );
    cout << "Дерево после удаления четных" << endl;
    print ( root, 3 );
    system( "pause" );
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 18:12     АВЛ деервья, реализация удаления
Посмотрите здесь:

Реализация ф-ции удаления элемента из списка - C++
Здравствуйте. У меня задание - создать список и интерфейс работы с ним (1-создание списка, 2 вывод списка, 3 удаление элемента, 4 звпись в...

АВЛ-дерево - C++
Из входной последовательности символов построить АВЛ-дерево без повторов. Найти в нем узел, относительно которого будет максимальная...

АВЛ дерево - C++
Здравствуйте. Я начинающий программист и мне нужна помощь. Сейчас пытаюсь понять тему АВЛ деревьев и попробовала забить этот код, но к...

АВЛ дерево и коллизия хэша - C++
До некоторых пор думал, что красно-черное и авл деревья, да и вообще любые структуры, позволяющие сделать нечто вида: printf(&quot;%d\n&quot;,...

Высота авл дерева - как считать? - C++
Добрый вечер. Забавно. Предположим, что пустой указатель равен -1, высота пр - высота лев. А как посчитать высоту авл дерева с...

Комменты к реализации Красно-черного и АВЛ дерева - C++
Люди добрые помогите разобрать и по возможности написать комментарии к этим 2м кодам .. Это коды Реализации Красно-черного и АВЛ дереве и...

Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? - C++
Доброго времени суток. Нужна помощь. В АВЛ-дереве надо найти самую короткую ветвь и удалить ее. Я могу удалить только узел по ключу (ну...

Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить - C++
Добрый день, читал на хабре про АВЛ-деревья и возник один вопрос вот ссылка на статью http://habrahabr.ru/post/150732/ Не могли бы Вы...

Функция удаления на С - C++
Помогите исправить ошыбки в удалении вот полный код: #include &lt;stdio.h&gt; #include&lt;iostream.h&gt; #include &lt;conio.h&gt; void Prosm();...

Удаления со строки подстроку! - C++
Здраствуйте! Дано подстроку...найти и уничтожить его со всех слов в строке... помогите плиз....

Функция удаления из списка - C++
помогите разобраться почему не работает функция удаления? плз #include &lt;iostream&gt; using namespace std; class Node{ public: ...

Удаления в Map по ключу - C++
Столкнулся с проблемой пытаюсь удалить по ключу в map и по итератору но нечего не происходит. вот код map&lt;string, int&gt;...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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