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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Разбор кода: fscanf и форматная строка http://www.cyberforum.ru/cpp-beginners/thread1191640.html
Добрый день! Необходимо разобраться в коде, в нем есть такие строки: h = fscanf(baza, "%*s %d", &kod1); h = fscanf(baza, "%*c %d %*c %d %*c %d", &t.tm_mday, &t.tm_mon, &t.tm_year); j =...
C++ Подскажите пожалуйста в чем ошибка?(С++,структуры,стек) Подскажите пожалуйста, в чем ошибка При считывании из файла единственной записи 5группа "Anokhin Viktor petrovich 4 5 3 http://www.cyberforum.ru/cpp-beginners/thread1191630.html
Класс TGoods, создающий тип – товар C++
Задание вот: Объявите класс TGoods, создающий тип – товар. Элементы – данные класса – наименование товара, год производства. Предусмотрите конструкторы класса: по умолчанию; получающий...
C++ Структура "Студент"
Помогите пожалуйста разобраться в программе Тест. // test.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <math.h> #include...
C++ Разделение классовой функции из заголовка в .h + .cpp http://www.cyberforum.ru/cpp-beginners/thread1191582.html
Пытаюсь разобрать заголовок на IAI.h + IAI.cpp столкнулся с функцией которую тупо не знаю как разбить правильно. Помогитепожа! :D friend ostream& operator<<(ostream& os, const sto& sto) {...
C++ Случайные блуждания с переменным шагом не могу разобраться в задании, объясните матмоделью или алгоритмом, может кто то программой поможет Случайные блуждания с переменным шагом. Рассмотрите одномерное случайное блуждание со всеми... подробнее

Показать сообщение отдельно
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
28.05.2014, 20:57
Вот я расписал код из статьи на хабре
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,
1
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru