Information Technology | Information theory » Bináris keresőfák

Bináris keresőfák keresőfa tulajdonságai: • minden csúcsához tartozik egy kulcs (különböző csúcsokhoz különböző kulcsok) • minden csúcs esetében a bal gyerek kulcsa kisebb, a jobb gyerek kulcsa nagyobb, mint a csúcsé Inorder bejárás: növekvő sorba rendezve adja meg a kulcsokat. 1 Keresőfa AAT műveletek: létrehozás, keresés, beszúrás, törlés, üres-e, elemek száma #include <iostream> using namespace std; typedef char Tipus; struct Csucs{ Tipus info; Csucs *bal, jobb; }; Csucs *binfa; void Preorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ printf("%c ", AktualisCsucs->info); Preorder(AktualisCsucs->bal); Preorder(AktualisCsucs->jobb); }; } 2 void Postorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ Postorder(AktualisCsucs->bal); Postorder(AktualisCsucs->jobb); printf("%c ", AktualisCsucs->info); }; } void Inorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ Inorder(AktualisCsucs->bal);

printf("%c ", AktualisCsucs->info); Inorder(AktualisCsucs->jobb); }; } bool Talalt(Csucs* fa, Tipus elem){ //IGAZ, ha elem bennevan if (fa==NULL) return false; else if (elem < fa->info) return Talalt(fa->bal,elem); else if (elem > fa->info) return Talalt(fa->jobb,elem); else return true; } 3 void Beszur(Csucs* &fa, Tipus elem){ // elemet beszúr if (fa==NULL){ fa = new Csucs; fa->bal=fa->jobb=NULL; fa->info=elem; } else if (elem < fa->info) Beszur(fa->bal,elem); else if (elem > fa->info) Beszur(fa->jobb,elem); }; Tipus LegnagyobbElem(Csucs* fa){ // legnagyobb elem keresése adott (rész)fában while(fa->jobb != NULL) fa=fa->jobb; return fa->info; }; void Torol(Csucs* &fa, Tipus elem); void CsucsotTorol(Csucs* &fa){ Tipus adat; Csucs* tempPtr; tempPtr=fa; 4 // elem törlése // csúcs törlése if (fa->bal==NULL){ fa=fa->jobb; delete tempPtr; } else if (fa->jobb==NULL){ fa=fa->bal;

delete tempPtr; } else { adat=LegnagyobbElem(fa->bal); fa->info=adat; Torol(fa->bal,adat); }; }; void Torol(Csucs* &fa, Tipus elem){ if (elem < fa->info) Torol(fa->bal, elem); else if (elem > fa->info) Torol(fa->jobb, elem); else CsucsotTorol(fa); }; 5 void main(){ binfa = NULL; Beszur(binfa,’c’); Beszur(binfa,’k’); Beszur(binfa,’e’); Beszur(binfa,’a’); Beszur(binfa,’b’); Beszur(binfa,’s’); cout << " Inorder: cout << endl; "; Inorder(binfa); Torol(binfa,’k’); cout << " Inorder: cout << endl; Beszur(binfa, ’d’); Beszur(binfa, ’p’); Beszur(binfa, ’t’); cout << " Inorder: cout << endl; Torol(binfa,’e’); cout << " Inorder: cout << endl; } "; Inorder(binfa); "; Inorder(binfa); "; Inorder(binfa); 6 Példák: Új elem beszúrása (3 beszúrása) 7 Egy utóddal rendelkező belső csúcs törlése (b törlése)

Két utóddal rendelkező belső csúcs törlése (k törlése) 8 Gyökér törlése (i törlése) 9 A kiírás szempontjából jobb megoldás C++-ban: void Preorder(Csucs* AktualisCsucs){ if (AktualisCsucs){ cout << AktualisCsucs->info << " "; Preorder(AktualisCsucs->bal); Preorder(AktualisCsucs->jobb); }; } Ekkor pl. typedef int Tipus; elég ahhoz, hogy karakterek helyett egészekkel dolgozzunk Megoldandó feladatok: Eljárások írása a következő műveletekre: – elemek megszámolása – legkisebb kulcsú elem megkeresése – legnagyobb kulcsú elem megkeresése 10 2-3-fák • minden levél azonos szinten van • minden belső csúcsból 2 vagy 3 él indul ki m1 s1 m2 s2 m3 m1 s1 m2 s1 < s2 kulcsok m1, m2, m3 mutatók 11 Bm-fák m-ed rendű B-fa v. Bm-fa: • a gyökér foka legalább 2 (akkor lehet kevesebb, ha a fa legfeljebb kétszintes) és legfeljebb m, • minden belső csúcsnak legalább d m2 e és legfeljebb m

gyereke van, • a levelek mind egy szinten vannak m0|s1|m1|s2|m2| . |sk |mk | |si|mi d m2 e − 1 ≤ i ≤ m − 1 Az mk által mutatott részfában minden s kulcsra igaz, hogy: sk ≤ s < sk+1 12 AV L-fák (Adelszon-Velszkij–Landisz, 1962) olyan bináris fa, amelynek minden csúcsára igaz: a bal és jobb részfa magassága legfeljebb egyben különbözik Legyen Gk a k magasságú AVL-fa minimális csúcsszáma G1 = 1, G2 = 2, G3 = 4, G4 = 7 stb. Tétel. Ha k ≥ 1, akkor Gk = Fk+2 − 1 Bizonyítás: indukcióval, k = 1, 2-re igaz, mert F0 = 0, F1 = 1, F2 = 2, . , Fn = Fn−1 + Fn−2 De: Gk = 1 + Gk−1 + Gk−2, innen és az ind. felt szerint Gk = 1 + Gk−1 + Gk−2 = 1 + Fk+1 − 1 + Fk − 1 = Fk+2 − 1. Következmény. Egy n-pontú AVL-fa szintjeinek száma (magassága) ≤ 1.44 log2(n + 1) Bizonyítás: n ≥ Fk+2 − 1, de √ !n−1 √ !n−2 1+ 5 1+ 5 ≤ Fn ≤ 2 2 ezért n+1≥ √ !k 1+ 5 =⇒ log 1+√5 (n + 1) ≥ k, 2 2 ahonnan k ≤ 1.44 log2(n

+ 1) 13 S-fák (splay-fák, kifordított fák) önszervező fák A fa nem kiegyenzúlyozott, hanem alakul a keresés során, a keresett elemet fennebb mozgatja (pl. a gyökérbe) Így a gyakran keresett elemek a gyökérhez közel kerülnek, és ezzel gyorsítják a keresést, az átlagos keresés ideje jobb lesz. 14 (Splay-tree, Wikipedia) 15 Szófák (trie)  d  - a  - m - a - 1   @ @   R @   S S S  S w  a l       g - *  a - *  k - *  S S    w S    í t 16 * Tömörítés (ha nincs elágazás) (Szlávi–Zsakó: Adatszerkezetek) 17 Piros-fekete fák A piros-fekete fa olyan bináris keresőfa, amelynek csúcsai pirosak vagy feketék: • Minden csúcs színe vagy piros vagy fekete. • A gyökércsúcs színe fekete. • Minden levél (nil v. null) színe fekete • Minden piros csúcsnak mindkét gyereke fekete. • Bármely csúcsból minden levélig vezető úton ugyannyi fekete csúcs van. • Teljesül

a keresőfa-tulajdonság. • Minden belső csúcsnak két gyereke van. Elég jól kiegyensúlyozott: a gyökért?l bármelyik levélig a leghosszabb út legfeljebb kétszerese a legrövidebbnek. Bármely n belső csúcsot tartalmazó piros-fekete fa magassága legfeljebb 2 log(n + 1). Műveletek: forgatások, beszúrás, törlés. 18 19 (CLRS: Új algoritmusok, Scolar, 2003) 20