Вставить в красное черное дерево - PullRequest
Новая
       13

Вставить в красное черное дерево

0 голосов
/ 28 мая 2018

Я хочу вставить новый узел рекурсивно, а затем вернуть этот вновь вставленный узел из функции insertRec.Вызовы функций выглядят так: 

    void insert(int value) {       
       root = insertRec(root, null, value);
       root = insertRec(root, null, 15);
       root = insertRec(root, null, 6);
       root = insertRec(root, null, 5);
       root = insertRec(root, null, 3);
       root = insertRec(root, null, 4);
       //insertFixup(newNode);
    }

    RedBlackNode insertRec(RedBlackNode current, RedBlackNode prev, int value)  
    {
       if(current == null) {
         current = new RedBlackNode(value);
         current.p = prev;
       }
       else if(current.key < value) {
         current.right = insertRec(current.right, current, value);
       }
       else {
         current.left = insertRec(current.left, current, value);
       }
       return current;
    }

Как это сделать, при этом гарантируя, что insertRec работает правильно?Прямо сейчас, если я не верну current из insertRec, я не смогу правильно создать дерево.

1 Ответ

0 голосов
/ 28 мая 2018

В вашем коде вы не имеете дело с цветом узла, который также важен?

Обычно для красно-черного дерева вставка выполняется линейно, а не с рекурсией.Что-то вроде: 

private void insert(int value) {
        RedBlackNode parent = null;
        RedBlackNode current = root;

        while (current!=null){
            parent = current;

            if (value < current.key){
                current = x.left;
                //Here if you store the number of items on the left of a node increase it
            }           
            else{
                current = current.right;
                //Here if you store the number of items on the right  of a node increase it
            }
        }

        RedblackNode newNode=new RedBlackNode(value);

        newNode.p=parrent;

        // Here if parent is null the new node is root of the tree
        //if (parrent==null)
        //      root = newNode;  


        if (value < parent.key)
            parent.left = newNode;
        else
            parent.right = newNode;
        // Usually we add it as RED and then fix the tree to comply with red black tree rules
        newNode.color=(RED);
        fixTree(newNode);
        }

Это какой-то псевдокод, но это идея.Вы итерируете по дереву, падающему, пока не достигнете нуляЗатем вы добавляете новый узел как КРАСНЫЙ, а затем вам может понадобиться повернуть дерево, чтобы исправить цвета.

...