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

Написать структуру данных — сбалансированное дерево AVL - C++

Восстановить пароль Регистрация
 
Dimon1994
Сообщений: n/a
22.03.2014, 22:09     Написать структуру данных — сбалансированное дерево AVL #1
Нужно написать структуру данных - сбалансированное дерево AVL. Не получается с удалением (не работает именно удаление листа), на возврате из рекурсии происходит перебалансировка и получается зацикливание некоторого узла, что не так?

C++ (Qt)
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
    
 
node <T> * removeMin(node <T> * r) {
    if (r->left == nullptr)
        return r->right;
    r->left = removeMin(r->left);
    return balance(r);
}
 
template <typename T>
inline node <T> * AVL_tree <T> :: remove(node <T> * r, const T & k) {
    if (r == nullptr)
        return nullptr;
    if (k < r->data)
        r->left = remove(r->left, k);
    else if (k > r->data) 
            r->right = remove(r->right, k);
    else {
        node <T> * lf = r->left;
        node <T> * ri = r->right;
        delete r;
        if (ri == nullptr)
            return lf;
        node <T> * min = findMin(ri);
        min->right = removeMin(ri);
        min->left = lf;
        return balance(min);
    }
    return balance(root);
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2014, 22:09     Написать структуру данных — сбалансированное дерево AVL
Посмотрите здесь:

C++ Сбалансированное дерево (бинарное)
C++ Сбалансированное дерево
C++ AVL - дерево, ошибка линковки <LNK2001>
C++ Сбалансированное дерево
C++ Ошибка компиляции. AVL-дерево
Определить, является ли дерево AVL деревом C++
C++ Реализовать структуру данных «сбалансированное дерево поиска»
Идеально сбалансированное дерево C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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