Вставка

Урок 9 из 16 курса AVL-дерево — Серия «Структуры данных» №10 на Coddy.

insert начинается как обычная вставка в бинарное дерево поиска: спускаемся вниз, сравнивая значения, переходим влево или вправо и помещаем новый узел там, где найдено пустое место (игнорируя дубликаты). Часть, относящаяся к AVL, выполняется при движении обратно вверх: после размещения узла каждый предок на пути пересчитывает свою height и проверяет свой коэффициент сбалансированности.

Если узел становится несбалансированным, то, какая сторона перевешивает и где именно оказалось новое значение, вместе определяют, какой из четырех случаев применим: left-left и right-right требуют одного поворота, в то время как left-right и right-left требуют двух — внутреннего поворота для выпрямления зигзага, за которым следует внешний.

Задание

Средне

Напишите метод insert(value) для AVLTree (использование рекурсивного вспомогательного метода — самый чистый способ). Вставьте value как в обычное BST, игнорируя его, если оно уже присутствует. При возврате по стеку вызовов пересчитайте высоту и коэффициент баланса каждого узла, и если узел не сбалансирован, примените соответствующий поворот (или пару поворотов) перед возвратом вверх по стеку.

Попробуйте сами

#include <stdio.h>
#include <string.h>
#include "avltree.h"

static void preorderValues(Node* node, int* vals, int* count) {
    if (node == NULL) {
        return;
    }
    vals[(*count)++] = node->value;
    preorderValues(node->left, vals, count);
    preorderValues(node->right, vals, count);
}

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line[256];
    while (fgets(line, sizeof(line), stdin) != NULL) {
        line[strcspn(line, "\r\n")] = '\0';
        char cmd[32];
        int arg;
        int parsed = sscanf(line, "%31s %d", cmd, &arg);
        if (parsed >= 1 && strcmp(cmd, "insert") == 0) {
            AVLTree_insert(tree, arg);
        }
        if (parsed >= 1 && strcmp(cmd, "preorder") == 0) {
            int vals[10000];
            int count = 0;
            preorderValues(tree->root, vals, &count);
            for (int i = 0; i < count; i++) {
                if (i > 0) {
                    printf(" ");
                }
                printf("%d", vals[i]);
            }
            printf("\n");
        }
        if (parsed >= 1 && strcmp(cmd, "height") == 0) {
            printf("%d\n", AVLTree_getHeight(tree, tree->root));
        }
    }
    return 0;
}