Van egy könyvem, amely nagyon rosszul magyarázza el a bináris keresőfa mögötti elméletet. Tudom, hogy van valami a bal és a jobb oldali gyermek sorrendjében, de még mindig nem tudom elképzelni, hogy az egyik nagyobb, mint a másik előző szint.
Vegyük például ezt a karakterláncfát:
(elnézést a festésért) ez a példa közvetlenül a könyvemből származik :)
Valaki elmagyarázná nekem a parancsot? mi a logika e mögött?
Karen csomópont van a példafában, akkor ez technikailag nem BST, mert a duplikált csomópontok nem megengedettek. 26.12.2012 A BST-ben minden csomópontnak legfeljebb egy bal és egy jobb gyermeke van. Egy adott csomópont bal oldalán minden csomópont kisebb nála, és egy adott csomópont jobb oldalán minden csomópont nagyobb nála. Ennek egyik következménye az, hogy nem lehetnek ismétlődő értékek, ezért nem vagyok biztos abban, hogy ez a példa pontosan így van-e a könyvben.
A példában a karakterláncok ábécé sorrendben vannak. Példaként a gyökércsomópontot véve Bob Karen elé kerül, így Bob Karen balján megy. Tom Karen után jön, így Tom Karen jobbján megy. Ha a fa egészét nézzük, láthatjuk, hogy Karen bal oldalán minden csomópont (Bob, Alan, Ellen) Karen elé kerül ábécé sorrendben, és Karen jobb oldalán minden csomópont (Tom, Wendy) Karen után következik ábécé sorrendben. Ez a minta ugyanaz, függetlenül attól, hogy melyik csomópontot nézi.
Bármely csomópont (például Karen – a gyökér – például) minden csomópontja a bal oldali részfában (Bob, Alan, Ellen) lexikográfiailag kisebb, mint Karen, és minden csomópont a jobb oldali részfában (Tom, Wendy) ) nagyobb, mint Karen.
A 2. Karen ne legyen ott, erre @mellamokb is rámutat a kommentekben.
Mint ilyen, binárisan kereshet ebben a fában O(log N) időben, mint egy rendezett tömbben.
Karen, majd a Karen-tól balra Bob, majd a Bob-től jobbra Tom, akkor az első feltételt kielégíti, a másodikat nem. A BST-t úgy kell definiálni, hogy a bal/jobb részfa összes csomópontja kisebb/nagyobb, mint a szülőcsomópont. 26.12.2012 A te példádban az egyes nevek első szimbólumának sorrendjét jelentették.
Ha látja, a névsorrend balról jobbra az ABC első karakterétől az utolsóig terjed.
Ezenkívül van egy speciális eset a Karen név második előfordulásával kapcsolatban - Az alapértelmezett viselkedés ebben a fában, ha ugyanazokat az adatokat adjuk meg, a "mozgás jobbra", akkor Karen Tomhoz képest -> K "kisebb" a T-nél, tehát marad belőle.
Mindenesetre itt van egy jobb példa, abból láthatod a rendelési számokat a bináris fában: http://www.codeproject.com/Articles/4647/A-simple-binary-tree-implementation-with-VB-NET
Bármely csomóponthoz:
Ez pár egyedi tulajdonságot biztosít
O(Log n) időn belül.Úgy gondolom, hogy ez a cikk nagyon hasznos lesz a bináris fa fogalmainak megértésében, valamint gyakori kódmintákat is tartalmaz C/C++ és Java nyelven:
http://cslibrary.stanford.edu/110/BinaryTrees.html
