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

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

15.05.2015, 11:49. Просмотров 3882. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.05.2015, 11:49
Ответы с готовыми решениями:

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

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

Красно черное дерево. Добавление и балансировка элементов. Исправить ошибку
Всем доброго времени суток!!Нужна ваша помощь;) Необходимо исправить ошибку в реализации...

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

1
84 / 80 / 31
Регистрация: 18.11.2013
Сообщений: 390
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.05.2015, 12:00

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

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

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

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

Балансировка двоичного дерева
В файле дана последовательность целых чисел. Построить из них двоичное дерево поиска . Разработать...


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

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

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