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

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

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

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

08.02.2013, 18:12. Просмотров 318. Ответов 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" );
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.02.2013, 18:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос АВЛ деервья, реализация удаления (C++):

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

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

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

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

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

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

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 18:12
Привет! Вот еще темы с ответами:

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

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

Реализация добавления и удаления ComboBox пользователем - Delphi
Составьте программу,в которой при выборе элемента в выпадающем списке ComboBox,заголовок главной формы будет изменен на строку,являющеюся...

Реализация добавления/удаления элементов списка классов - C#
Доброго времени суток! Ищу совета, так как тот метод который я придумал, мне кажется, можно сделать проще, но я не знаю как. Задача: ...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

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