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

Сбалансированное дерево - C++

Восстановить пароль Регистрация
 
Гузель23
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
28.05.2014, 19:37     Сбалансированное дерево #1
Ребят, может есть у кого код сбалансированного дерева с подробными комментариями, чтобы разобраться? выложите пож-та. спасайте..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.05.2014, 19:37     Сбалансированное дерево
Посмотрите здесь:

C++ Сбалансированное дерево (бинарное)
C++ Сбалансированное двоичное дерево поиска
C++ Сбалансированное дерево
C++ Сформировать идеально сбалансированное бинарное дерево
Идеально сбалансированное дерево C++
C++ Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Идеально сбалансированное дерево C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 19:39     Сбалансированное дерево #2
Вообще сбалансированных деревьев много. Один из самых простых - это дермаида.
Код и комментарии можно почитать тут
http://neerc.ifmo.ru/wiki/index.php?...B5%D0%B2%D0%BE
http://e-maxx.ru/algo/treap
Гузель23
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
28.05.2014, 19:44  [ТС]     Сбалансированное дерево #3
что такое сбалансированное дерево,и в вращениях в общем, вроде разобралась. хотелось бы разобранный код, если конечно возможно. кодов в интернете много, а комментариев к действиям практически нет. тема очень сложная для меня

Добавлено через 32 секунды
grikukan, что такое сбалансированное дерево,и в вращениях в общем, вроде разобралась. хотелось бы разобранный код, если конечно возможно. кодов в интернете много, а комментариев к действиям практически нет. тема очень сложная для меня
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 19:59     Сбалансированное дерево #4
Поймите, по сути сбалансированное дерево - это любое двоичное дерево, где для каждой вершины выполняется условие, что модуль разности высот поддеревьев с вершинами в ее сыне не превышает 1. Соответственно, строить его можно различными способами со своими плюсами и минусами. Самое распространенное - это красно-черное дерево(однако я не вижу смысла его писать, так как он уже есть в c++ под названием set). Помимо него есть еще например АВЛ или 2-3-4 деревья. Но все они для новичка очень сложные. Самым простым является дерамида.

Чтобы понять,как это работает, давайте для начала я расскажу как работает простое двоичное дерево.
Двоичное дерево поиска - это дерево, у каждой вершины которого левый сын мееньше ее, а првый сын - больше.Отсюда понятно, как в нем искать требуемый элемент. Просто пройдем рекурсией, и посмотрим, что если вершина равна искомому элементу, то она и ответ, если больше искомого, то пойдем в левого сына, иначе - в правого. Соответственно, понятно как добавлять вершины. Хранят его обычно при помощи рекурсивных структур, примерно так :

C++
1
2
3
4
5
struct edge
{
    long val;
    struct edge *l,*r,*p;
}
Ну это краткий ликбез, о том что такое двоичное дерево поиска.

Теперь должно примерно стать понятна суть этих статей
http://habrahabr.ru/post/101818/
Гузель23
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
28.05.2014, 20:14  [ТС]     Сбалансированное дерево #5
grikukan, я понимаю, что все это сложно для новичка, и что лучше бы начать изучать все последовательно.
проблема в том, что нужно сдать это самое авл дерево,и у меня всего лишь несколько часов, чтобы подготовиться.
поэтому я спрашиваю код, чтобы не вникая во все подробности, просто рассказать то, что есть по коду.а для этого соответственно нужен код и подробные комментарии к нему (что то типо," тут происходит ..., если это, то.." и тд)
понимаю, что очень нагло с моей стороны, уж извините, такая ситуация...
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 20:57     Сбалансированное дерево #6
Вот я расписал код из статьи на хабре
http://habrahabr.ru/post/150732/

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
struct node // структура для представления узлов дерева
{
    int key; // номер вершины
    unsigned char height; // высота поддерева
    node* left; // cсылка на левого сына
    node* right; // ссылка на правого сына
    node(int k) { key = k; left = right = 0; height = 1; } //  пустая вершина без детей
};
 
unsigned char height(node* p) // получение высоты вершины
{
    return p?p->height:0; //получим высоту следующим способом : если вершины нет, ответ 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; // высота вершины - это высота сына с макс высотой плюс 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* findmin(node* p) // поиск узла с минимальным ключом в дереве p 
{
    return p->left?findmin(p->left):p; //если есть левый сын, идем в него иначе ответ в этой вершине
}
 
node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
{
    if( p->left==0 ) // если нет левого сына удалим эту вершину
        return p->right;
    p->left = removemin(p->left); // иначе идем в левого сына
    return balance(p); //балансируем дерево
}
 
node* remove(node* p, int k) // удаление ключа k из дерева p
{
    if( !p ) return 0; // если дерево пустое, уходим
    if( k < p->key ) //если элемент меньше вершины идем в левого сына
        p->left = remove(p->left,k);
    else if( k > p->key )
        p->right = remove(p->right,k);  // если элемент больше вершины, идем в правого сына
    else //  мы пришли в вершину, которую надо удалить
    {
        node* q = p->left;
        node* r = p->right;
        delete p; //удалим физически эту вершину
        if( !r ) return q;
        node* min = findmin(r); 
        min->right = removemin(r); //правый сын минимальной вершины - это правое поддерево удаляемой без минимума
        min->left = q; // левый сын минимальной вершины - левый сын удаляемой
        return balance(min); // балансируем меньшую вершину
    }
    return balance(p); // мы ничего не нашли, балансируем дерево
}
А вообще на досуге разберите эту тему, вполне может пригодиться по жизни

Добавлено через 14 минут
Гузель23,
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.05.2014, 21:06     Сбалансированное дерево
Еще ссылки по теме:

C++ Реализовать структуру данных «сбалансированное дерево поиска»
Сбалансированное бинарное дерево. Структуры даннных C++
Идеально сбалансированное дерево C++
C++ Сбалансированное не бинарное дерево
Написать функцию, которая вводит с клавиатуры сбалансированное дерево C++

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

Или воспользуйтесь поиском по форуму:
Гузель23
0 / 0 / 0
Регистрация: 11.12.2012
Сообщений: 56
28.05.2014, 21:06  [ТС]     Сбалансированное дерево #7
grikukan, спасибо большое) выручаете
Yandex
Объявления
28.05.2014, 21:06     Сбалансированное дерево
Ответ Создать тему
Опции темы

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