[Recursie] Probleem MBT de return waarde.

[Rob]

Ik heb hier een ongebalanceerde binaire boom in Java. Volgens de implementatie moet deze er zo uitzien:
SearchTree<K extends Comparable<K>, V> { }

De boom is dus een verzameling key/value pairs waarvan de key met een andere key vergeleken kan worden met de methode compareTo(T obj) (zie API).

Nu heb ik een methode containsKey(K aKey) die kijkt of een key bestaat en true of false terugkeert.

De boom zelf is recursief gedefinieerd: er is een root node met een linkernode en een rechternode, welke zelf ook weer roots kunnen zijn.

Het vinden van een key gebeurt dus ook recursief, en dan wel op de volgende manier:

PHP-code:

    public boolean containsKey(K aKey) {        
        if(key.compareTo(aKey) == 0) {
            System.out.println("Match!\n");
            return true;
        } else {
            if(left.getKey() != null) {
                System.out.println("No match. Checking left\n");
                left.containsKey(aKey);
            }
            if(right.getKey() != null) {
                System.out.println("No match. Checking right\n");
                right.containsKey(aKey);
            }
            return false;
        }
    } 


Deze methode gaat braaf alle child nodes af en returned true als die 'm vind.
Helaas lukt het mij niet om, als de key n lagen diep zit, deze n lagen omhoog te laten komen; hij returned altijd de false die aan het einde van de else staat.

Hoe laat ik die true omhoog komen, zonder dat ik gebruik maak van externe variabelen of argumenten toevoeg aan mijn methode? Als ik de return false weghaal, klaagt de compiler dat deze een return value mist, dus dat gaat in ieder geval niet...

Hier volgen alle stukken relevante code:

PHP-code:

public class SearchTree<K extends Comparable<K>, V> {
    private SearchTree<K, V> left;
    private SearchTree<K, V> right;
    
    private K key = null;
    private V value = null;
    
    public static void main(String[] args) {
        SearchTree<Integer, String> tree = new SearchTree<Integer, String>();
        tree.init();
        tree.setKey(null);
        tree.put(new Integer(10), "string 1");
        tree.put(new Integer(9), "string 2");
        tree.put(new Integer(12), "string 3");
        tree.put(new Integer(3), "string 4");
        tree.put(new Integer(65), "string 5");
        System.out.println("\nThe key exists: " + tree.containsKey(new Integer(9)) + ".");
        System.out.println(tree.toString());
        System.out.println("There are " + tree.size() + " elements in the tree");
    }

[...]

    public void init() {
        left = new SearchTree<K, V>();
        right = new SearchTree<K, V>();
        left.setKey(null);
        right.setKey(null);
    }

[...]

    public boolean containsKey(K aKey) {
        if(key.compareTo(aKey) == 0) {
            System.out.println("FOUND!\n");
            return true;
        } else {
            if(left.getKey() != null) {
                System.out.println("No match. Checking left\n");
                left.containsKey(aKey);
            }
            if(right.getKey() != null) {
                System.out.println("No match. Checking right\n");
                right.containsKey(aKey);
            }
            return false;
        }
    }

    public K getKey() {
        return key;
    }

[...]
} 


Vind de fout. >.< Mij lukt 't namelijk niet.

[WelVrolijk]

Laten we gewoon even kijken wat jouw zoekfunctie doet.

Je kijkt eerst, of de huidige knoop de gezochte sleutel bevat.
Zo ja, dan meld je succes.
Zo nee, dan komt het volgende:

Als de linkertak leeg is, sla je die over, anders doorzoek je die.
Als de rechtertak leeg is sla je die over, anders doorzoek je die.
Uiteindelijk meldt je altijd mislukking!

-------------------------------------

De fout zit dus in dat tweede gedeelte.
Je wilt daar enkel mislukking melden indien het daadwerkelijk is mislukt!

In feite ben je klaar, zodra je de gezochte sleutel ergens vindt.
Dus het tweede deel zou je bijvoorbeeld kunnen vervangen door:

Als de linkertak leeg is, sla je die over.
Zo niet: Doorzoek linkertak, indien gevonden meld je succes (return true).

Als de rechtertak leeg is, meldt je mislukking (return false).
Zo niet, dan doorzoek rechtertak en geef het resultaat door ( return right.containsKey(aKey);)

[Rob]

Het is gelukt. ^^

Ik heb gedaan door de uitvoer van de statement in de ifexpressie te doen en true te returnen als de ifstatement true is...

PHP-code:

    public boolean containsKey(K aKey) {
        if(key == null) {
            //For when we start the tree. We want to add whatever the first
            //element is.
            return false;
        }
        
        if(key.compareTo(aKey) == 0) {
            return true;
        } else {
            if(!left.isSentinel()) {
                if(left.containsKey(aKey)) {
                    return true;
                }
            }
            if(!right.isSentinel()) {
                if(right.containsKey(aKey)) {
                    return true;
                }
            }
            return false;
        }
    } 


En dat werkt.

