Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
Дана18
0 / 0 / 0
Регистрация: 10.10.2014
Сообщений: 121
#1

Балансировка дерева

15.05.2015, 11:49. Просмотров 1377. Ответов 1
Метки нет (Все метки)

Как сделать балансировку бинарного дерева поиска?
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
131
132
133
134
135
template <class T, class I> class node
{
private:
    T x; //ключ
    I info;//информация
    node* LL; //left link
    node* RL; //right link
public:
    node(){ x = 0; LL = 0; RL = 0; };
    ~node()
    {
        if (LL) LL->~node();
        if (RL) RL->~node();
        if (LL) { delete LL; LL = 0; }
        if (RL) { delete RL; RL = 0; }
    }
    void putx(T new_x, I new_info){ this->x = new_x; this->info = new_info; }
    void null_leftlink(){ this->LL = 0; }
    void null_rightlink(){ this->RL = 0; }
    void add(T new_x, I new_info)
    {
        if (LL && (new_x < x)) LL->add(new_x, new_info);
        if (RL && (new_x > x)) RL->add(new_x, new_info);
 
        if (!LL && (new_x < x))
        {
            node* N = new node;
            N->x = new_x;
            N->info = new_info;
            N->LL = 0;
            N->RL = 0;
            LL = N;
        }
        if (!RL && (new_x > x))
        {
            node* N = new node;
            N->x = new_x;
            N->info = new_info;
            N->LL = 0;
            N->RL = 0;
            RL = N;
        }
    }
    void print(int tab)
    {
        if (RL) RL->print(tab + 1);
        for (int i = 1; i != tab; i++)cout << "  "; cout << this->x << "-" << this->info << endl;
        if (LL) LL->print(tab + 1);
    }
    void del_all()
    {
        if (LL) LL->del_all();
        if (RL) RL->del_all();
        if (LL) { delete LL; LL = 0; }
        if (RL) { delete RL; RL = 0; }
    }
    void del(T x_to_del)
    {
        if (LL) LL->del();
        if (RL) RL->del();
        //не дописано еще.
    }
    I get(T getx)
    {
        if (getx == x) return info;
        if (LL && (getx < x)) return LL->get(getx);
        if (RL && (getx > x)) return RL->get(getx);
    }
};
 
template <class T, class I> class tree
{
private:
    node <T, I>* link;
public:
    tree(){ link = 0; };
    ~tree(){ if (link)link->~node<T, I>(); delete link; link = 0; };
    void add(T new_x, I new_info)
    {
        if (link) link->add(new_x, new_info);
        else
        {
            node<T, I>* N = new node<T, I>;
            N->putx(new_x, new_info);
            N->null_leftlink();
            N->null_rightlink();
            link = N;
        }
    };
    void print(){ if (link)link->print(1); else cout << "No tree existing\n"; }
    void del_all(){ if (link) link->del_all(); delete link; link = 0; }
    void del(int x){ if (link)link->del(x); };
    I get(T x){ if (link) return link->get(x); else cout << "No elements existing\n"; }
};
 
int main()
{
    system("cls");//clear screen
    tree <int, char> *T = new tree <int, char>; // создание дерева
    //menu
    int choos = 0;
    const int exit = 6;
    while (choos != exit)
    {
        cout <<"There is a menu for you to choos:\n"
            "  1-add;\n"
            "  2-use destructor;\n"
            "  3-print;\n"
            "  4-delete all;\n"
            "  5-get element;\n"
            "  6-exit;\n"
            "enter-> \n";
        cin >> choos;
        switch (choos){
        case 1: {
                    int key; //ключ.
                    char info; //значение
                    cout << "enter key: "; cin >> key;
                    cout << "enter int value: "; cin >> info;
                    T->add(key, info);
                    break;
        }
        case 2: T->~tree(); break;
        case 3: T->print(); break;
        case 4: T->del_all(); break;
        case 5:{
                   cout << "what is key of element? ";
                   int key = 0;
                   cin >> key;
                   cout << "there it is: " << T->get(key) << endl;
                   break; }
        default: if (choos != exit)cout << "wrong int value " << choos << endl;
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.05.2015, 11:49
Ответы с готовыми решениями:

Балансировка бинарного дерева
Попалась одна на вид простая задача. Код написал, но не проходит 10 тестов из...

Балансировка игроков
Здравствуйте. Начинал изучение этого языка программирования и решил сделать для...

Запись бинарного дерева в файл и восстановление из него этого дерева
Задача такая: есть бинарное дерево. Каждый элемент дерева содержит 3 указателя...

Написать шаблон бинарного дерева с функцией распечатки дерева
Не понимаю, что от меня хотят. Дано такое задание: Написать шаблон бинарного...

Вывод бинарного дерева на экран в виде "дерева"
основная задача: подсчет количества листьев. проблема: при просмотре хочу...

1
Krock21rus
74 / 74 / 27
Регистрация: 18.11.2013
Сообщений: 373
Завершенные тесты: 2
15.05.2015, 12:00 #2
Кликните здесь для просмотра всего текста

Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, то есть чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность.

В вырожденном случае может оказаться, что все левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве.

Для балансировки дерева применяется операция «поворот дерева». Поворот налево выглядит так:

AVL LR.GIF

было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.
Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.

Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или −1) влияние на глубины всех затронутых поддеревьев.

Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «красно-чёрное дерево» и АВЛ.

Оба они требуют дополнительной информации в узлах — 1 бит у красно-черного или знаковое число у АВЛ.

Красно-черное дерево требует <= 2 поворотов после добавления и <= 3 после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого).

АВЛ-дерево требует <= 2 поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).

Википедия, не?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.05.2015, 12:00

Балансировка AVL дерева
Здравствуйте. У меня возникла такая проблема, не могу сбалансировать AVL...

створення дерева
погогите пожалуста треба створити дерево-формулу за постфиксною формулою. И...

Построение В*-дерева
Задание: Построение B* дерева, добавление вершин и балансировка в случае...


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

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

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