Dvejetainio medžio ir dvejetainio paieškos medžio skirtumas

Kas yra dvejetainis medis?

Dvejetainis medis yra hierarchinė duomenų struktūra, kurioje kiekvienas mazgas turi nulį, vieną ar daugiausiai du vaikus. Kiekviename mazge yra „kairysis“ rodyklė, „dešinis“ rodyklė ir duomenų elementas. „Šaknies“ rodyklė žymi aukščiausią medžio mazgą. Kiekvienas mazgas duomenų struktūroje yra tiesiogiai sujungtas su savavališku mazgų skaičiumi iš abiejų pusių, vadinamu vaikais. Nulinis žymiklis žymi dvejetainį medį. Nėra specialios tvarkos, kaip mazgai turi būti išdėstyti dvejetainiame medyje. Mazgai, neturintys vaikų mazgų, vadinami lapų mazgais arba išoriniais mazgais.

Kalbant paprastai, jis apibūdina mazgų organizuotą ženklinimo funkciją, kuri savo ruožtu kiekvienam mazgui priskiria tam tikrą atsitiktinę vertę. Viskas, kas turi du vaikus ir vieną iš tėvų mazgų, yra dvejetainis medis. Dvejetainiai medžiai yra naudojami informacijai, kuri sudaro hierarchiją, tokią kaip failų sistema, saugoti asmeniniame kompiuteryje. Skirtingai nuo masyvų, medžiai neturi viršutinės mazgų skaičiaus ribos, nes jie susieti naudojant rodykles, pavyzdžiui, susietus sąrašus. Pagrindinės dvejetainio medžio funkcijos yra hierarchinių duomenų pateikimas, duomenų sąrašų rūšiavimas, efektyvių įterpimo / ištrynimo operacijų teikimas ir kt. Medžio mazgai pateikiami naudojant struktūras C.

Kas yra dvejetainė paieškos medis?

Dvejetainis paieškos medis yra dvejetainio medžio duomenų struktūros rūšis, kurioje mazgai yra išdėstyti eilės tvarka, todėl dar vadinami „užsakytu dvejetainiu medžiu“. Tai mazgo pagrindu sukurta duomenų struktūra, užtikrinanti efektyvų ir greitą duomenų rūšiavimo, gavimo ir paieškos būdą. Kiekvieno mazgo kairiajame papildomame elemente elementai turi būti mažesni arba lygūs jo pagrindinio mazgo (LP) raktui. Raktų kopijų neturėtų būti. Paprastai tariant, tai yra ypatinga dvejetainių medžių duomenų struktūra, kuri efektyviai saugo ir tvarko atmintyje esančius elementus.

Tai leidžia greitai pasiekti informaciją, įterpti ir pašalinti duomenis, be to, ją galima naudoti ieškos lentelėms, kurios leidžia ieškoti daiktų pagal jų unikalius klavišus, pavyzdžiui, ieškoti asmens telefono numerio pagal pavadinimą. Unikalūs raktai yra rūšiuojami organizuotai, kad paiešką ir kitas dinamines operacijas būtų galima atlikti naudojant dvejetainę paiešką. Tai palaiko tris pagrindines operacijas: elementų paiešką, elementų įdėjimą ir elementų ištrynimą. Dvejetainis paieškos medis leidžia greitai atkurti medyje saugomus elementus, nes kiekvienas mazgo raktas yra kruopščiai lyginamas su šaknies mazgu, kuris pašalina pusę medžio.

Dvejetainio medžio ir dvejetainio paieškos medžio skirtumas

1. Dvejetainio medžio ir dvejetainio paieškos medžio apibrėžimas - Dvejetainis medis yra hierarchinė duomenų struktūra, kurioje vaikas gali turėti nulį, vieną ar daugiausiai du vaiko mazgus; kiekviename mazge yra kairysis rodyklė, dešinysis rodyklė ir duomenų elementas. Nėra specialios tvarkos, kaip mazgai turėtų būti išdėstyti medyje. Dvejetainis paieškos medis, kita vertus, yra užsakytas dvejetainis medis, kuriame yra santykinė tvarka, kaip turėtų būti išdėstyti mazgai..
2. Struktūra apie Dvejetainis medis ir dvejetainis paieškos medis- Viršutinis medžio mazgas žymi šaknies žymiklį dvejetainiame medyje, o kairysis ir dešinysis rodyklės žymi mažesnius medžius iš abiejų pusių. Tai specializuota medžio forma, vaizduojanti duomenis medžio struktūroje. Dvejetainis paieškos medis, kita vertus, yra dvejetainis medis, kurio visi mazgai kairiajame subsere yra mažesni arba lygi šaknies mazgo vertei, o dešiniojo subtempio vertė yra didesnė arba lygi reikšmei. šaknies mazgo.
3. Operacija apie Dvejetainis medis ir dvejetainis paieškos medis- Dvejetainis medis gali būti viskas, kas turi du vaikus ir vieną iš tėvų. Įprastos operacijos, kurias galima atlikti dvejetainiame medyje, yra įterpimas, ištrynimas ir judėjimas. Dvejetainiai paieškos medžiai yra daugiau išrūšiuoti dvejetainiai medžiai, kurie leidžia greitai ir efektyviai ieškoti, įterpti ir ištrinti elementus. Skirtingai nei dvejetainiai medžiai, dvejetainiai paieškos medžiai palaiko jų raktus, todėl peržiūra paprastai vykdo dvejetainę operacijų paiešką.
4. Tipai apie Dvejetainis medis ir dvejetainis paieškos medis- Yra įvairių rūšių dvejetainių medžių, iš kurių paplitę yra „Visas dvejetainis medis“, „Užbaigtas dvejetainis medis“, „Tobulas dvejetainis medis“ ir „Išplėstas dvejetainis medis“. Kai kurie įprasti dvejetainių paieškos medžių tipai yra T-medžiai, AVL medžiai, Splay medžiai, Tango medžiai, Raudonai juodi medžiai ir kt..

Dvejetainis medis ir dvejetainis paieškos medis: palyginimo diagrama

Dvejetainio medžio ir dvejetainio paieškos medžio santrauka

Nors abu imituoja hierarchinę medžio struktūrą, vaizduojančią mazgų rinkinį su kiekvienu mazgu, reiškiančiu vertę, jie labai skiriasi vienas nuo kito tuo, kaip juos galima įgyvendinti ir panaudoti. Dvejetainis medis vadovaujasi viena paprasta taisykle, kad kiekvienas pirminis mazgas neturi daugiau nei dviejų vaiko mazgų, tuo tarpu dvejetainis paieškos medis yra tik dvejetainio medžio variantas, kuris seka santykinę tvarką, kaip mazgai turėtų būti išdėstyti medyje..