Which reminds me: Hoe itereer je netjes door een boom? Die boom is dus af, maar nu moet ik 'm iterabel maken (SearchTree implements Iterable en de SearchTreeIterator class implements Iterator).

Ik kom er alleen niet echt uit... Ik kan helemaal naar links, helemaal naar rechts, maar niet netjes door de hèle boom. >.<

[WelVrolijk]

"Hoe itereer je netjes door een boom?"

Bij een binaire boom zijn er 3 voor de hand liggende manieren om door de boom te lopen.
1 - Eerst de knoop zelf, dan de linkertak, en tenslotte de rechtertak.
2 - Eerst de linkertak, dan de knoop zelf, en tenslotte de rechtertak.
3 - Eerst de linkertak, dan de rechtertak, en tenslotte de knoop zelf.
Dat is dus een keus die je zult moeten maken.

---------

Zo'n Iterator houdt blijkbaar bij, hoever hij is. Dat zal de Iterator die je zelf schrijft, dus ook moeten bijhouden.
Dat wil zeggen:
- je moet bijhouden of je in de linkertak zit, of in de rechtertak, of in de knoop zelf.
- indien je in een van beide takken zit, zul je de in-eerste-instantie-opgevraagde-Iterator dus steeds moeten hergebruiken, totdat je de hele tak afgehandeld hebt.

-----------

Als jouw Iterator de remove() moet ondersteunen, zul je natuurlijk moeten verzinnen hoe je dat doet indien het laatst-opgevraagde-element de knoop zelf is...
(Als je in een van de takken zat, kun je volgens mij gewoon de remove() van de Iterator-die-je-gebruikt-voor-de-betreffende-tak aanroepen)

[Rob]

In-, post- of preorder boeit weinig. Het staat tenminste niet aangegeven. =\

remove() hoeft niet ondersteunt te worden.

Nu zit ik dus te denken. Ik begin bij parent (die moet ik bijhouden). Zolang mijn parent een linkernode heeft, zet ik mijn huidige node op de linkernode van de parent. Heeft de huidige node geen linker kind, dan return ik de waarde daarvan en zet ik de waarde van de node in een Vector om zo markeren dat ik er al ben geweest. Dan kijk ik of de parent een rechterkind heeft. Zoja, zet huidige node op de rechter van de parent. Dan kijk ik of dat rechterkind linker kinderen en rechterkinderen heeft, etc.. Wanneer alle kinderen van de parent zijn gedaan, return ik de parent en kijk ik, mits die er is, naar de parent van de parent.

Ik heb dus een huidige node nodig (de node waarmee we nu bezig zijn), een parent, een linker en een rechter. Aan het begin is de huidige node de allereerste...

Ik kan 't alleen niet echt naar nuttige pseudocode vertalen. >.< Even denken...


Ik loop dus nu vast op het punt wanneer ik terug omhoog wil. Op een gegeven moment wordt je currentnode de parent node. En de parentnode de parent van de parent.

Maar de parent van de parent hou ik niet bij. Zou ik dat wel moeten doen? Of bewaard het systeem, zonder dat ik het zie, de parent van de parent? >.<

Of moet ik in mijn iterator een recursieve methode toevoegen die dit uitwerkt?

[WelVrolijk]

Volgens mij hoef je zelf niet door die linkertak heen te lopen.


Je hoeft alleen maar telkens wanneer jouw next() wordt aangeroepen, de volgende waarde door te geven.

Of iets concreter:
- Als je aan die linkertak toe bent, laat je die tak gewoon een iterator genereren. Je vraagt de next() van die iterator op, en die geef je als resultaat omhoog (nadat je die iterator onthouden hebt, natuurlijk).
- Voor de rechtertak geldt later hetzelfde verhaal.
Daarnaast is er een moment dat je de knoop zelf moet doorgeven.
Aangezien niet is voorgeschreven of het pre-order, in-order of post-order is, zul je die keuze zelf moeten maken.
- Als je aan de knoop zelf toe bent, geef je die als resultaat omhoog (nadat je onthouden hebt dat daarmee de knoop zelf verwerkt is, natuurlijk).

De enige variabelen die je (volgens mij) nodig hebt zijn:
- een variabele die aangeeft of je in de linkertak bezig bent, of in de knoop zelf, of in de rechtertak.
- een variabele om (indien je in een van beide takken zit) de iterator van die tak te onthouden.

Waar je nu precies bent in die tak, hoeft jouw iterator niet te onthouden. Dat onthoudt de iterator van die tak namelijk al.

[Rob]

Het is gelukt!
Met een postorder iteratie, weliswaar. Maar dat mag de pret niet drukken.

[Rob]

...Typisch. XD Ik zeg zo dat het gelukt is, komt de docent met de mededeling dat de boom, vanwege de moeilijkheid, niet iterabel hoeft te zijn. Nouja, pluspunten voor mij omdat het mij wel gelukt is, nu.

Anyway, die SearchTree moet nu een weight balanced search tree worden. Die WBSTree moet erven van de SearchTree (dmv extends). Nu had ik twee vraagjes:

Gegeven de volgende (ongebalanceerde) boom:

a
 \
  b
   \
    c

