dvoichnie derevya.

DOCX 21 pages 130.5 KB Free download

21 pages

FaylHub.uz

Download via Telegram

Size 130.5 KB

File type DOCX

Pages 21

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 21

ministerstvo visshego i srednego spetsialnogo obrazovaniya respubliki uzbekistan ___________________________ universitet fakultet:“___________________________________” napravlenie:“_________________________________” samostoyatelnaya rabota _________ gruppi tema: _______________________________ _______________________________ sdal(a): _______________ prinyal(a): _______________ tema: dvoichnie derevya. plan: 1. vvedenie 2. opredelenie dvoichnogo dereva poiska (binary search tree, bst) 3. poisk vershini po klyuchu. 4. sposobi obxoda ddp 5. poisk vershini v ddp 6. udalenie vershini 7. nil, null i malenkie xitrosti 8. osnovnaya problema ispolzovaniya ddp 9. krasno - chyornie derevya (red-black tree, rb-tree) 10. svoystva kchd 11. dobavlenie vershini v kchd 12. zaklyuchenie 13. spisok ispolzuemoy literaturi vvedenie dinamicheskie strukturi dannix v protsesse sushestvovaniya v pamyati mogut izmenyat ne tolko chislo sostavlyayushix ix elementov, no i xarakter svyazey mejdu elementami. pri etom ne uchitivaetsya izmenenie soderjimogo samix elementov dannix. takaya osobennost dinamicheskix struktur, kak nepostoyanstvo ix razmera i xaraktera otnosheniy mejdu elementami, privodit k tomu, chto na etape sozdaniya mashinnogo koda programma-kompilyator ne mojet videlit dlya vsey strukturi v …

2 / 21

poryadocheni, kajdaya vershina imeet ne bolee dvux potomkov (nazovyom ix levim i pravim), i vse vershini, krome kornya, imeyut roditelya. vershini, ne imeyushie potomkov, nazivayutsya listami. podrazumevaetsya, chto kajdoy vershine sootvetstvuet element ili neskolko elementov, imeyushie nekie klyuchevie znacheniya, v dalneyshem imenuemie prosto klyuchami. obichno odnoy vershine sootvetstvuet odin element, poetomu dannie termini mojno bez poteri smisla schitat sinonimami, xotya i nado pomnit, chto v nekotorix realizatsiyax eto ne tak. v privedyonnix algoritmax schitaetsya, chto odnoy vershine sootvetstvuet tolko odin element. poetomu mi budem ispolzovat ponyatiya klyucha vershini i dannix vershini, podrazumevaya klyuch i dannie sootvetstvuyushego vershine elementa. mi tak je budem ponimat pod vstavkoy vershini dobavlenie vershini s ukazannim znacheniem elementa i prisvoenie ukazatelyam na roditelya i potomkov korrektnix znacheniy. imenno klyuch ispolzuetsya vo vsex operatsiyax sravneniya elementov. element mojet takje soderjat assotsiirovannie s klyuchom dannie. na praktike v kachestve klyucha mojet ispolzovatsya chast dannix elementa. klyuch takje mojet …

3 / 21

, kak pryamimi, tak i kosvennimi. poetomu o dereve mojno govorit kak o rekursivnoy strukture. effektivnost poiska po derevu napryamuyu svyazana s ego sbalansirovannostyu, to est s maksimalnoy raznitsey mejdu glubinoy levogo i pravogo poddereva sredi vsex vershin. imeetsya dva kraynix sluchaya – sbalansirovannoe binarnoe derevo (gde kajdiy uroven imeet polniy nabor vershin) i virojdennoe derevo, gde na kajdiy uroven prixoditsya po odnoy vershine. virojdennoe derevo ekvivalentno svyazannomu spisku. vremya vipolneniya vsex osnovnix operatsiy proportsionalno glubine dereva. takim obrazom, skorostnie xarakteristiki poiska v ddp mogut varirovatsya ot o(log2n) v sluchae zakonchennogo dereva do o(n) – v sluchae virojdennogo. ddp mojet bit ispolzovano dlya realizatsii takix abstraktsiy, kak sortirovanniy spisok, slovar (nabor sootvetstviy "klyuch-znachenie"), ochered s prioritetami i tak dalee. pri realizatsii dereva pomimo znacheniya klyucha (key) i dannix takje xranyatsya tri ukazatelya: na roditelya (net), levogo (left) i pravogo (right) potomkov. esli roditelya ili potomka net, to ukazatel xranit nulevoe …

