Pemët binare

Në shkencat kompjuterike, një pemë binarë (Anglisht : binary tree) është një pemë e të dhënave në te cilin çdo nyje ka një ose dy nën fëmije, normalisht "fëmiu i djathte" dhe "fëmiu i majtë". Nyja e cila i ka "fëmiun e djathte" ose "fëmiun e majtë" ose ne raport me to është prindi i tyre. Jasht kësaj strukture qëndron një referencë në "nenin rrenjë" nenin (paraardhësin e të gjithe neneve), në qofte se ai egziston. Çdo nyje në këtë strukturë të dhënash mundet të takohet duke filluar nga "neni rrenjë" dhe duke përcjellur përsërituri referencën se a do zbresim në nën fëmiun e majtë apo të djathtë. Lisat Binarë përdoren për të krijuar lisat e kërkimit dhe grumbujt binarë;

Definicioni për lisat me rrënjë

Rruga e drejtë na tregon lidhjen nga prind në fëmije (siç e shihni dhe në figurën lartë me shigjeta).
Pra neni rrenjë i lisit ështëneni që nuk ka prind. Lisat me rrënje duhen të kenë së paku një rrënjë.
Një nen fletë nuk ka fëmijë.
Thellësia e një neni n ështe gjatësia e rrugës nga rrënja deri në at nen. Kështu mund të themi se thellësia e të gjith neneve mund të quhet Nivel,Lartesi. Rrënja ështe ne thellësine zero.
Lartësia e një lisi ështe rruga nga rrënja deri në nenin më të thellë në at lis. Lisi i rrënjëzuar apo vetëm me elementin rrënjë ka lartësinë zero.
Binjakët janë nene që ndajnë të njejtin prind.
Neni p është paraardhës i një neni q në qofte se egziston ai nen q në rrugën prej q deri në rrënjë. Kështu qe neni q është i quajtur pasaardhës i një neni p.
Madhësia e një neni ështe numri i pasaardhësve që ai përmban në vetëvete.
Shkalla e brendëshme e një neni është numri i shigjetave që arrijnë në at nen.
Shkalla e jashtëme e një neni është numri i shigjetave që largohen nga ai nen.
Rrënja është e vetmja nyje në lis që ka Shkallën e brendëshme = 0.

Shembull.: thellësia e lisit me Niveli = 3; atëhere madhësia do të jetë e barabarte me:Niveli+1=4.

Llojet e lisave binarë

Lisat e rrënjëzuar jan lisa me nenin rrënje i cili ne çdo nyje më së shumti mund të ket 2 fëmije. Një Lis plotësisht Binarë (nganjëhere mund të themi Lis fondamental binarë ose LIS-2 ose plotësisht binarë) ështe i llojit ku çdo nyje ka dy fëmijë.

Në Përkthim e sipër*

Burime

References

Donald Knuth. The art of computer programming vol 1. Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.3, especially subsections 2.3.1–2.3.2 (pp. 318–348).
Kenneth A Berman, Jerome L Paul. Algorithms: Parallel, Sequential and Distributed. Course Technology, 2005. ISBN 0-534-42057-5. Chapter 4. (pp. 113–166).

External links

flash actionscript 3 opensource implementation of binary tree — opensource library
[1] — GameDev.net's article about binary trees
[2] — Binary Tree Proof by Induction
Balanced binary search tree on array How to create bottom-up an Ahnentafel list, or a balanced binary search tree on array

Pemët binare