• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

RedBlack BST - usuwanie minimum

Object Storage Arubacloud
0 głosów
101 wizyt
pytanie zadane 27 marca 2021 w Java przez amtrax Dyskutant (9,630 p.)

Cześć, 

analizując sposób reprezentacji drzew czerwono-czarnych  w witrynie: https://algs4.cs.princeton.edu/33balanced napotkałem problem w metodzie, która usuwa minimum. 

Autorzy, dla całej struktury  zaproponowali układ, w którym czerwone odnośniki mogą być tylko po lewej stronie. 
W usuwaniu minimalnej wartości, aby zachować  zbalansowanie drzewa, zakładamy, że kolejny węzeł nie może być podwójny (tj. czarny). Jeżeli jest - wykonujemy odpowiednie transformacje Tutaj znajduje się moje pytanie. Dlaczego w kodzie sprawdzamy dwa kolejne węzły zamiast tylko jednego? 

Kod całej klasy dostępny jest tutaj: 

Metoda minimum, i wszystkie inne wymagane do jej działania, wyglądają następująco:

public void deleteMin(){
        if(isEmpty())
            return;
        root = deleteMin(root);
        }

    private Node deleteMin(Node x) {

        if(x.left  == null)
           return null;

      //Chodzi mi to ten fragment
  if(!isRed(x.left) && !isRed(x.left.left)){

           flipColors(x);
           if (isRed(x.right.left)) {
               x.right = rotateRight(x.right);
               x = rotateLeft(x);
               flipColors(x);
           }
        }

       x.left = deleteMin(x.left);
       return balance(x);
    }

 private  Node balance(Node h) {
        if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right)) flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;

        return h;
    }

    private Node rotateLeft(Node h)
    {
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }
    private Node rotateRight(Node h)
    {
        Node x= h.left;
        h.left = x.right;
        x.right = h;
        x. color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }
    private  void flipColors(Node h)
    {
        h.color = !h.color;
        h.left.color =  !h.left.color;
        h.right.color = !h.right.color;
    }

 

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 723 wizyt
pytanie zadane 2 kwietnia 2019 w C i C++ przez Zielony12 Nowicjusz (200 p.)
0 głosów
1 odpowiedź 89 wizyt
pytanie zadane 28 listopada 2023 w C i C++ przez natalia2002. Początkujący (400 p.)
0 głosów
1 odpowiedź 310 wizyt
pytanie zadane 4 lutego 2020 w C i C++ przez Kate1243 Nowicjusz (120 p.)

92,572 zapytań

141,422 odpowiedzi

319,643 komentarzy

61,959 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...