Om deze gebalanceerd te maken doe je een single left rotation. Volgens het algoritme doe ik dan dit:
- Verwissel b en a
- Geef a b's linkerkind als rechterkind (Overschrijf je c dan niet als b WEL een linkerkind heeft?)
- b neemt a (plus zijn subboom) als zijn linkerkind

Mijn vraag ging dus als eerste over dat tweede punt (bijvoorbeeld bij de boom:

   a
  / \
-a   b
      \
       c

Waarbij -a kleiner is dan a. Ik dat geval krijgt a dus -a als rechterkind, maar wat gebeurt er met c? Schuift die als het ware 1 niveau naar beneden, of gebeurt er iets anders?

De tweede vraag: Ik moet dus een methode hebben om de grootste en de kleinste boom te pakken te krijgen. De SearchTree bevat left en right (van het type SearchTree<K,V>) en deze zijn protected. Mijn WBSTree kan er gewoon bij.
Maar nu zit ik eigenlijk met het probleem dat ik een SearchTree niet zomaar naar een WBSTree kan casten (ik krijg een ClassCastException).
En ik moet de grootste en kleinste subboom te pakken krijgen. Ik moet dus een methode largest en smallest hebben.
Alleen: als ik 'm in WBSTree definieer en recursief gebruik, zit ik dus met left en right die SearchTrees zijn en de methode niet kennen.
Als ik in SearchTree de methode uitwerk, kan ik het resultaat niet casten naar een WBSTree vanwege die Exception.

Hoe los ik dat op? =s

[WelVrolijk]

Tja, hier zul je me dus eerst wat achtergrond-informatie moeten geven.
Het is allemaal een beetje lang geleden.


De term "weight balanced tree" doet mij denken aan een boom waarbij voor iedere knoop geldt dat beide takken evenveel knopen bevatten (plus of min 1).

Maar dan begrijp ik jouw tweede voorbeeld niet (die boom met 4 knopen).
De linkertak heeft 1 knoop, en de rechter 2. Beter kun je het volgens mij niet verdelen ...


De term "single left rotation" is ook een beetje vaag voor mij.
Ik heb even gegoogled, en ik zie vooral verwijzingen naar AVL-bomen.
Ik meen me echter te herinneren, dat die niet weight-balanced waren, maar dat het daarbij om de diepte ging.
Maar ja, dat is voor mij meer dan 25 jaar geleden ...

(Ik ga zodirect nog even kijken naar mijn zoek-resultaten, denk ik).

[WelVrolijk]

Rob schreef op 10-05-2007 @ 23:34 :
... een single left rotation. Volgens het algoritme doe ik dan dit:
- Verwissel b en a
- Geef a b's linkerkind als rechterkind (Overschrijf je c dan niet als b WEL een linkerkind heeft?)
- b neemt a (plus zijn subboom) als zijn linkerkind

Mijn vraag ging dus als eerste over dat tweede punt (bijvoorbeeld bij de boom:

   a
  / \
-a   b
      \
       c

Waarbij -a kleiner is dan a. Ik dat geval krijgt a dus -a als rechterkind, maar wat gebeurt er met c? Schuift die als het ware 1 niveau naar beneden, of gebeurt er iets anders?

c blijft gewoon het rechterkind van b.
-a blijft het linkerkind van a.
In dit geval krijgt a wederom *geen* rechterkind, omdat b geen linkerkind had.
Het resultaat wordt dus:

     b
    / \
   a   c
  /
-a

----------------------------

Als b *wel* een linkerkind had gehad, zou het uitgangspunt er zo uitzien:

   a
  / \
-a   b
    / \
  ab   c

Het resultaat van een single left rotation zou dan zijn:

     b
    / \
   a   c
  / \
-a  ab

en het resultaat is dus nog steeds ongebalanceerd.

Blijkbaar moet je in dit gevaal eerst een single right rotation toepassen op de rechter subtree, en pas daarna een single left rotation bovenin.
Dat ziet er dus als volgt uit:

   a
  / \
-a   b
    / \
  ab   c


   a
  / \
-a  ab
      \
       b
        \
         c


    ab
    / \
   a   b
  /     \
-a       c

[WelVrolijk]

Als ik het goed begrijp, werkt zo'n single left rotation dus als volgt.

Noem de top van de tree even a.
Noem de top van de rechtertak van a even b.


De linkertak van a blijft gewoon linkertak van a.
De rechtertak van b blijft gewoon rechtertak van b.

De linkertak van b wordt rechtertak van a (dat was eerst b).
a wordt linkertak van b (de oude linkertak hebben we zojuist naar rechtertak van a).
b wordt top van de tree (was eerst a).


Maar ik kan het natuurlijk best wel verkeerd begrepen hebben.
Reken het dus eerst zelf maar even na ...

[Rob]

Ik zie net dat mijn tweede voorbeeld wèl weight-balanced was.

En ja, ik vond het ook al raar: We moeten een weight-balanced search tree maken die AVL methoden heeft. =\

Ik lees later de rest wel even en geef dan wel antwoord en dan reken ik na, e.d.. Truste!