Hierarkisk Java-datastruktur - 'For disse datastrukturer er lige så vigtige'

Hvis jeg havde en chance for at hente og lære et tilfældigt emne fra Java Tutorial, ville jeg vælge Hierarchical Data Structure i Java. Det er det mest interessante og nemmeste at lære konceptet i hele Java Tutorial Series.

I vores tidligere artikel diskuterede vi de lineære datastrukturer i Java og dækkede arrays, linkede lister, stakke og køer.

For at fortsætte datastrukturkæden i dag vil vi lære om den hierarkiske datastruktur i Java, såsom binært træ, binært søgetræ, heap og hash-datastruktur i detaljer med eksempler. Disse datastrukturer er ikke-lineære.

Men før det anbefales det, at du tager en hurtig revision af Linear Data Structure i Java for at rydde dit grundlæggende med Techvidvan.

Så lad os begynde at udforske nogle hierarkiske datastrukturer i Java.

Hold dig opdateret med de nyeste teknologitrends, Deltag i TechVidvan på Telegram

Hierarkiske datastrukturer i Java

Hierarkiske datastrukturer er ikke-lineære datastrukturer. Disse strukturer repræsenterer hovedsageligt data, der indeholder det hierarkiske forhold mellem dets elementer, for eksempel poster, træer osv.

1. Binære træer

Et binært træ er en struktur, hvor hver node højst kan have to børn (underknudepunkter). I et binært træ eksisterer der en unik sti fra rodknudepunktet til hver anden knude.

Den øverste knude i et binært træ kaldes rodknuden eller overordnet node , og de knudepunkter, der kommer fra rodknuden, kaldes underknudepunkterne .

Et binært træ er enten tomt (som kaldes et nultræ). ), eller den består af en rodknude sammen med de resterende to knudepunkter, som hver er et binært træ i sig selv.

Hver knude i et binært træ kan have nul, en eller maksimalt to efterfølgere eller underknudepunkter:venstre efterfølger eller underknude og højre efterfølger eller underknude. En terminal node (det vil sige en node med n efterfølger) kaldes en bladknude .

Figuren nedenfor viser et eksempel på et binært træ:

Repræsentation af binære træer

Hvert objekt i et binært træ er repræsenteret af en markør på den øverste knude sammen med de to referencer til venstre knude og højre knude i træet. Hvis noderne i træet er tomme, det vil sige bladknude, så er dens venstre og højre referencer NULL.

Delene af det binære træ er:

• Data
• Reference til venstre barn
• Reference til det rigtige barn

I et binært træ er der et niveautal for hver node. Rodnoden er på niveau 0, så hvert barn har niveau nummer et mere end niveaunummeret på dets overordnede node.

Køre gennem binære træer

Trægennemløbet er processen med at gå gennem et træ, på en sådan måde, at det kun besøger hver knude én gang. Der er tre standard måder at krydse et binært træ på, som er:

• Forudbestil gennemkørsel
• In-order Traversal
• Postorder-gennemgang

Egenskaber af binære træer:

• Antallet af børn i en node kaldes træets grad. Et binært træ er et træ af grad 2, da hver node maksimalt kan have 2 børn.
• Dybden eller højden af ​​et træ er det maksimale antal noder i en gren af ​​det. Det er altid et mere end træets længste niveaunummer.
• Det maksimale antal noder på niveau 'L' er 2^ (L-1)
• Det maksimale antal noder for et træ med højden 'h' er 2^ (h – 1)
• Tidskompleksiteten af ​​trægennemgang er O(n)

2. Binært søgetræ (BST)

Binary Search Tree er den anden vigtigste hierarkiske datastruktur i Java. Det ligner de binære træer, men har nogle yderligere egenskaber som:

• Værdien af ​​hver node N i det højre undertræ er større end hver værdi i det venstre undertræ.
• Værdien af ​​hver node N i det venstre undertræ er mindre end hver værdi i det højre undertræ.
• Det venstre og højre undertræ skal være et binært søgetræ.

Figuren nedenfor viser et eksempel på et binært søgetræ:

Den primære anvendelse af et binært søgetræ er at søge i applikationer som kort, hvor dataene kommer ind ofte. Binære søgetræer giver hurtig søgning og adgangsmuligheder, som er hurtige sammenlignet med de linkede lister.

Egenskaber for binære søgetræer:

• Søg:O(h)
• Indsættelse:O(h)
• Sletning:O(h)

hvor 'h ’ er træets højde.

3. Binær bunke

En binær bunke er en anden hierarkisk datastruktur, der ligner et komplet binært træ med nogle yderligere egenskaber. Et komplet binært træ er et binært træ uden noder med kun ét barn; undtagen det dybeste niveau. Den almindelige brug af binære heaps er at implementere prioritetskøer.

Den binære bunke har følgende egenskaber:

• En binær bunke kan enten være en Min bunke eller en Max Heap.
• I en Min Binary Heap skal dataene ved roden være minimum blandt alle data, der findes i Binary Heap.
• I en Max Binary Heap skal dataene ved roden være maksimale blandt alle data, der findes i Binary Heap.

Eksempel på min. bunke:

Eksempel på Max Heap:

4. Hashing-funktion

En hashfunktion eller en hashfunktion er den hierarkiske datastruktur i Java. Hashing-funktionen konverterer en gruppe af tegn (kaldet en nøgle) til en lille heltalsværdi af en bestemt længde kaldet en hashværdi eller hashkoder eller hash.

Kort sagt, denne hash-funktion kortlægger nøgler til nogle værdier. Hashværdien repræsenterer den oprindelige streng af tegn i en eller anden heltalsværdi, og denne værdi er normalt mindre end den oprindelige værdi.

Vi bruger hash-funktioner til at indeksere og lokalisere elementer i databaser, da det er nemmere at finde den kortere hashværdi end den længere streng. Den vigtigste anvendelse af Hashing can er i kryptering. Vi kan også kalde denne funktion som en message digest-funktion eller hashing-algoritme.

HashMap: HashMap er en samlingsklasse i Java, der gemmer elementerne som nøgle-værdi-par.

Tilgange til at håndtere hashing er:

4.1 Kædning

I denne tilgang indeholder hver plads i hash-tabellen et link, der peger på en enkelt-linket liste, der indeholder nøgle-værdi-par med den samme hash .

4.2 Åbn adressering

I åben adressering gemmer vi alle elementerne i selve hash-tabellen. Hver tabelsektion indeholder enten Nul eller en post.

Oversigt

I denne tutorial lærte vi om den anden del af Java Data Structures, det vil sige hierarkisk datastruktur i Java-programmeringssprog. I denne tutorial lærte vi om binært træ, binært søgetræ, binært bunke og hashing-funktion i Java.

Denne artikel vil helt sikkert hjælpe dig med at forstå konceptet med de hierarkiske datastrukturer i Java.

Tak fordi du læste vores artikel. Hvis du har spørgsmål relateret til Java Data Structure, så lad os det vide ved hjælp af kommentarsektionen nedenfor.

God læring 🙂