4 / 21

oy (preorder), poperechniy (inorder), obratniy (postorder). pryamoy obxod: snachala obxoditsya dannaya vershina, levoe podderevo dannoy vershini, zatem pravoe podderevo dannoy vershini. poperechniy obxod: snachala obxoditsya levoe podderevo dannoy vershini, zatem dannaya vershina, zatem pravoe podderevo dannoy vershini. vershini pri etom budut sledovat v neubivayushem (po klyucham key) poryadke. obratniy obxod: snachala obxoditsya levoe podderevo dannoy vershini, zatem pravoe, zatem dannaya vershina. na risunke 3 poryadok obxoda vershin ukazan nomerami, pri etom predpolagaetsya, chto sami vershini raspolojeni tak, chto obrazuyut ddp. risunok 3. naibolee chasto upotreblyaetsya poperechniy obxod, tak kak vo vsex drugix sposobax obxoda sleduyushie drug za drugom vershini ne svyazani nikakimi usloviyami otnosheniya. poisk vershini v ddp ideya poiska prosta. algoritm poiska v ddp po svoey prirode rekursiven. pri ego opisanii proshe vsego ispolzovat ponyatie poddereva. poisk nachinaetsya s kornya dereva, kotoriy prinimaetsya za koren tekushego poddereva, i ego klyuch sravnivaetsya s iskomim. esli oni ravni, to, ochevidno, poisk …

5 / 21

le-podobnom yazike, vse parametri peredayutsya po znacheniyu. nodeparent, nodetemp i node – eto ukazateli na vershini, a tree – samo derevo, imeyushee pole root, ukazatel na koren dereva. iterativno: treesearch(node,key) begin // poka eshyo est vershini sredi kotorix mojno iskat //(mi prosmatrivaem ne vse, no neskolko) i poka mi ne nashli while (node != nil) and (node.key != key) do begin // esli klyuch naydennogy vershini bolshe togo kotoriy mi ishem if (node.key > key) then node = node.left; // to iskat v levom poddereve else node = node.right; // a inache v pravom poddereve end return node; // vozvratit naydennoe end poisk vershini s minimalnim i maksimalnim znacheniem klyucha vershini s minimalnim i maksimalnim znacheniem klyucha mojno nayti, proydyas po levim (pravim) ukazatelyam ot kornya (poka ne dostignem nil). vozvrashaemoe znachenie – eto ukazatel na vershinu s minimalnim (maksimalnim) znacheniem klyucha. treeminimum(node) begin while (node.left != nil) do // …

Want to read more?

Download all 21 pages for free via Telegram.

Download full file

About "dvoichnie derevya."

ministerstvo visshego i srednego spetsialnogo obrazovaniya respubliki uzbekistan ___________________________ universitet fakultet:“___________________________________” napravlenie:“_________________________________” samostoyatelnaya rabota _________ gruppi tema: _______________________________ _______________________________ sdal(a): _______________ prinyal(a): _______________ tema: dvoichnie derevya. plan: 1. vvedenie 2. opredelenie dvoichnogo dereva poiska (binary search tree, bst) 3. poisk vershini po klyuchu. 4. sposobi obxoda ddp 5. poisk vershini v ddp 6. udalenie vershini 7. nil, null i malenkie xitrosti 8. osnovnaya problema ispolzovaniya ddp 9. krasno - chyornie derevya (red-black tree, rb-tree) 10. svoystva kchd 11. dobavlenie vershini v kchd 12. zaklyuchenie 13. spisok ispolzuem...

This file contains 21 pages in DOCX format (130.5 KB). To download "dvoichnie derevya.", click the Telegram button on the left.

Tags: dvoichnie derevya. DOCX 21 pages Free download Telegram