Binarno drevo

Binarno drevo shranjuje povezave med telesi v modelirniku. Sestavljeno je iz vozlov in povezav med vozli. Vsak vozel ima shranjene naslednje podatke:

• kazalec na telo v seznamu teles
• tip operacije, ki jo opravlja trenutni vozel
• kazalec na nad-vozel
• kazalca na levo in desno vejo

Vsak vozel ima definirano operacijo, katero izvaja z obema vejama. Operacija za binarno drevo ni pomembna, upo¹teva se pri izgradnji predstavitve z mejami za novo nastalo telo. Pri izvajanju operacije je leva veja vedno tudi levi operand (slika 6.7 in tabela 6.1).

  
Slika 6.7: Primer osnovnega binarnega drevesa

 

operacija enaèba se¹tevanje od¹tevanje presek

 

• Zdru¾itev dveh teles pod isti vozel
• Dodajanje novega telesa v binarno drevo
• Brisanje teles iz binarnega drevesa
• Se¹tevanje, od¹tevanje, presek teles