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

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

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

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

08.02.2013, 18:12. Просмотров 297. Ответов 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++
Как в АВЛ-дереве найти самую короткую ветвь и удалить ее? C++
Функция удаления на С C++
Не выполняется функция удаления C++
Высота авл дерева - как считать? C++
АВЛ дерево и коллизия хэша C++
C++ АВЛ-дерево
C++ Удаления в Map по ключу
Комменты к реализации Красно-черного и АВЛ дерева C++
C++ Добрый день, читал на хабре про АВЛ-деревья и хотелось бы кое-что уточнить
Реализация ф-ции удаления элемента из списка C++
АВЛ дерево C++

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

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

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