AVL дерево словарь - PullRequest
Новая
       4

AVL дерево словарь

5 голосов
/ 24 июля 2011

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

bool isEmpty() const - возвращает true, если пусто, false если нет

int getSize() - возвращает количество слов, которые хранятся в словаре

void insert (String word) - вставить слово в словарь, если его еще нет, иначе обновить.

boolfind(String word, WordNode & x) -возвращает true, если слово присутствует, и помещает данные в x.

void printSorted() - печатает слова в дереве в лексикографическом порядке (указано)

void remove (String word) - реализует отложенное удалениеузел

У меня есть представление о том, что я хочу сделать, и я понимаю, как работают деревья AVL.Но я полностью застрял, когда дело доходит до написания кода, может кто-нибудь помочь мне начать?

1 Ответ

2 голосов
/ 25 июля 2011

Начните с реализации простого двоичного дерева (то есть без балансировки) вместе с соответствующей программой для подсчета слов в файле. Сделайте так, чтобы у вас было что проверить. Пока не беспокойтесь о балансе; это действительно сложная часть.

Вот функция вставки (непроверенная) для простого двоичного дерева: 

/*
 * Insert a new key into a binary tree, or find an existing one.
 *
 * Return the new or existing node whose key is equal to the one requested.
 * Update *node with the new (sub)tree root.
 */
Node *insert(Node **node, String key)
{
    if (*node == NULL) {
        *node = new Node(key);
        return *node;
    }

    if (key < (*node)->key)
        return insert(&(*node)->left, key);

    if (key > (*node)->key)
        return insert(&(*node)->right, key);

    return *node;
}

После того, как у вас есть работающее и протестированное простое двоичное дерево, повторно реализуйте функцию вставки для выполнения балансировки, которая является сердцем алгоритма AVL.

Начните с знания инвариантов дерева AVL:

  • Коэффициент баланса любого узла (разница между ростом левого ребенка и ростом правого ребенка) составляет -1, 0 или + 1.
  • Обход по порядку создает словарный порядок.

Я рекомендую обратиться к Схеме вставки дерева AVL в Википедии. Он иллюстрирует четыре поворота, которые вам нужно осуществить, и где они необходимы.

Вращение необходимо, когда коэффициент баланса узла выходит за пределы диапазона - другими словами, когда разница в высоте между левым поддеревом и правым поддеревом больше 1.

Как вы определяете коэффициент баланса узла? Хорошо, подойдет любое из следующего:

  1. Добавьте элемент height в структуру Node и определите коэффициент баланса любого данного узла, вычитая рост правого ребенка из роста левого ребенка.
  2. Добавление члена balance в структуру Node. Это может быть немного сложнее понять, но это дает более простой код (я думаю).
  3. Вычислить высоту и баланс дерева путем обхода. Это неэффективно, настолько, что это побеждает цель AVL. Тем не менее, это легче понять и менее подвержено ошибкам.

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

Чтобы прояснить, что подразумевается под «высотой» и «коэффициентом баланса», вот функции для их вычисления: 

int height(Node *node)
{
    if (node == NULL)
        return -1;
    return std::max(height(node->left), height(node->right)) + 1;
}

int balanceFactor(Node *node)
{
    assert(node != NULL);
    return height(node->right) - height(node->left);
}

Для постепенного обновления высот или коэффициентов баланса потребуется бумага, карандаш, простая алгебра и здравый смысл.

Надеюсь, это поможет!

...