Как реализовать дерево AVL без родительского указателя?

Question

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

Но мне интересно, есть ли другой способ сделать это без использования указателя родителя?например, структура узла:

struct Node{
int data;
struct Node *lchit, *rchild; //*parent;
};

Answer 1

Вы можете поддерживать стек в текущем узле, пока вы пересекаете дерево

stack<Node*> nodeStack;

Когда вы переходите в новый узел, добавьте его в стек, и тогда у вас будет свое происхождение.Когда вы закончите обработку узла, извлеките его из стека.

** Правка **

Разработка для комментария выравнивания:

struct Node {
    int data;
    struct Node *children, *parent
};

при создании дочерних элементов, выполнитеэто так:

node.children = new Node[2]; or node.children = malloc(sizeof(Node) * 2);
node.children[0].parent = node;
node.children[1].parent = node;

Answer 2

Если я правильно помню домашнюю работу по структурам данных:

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

• -1: левое поддерево узла - это уровень выше правого (левый-тяжелый)
• 0 узел сбалансирован;или
• 1 правое поддерево выше (правое тяжелое).

Функция вставки (поддерево узла) возвращает логическое значение, которое имеет значение true, если при вставке высота поддерева увеличилась.Вы обновляете коэффициент баланса и перебалансируете дерево по мере того, как вы возвращаетесь из рекурсивных вызовов insert ().

Вероятно, это лучше всего объяснить на нескольких примерах:

Если текущий узел имеет коэффициент баланса -1 , вы вставляете в поддерево right , и вставка (rchild) возвращает true , вы:

1. обновить коэффициент баланса текущего узла до 0 - левое поддерево было выше перед вставкой, а высота правого поддерева увеличилась, поэтому теперь они имеют ту же высоту;и
2. return false - высота более мелкого дерева увеличилась, поэтому высота текущего узла остается неизменной

---

Если вы вставляете в либо поддерево, и insert (…) возвращает false :

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

---

Если коэффициент баланса текущего узла равен 0 , вы вставляете в поддерево left , а insert (lchild) возвращает true :

1. коэффициент баланса изменяется на -1 - поддеревья были одинаковой высоты перед вставкой, а вставка сделала левое более высокое
2. return true

(Аналогично, если вставить правильное поддерево, коэффициент баланса изменится на 1.)

---

Если коэффициент баланса текущего узла равен -1 , вы вставляете в поддерево left , а insert (lchild) возвращает true:

Коэффициент баланса изменится на -2, что означает, что вы должны перебалансировать узел, выполнив соответствующее вращение.Я признаю, что нарисую пробел в том, что каждое из четырех вращений будет делать с коэффициентом баланса, и что вернет insert (current), надеюсь, предыдущие примеры объясняют подход к достаточному отслеживанию баланса узлов.

Answer 3

Использование двойных указателей (или ссылок на указатели, как вы просили C ++) должно полностью устранить необходимость в родительских указателях.

typedef struct Node {
    int value;
    int height;
    struct Node *left;
    struct Node *right;
} Node;

int height(Node *node) {
    return (node == NULL) ? -1 : node->height;
}

void insert(Node * & node, int value) {
    if (node == NULL) {
        node = new Node();
        node->value = value;
    } else if (value < node->value) {
        insert(node->left, value);
        if (height(node->left) - height(node->right) == 2) {
            if (value < note->left->value) {
                singleRotateWithLeftChild(node);
            } else {
                doubleRotateWithLeftChild(node);
            }
        }
    } else if (value > node->value) {
        // Symmetric case
    }

    node->height = 1 + max(height(node->left), height(node->right));
}

Answer 4

Поскольку нет полной реализации этого вопроса, я решил добавить его.Это можно сделать с помощью рекурсивного insert, возвращающего текущий узел.Итак, вот код:

typedef struct node
{
    int val;
    struct node* left;
    struct node* right;
    int ht;
} node;

int height(node* current) {
    return current == nullptr ? -1 : current->ht;
}

int balanceFactor(node* root) {
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    return leftHeight - rightHeight;
}

int calcHeight(node* n) {
    int leftHeight = height(n->left);
    int rightHeight = height(n->right);

    return max(leftHeight, rightHeight) + 1;
}

node* insert(node * root,int val) {
    /**
    First, recusively insert the item into the tree
    */
    if (root == nullptr) {
        root = new node();
        root->val = val;
    } else if (root->val < val) {
        root->right = insert(root->right, val);
        //the height can increase only because of the right node
        root->ht = std::max(root->ht, root->right->ht + 1);
    } else {
        root->left = insert(root->left, val);
        //the height can increase only because of the left node
        root->ht = std::max(root->ht, root->left->ht + 1);
    }

    //after insertion on this depth is complete check if rebalancing is required

    // the right subtree must be rebalanced
    if (balanceFactor(root) == -2) {
        node* r = root->right;
        node* rl = r->left;
        // it's a right right case
        if (balanceFactor(r) == -1) {
            r->left = root;
            root->right = rl;
            root->ht = calcHeight(root);
            r->ht = calcHeight(r);
            //return new root
            return r;
        } else { // it's a right left case
            node* rlr = rl->right;
            node* rll = rl->left;
            rl->left = root;
            root->right = rll;
            rl->right = r;
            r->left = rlr;

            root->ht = calcHeight(root);
            r->ht = calcHeight(r);
            rl->ht = calcHeight(rl);
            return rl;
        }
    } else if (balanceFactor(root) == 2) {
        node* l = root->left;
        node* lr = l->right;
        // it's a left left case
        if (balanceFactor(l) == 1) {
            l->right = root;
            root->left = lr;
            root->ht = calcHeight(root);
            l->ht = calcHeight(l);

            //return new root
            return l;
        } else { // it's a left right case
            node* lrl = lr->left;
            node* lrr = lr->right;
            lr->right = root;
            lr->left = l;
            root->left = lrr;
            l->right = lrl;

            root->ht = calcHeight(root);
            l->ht = calcHeight(l);
            lr->ht = calcHeight(lr);

            return lr;
        }
    }

    return root;
}

Answer 5

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

Для кодировки C ++ см. Функцию удаления члена (в настоящее время в строке 882) в https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h.

Для кодирования C см. Функцию, имя которой генерируется вызовом макроса L __ (remove) в http://wkaras.webs.com/gen_c/cavl_impl_h.txt.

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

Если вы хотите удалить узел, идентифицированный указателем узла, а не уникальным ключом, то, возможно, это будет быстрее, я думаю, с родительскими указателями.