Citim structurile de date liniare ca o matrice, o listă legată, o stivă și o coadă în care toate elementele sunt aranjate într-o manieră secvențială. Diferitele structuri de date sunt utilizate pentru diferite tipuri de date.

Câțiva factori sunt luați în considerare pentru alegerea structurii datelor:

Ce tip de date trebuie stocate?: Ar putea fi o posibilitate ca o anumită structură de date să fie cea mai potrivită pentru un anumit tip de date.Costul operațiunilor:Dacă dorim să minimizăm costul operațiunilor pentru cele mai des efectuate operațiuni. De exemplu, avem o listă simplă pe care trebuie să efectuăm operația de căutare; apoi, putem crea o matrice în care elementele sunt stocate în ordine sortată pentru a efectua căutare binară . Căutarea binară funcționează foarte rapid pentru lista simplă, deoarece împarte spațiul de căutare în jumătate.Folosirea memoriei:Uneori, dorim o structură de date care utilizează mai puțină memorie.

Un copac este, de asemenea, una dintre structurile de date care reprezintă date ierarhice. Să presupunem că vrem să arătăm angajații și pozițiile lor în formă ierarhică, atunci poate fi reprezentat după cum se arată mai jos:

Arborele de mai sus arată ierarhia organizației a unei firme. În structura de mai sus, Ioan este CEO al companiei, iar John are doi raportori direcți numiți ca Steve și Rohan . Steve are trei subordonați direcți numiți Lee, Bob, Ella Unde Steve este manager. Bob are doi raportori direcți numiți Trebuie și Emma . Emma are doi subordonați direcți numiți Tom și Raj . Tom are un raport direct numit Factură . Această structură logică specială este cunoscută ca a Copac . Structura sa este similară cu arborele real, așa că este numit a Copac . În această structură, rădăcină se află în vârf, iar ramurile sale se mișcă în direcție în jos. Prin urmare, putem spune că structura de date Tree este o modalitate eficientă de stocare a datelor într-un mod ierarhic.

Să înțelegem câteva puncte cheie ale structurii de date Tree.

• O structură de date arborescentă este definită ca o colecție de obiecte sau entități cunoscute sub numele de noduri care sunt legate între ele pentru a reprezenta sau simula ierarhia.
• O structură de date arborescentă este o structură de date neliniară deoarece nu este stocată într-o manieră secvenţială. Este o structură ierarhică, deoarece elementele dintr-un arbore sunt aranjate pe mai multe niveluri.
• În structura de date Tree, nodul cel mai de sus este cunoscut ca nod rădăcină. Fiecare nod conține unele date, iar datele pot fi de orice tip. În structura arborescentă de mai sus, nodul conține numele angajatului, deci tipul de date ar fi un șir.
• Fiecare nod conține unele date și legătura sau referința altor noduri care pot fi numite copii.

Câțiva termeni de bază utilizați în structura de date Tree.

Să luăm în considerare structura arborelui, care este prezentată mai jos:

În structura de mai sus, fiecare nod este etichetat cu un număr. Fiecare săgeată prezentată în figura de mai sus este cunoscută ca a legătură între cele două noduri.

Rădăcină:Nodul rădăcină este nodul cel mai de sus din ierarhia arborescentă. Cu alte cuvinte, nodul rădăcină este cel care nu are niciun părinte. În structura de mai sus, nodul numerotat 1 este nodul rădăcină al arborelui. Dacă un nod este direct legat de un alt nod, s-ar numi o relație părinte-copil.Nod copil:Dacă nodul este un descendent al oricărui nod, atunci nodul este cunoscut ca nod copil.Mamă:Dacă nodul conține orice sub-nod, atunci se spune că acel nod este părintele acelui sub-nod.Frate:Nodurile care au același părinte sunt cunoscute ca frați.Nodul frunzelor: -Nodul arborelui, care nu are niciun nod copil, se numește nod frunză. Un nod frunză este cel mai jos nod al arborelui. Într-un arbore general poate exista orice număr de noduri frunze. Nodurile frunzelor pot fi numite și noduri externe.Noduri interne:Un nod are cel puțin un nod copil cunoscut ca un intern Nodul strămoș:-Un strămoș al unui nod este orice nod predecesor pe o cale de la rădăcină la acel nod. Nodul rădăcină nu are strămoși. În arborele prezentat în imaginea de mai sus, nodurile 1, 2 și 5 sunt strămoșii nodului 10.Descendent:Succesorul imediat al nodului dat este cunoscut ca descendent al unui nod. În figura de mai sus, 10 este descendentul nodului 5.

Proprietățile structurii de date arbore

Structura datelor recursive:Arborele este cunoscut și sub numele de a structura de date recursivă . Un arbore poate fi definit recursiv deoarece nodul distinct dintr-o structură de date arborescentă este cunoscut ca un nodul rădăcină . Nodul rădăcină al arborelui conține o legătură către toate rădăcinile subarborilor săi. Subarborele din stânga este afișat cu culoarea galbenă în figura de mai jos, iar subarborele din dreapta este afișat cu culoarea roșie. Subarborele din stânga poate fi împărțit în continuare în subarbori afișați în trei culori diferite. Recursiunea înseamnă reducerea a ceva într-o manieră asemănătoare cu sine. Deci, această proprietate recursivă a structurii de date arborescente este implementată în diverse aplicații.
Numar de margini:Dacă există n noduri, atunci ar exista n-1 muchii. Fiecare săgeată din structură reprezintă legătura sau calea. Fiecare nod, cu excepția nodului rădăcină, va avea cel puțin o legătură de intrare cunoscută sub numele de margine. Ar exista un singur link pentru relația părinte-copil.Adâncimea nodului x:Adâncimea nodului x poate fi definită ca lungimea căii de la rădăcină la nodul x. O muchie contribuie la o unitate de lungime a traseului. Deci, adâncimea nodului x poate fi definită și ca numărul de muchii dintre nodul rădăcină și nodul x. Nodul rădăcină are 0 adâncime.Înălțimea nodului x:Înălțimea nodului x poate fi definită ca cea mai lungă cale de la nodul x la nodul frunză.

Pe baza proprietăților structurii de date Tree, arborii sunt clasificați în diferite categorii.

actor rohit shetty

Implementarea Tree

Structura de date arborescentă poate fi creată prin crearea dinamică a nodurilor cu ajutorul pointerilor. Arborele din memorie poate fi reprezentat după cum se arată mai jos:

Figura de mai sus arată reprezentarea structurii de date arborescente în memorie. În structura de mai sus, nodul conține trei câmpuri. Al doilea câmp stochează datele; primul câmp stochează adresa copilului din stânga, iar al treilea câmp stochează adresa copilului din dreapta.

În programare, structura unui nod poate fi definită astfel:

 struct node { int data; struct node *left; struct node *right; } 

Structura de mai sus poate fi definită numai pentru arborii binari, deoarece arborele binar poate avea cel mult doi copii, iar arborii generici pot avea mai mult de doi copii. Structura nodului pentru arbori generici ar fi diferită în comparație cu arborele binar.

Aplicații ale arborilor

Următoarele sunt aplicațiile arborilor:

Stocarea datelor ierarhice în mod natural:Arborii sunt utilizați pentru a stoca datele în structura ierarhică. De exemplu, sistemul de fișiere. Sistemul de fișiere stocat pe unitatea de disc, fișierul și folderul sunt sub forma datelor ierarhice în mod natural și stocate sub formă de arbori.Organizați datele:Este folosit pentru a organiza datele pentru inserarea, ștergerea și căutarea eficientă. De exemplu, un arbore binar are un timp logN pentru căutarea unui element.Încearcă:Este un tip special de arbore care este folosit pentru a stoca dicționarul. Este o modalitate rapidă și eficientă de verificare ortografică dinamică.Morman:Este, de asemenea, o structură de date arborescentă implementată folosind matrice. Este folosit pentru implementarea cozilor prioritare.B-Tree și B+Tree:B-Tree și B+Tree sunt structurile de date arborescente utilizate pentru implementarea indexării în bazele de date.Tabel de rutare:Structura de date arborescentă este, de asemenea, utilizată pentru a stoca datele în tabelele de rutare din routere.

Tipuri de structură de date arbore

Următoarele sunt tipurile unei structuri de date arborescente:

Arborele general:Arborele general este unul dintre tipurile de structuri de date arborescente. În arborele general, un nod poate avea fie 0, fie maximum n număr de noduri. Nu există nicio restricție impusă asupra gradului nodului (numărul de noduri pe care le poate conține un nod). Nodul cel mai de sus dintr-un arbore general este cunoscut ca nod rădăcină. Copiii nodului părinte sunt cunoscuți ca subarbori .

Poate fi n numărul de subarbori dintr-un arbore general. În arborele general, subarborele sunt neordonate, deoarece nodurile din subarborele nu pot fi ordonate.
Fiecare arbore negol are o margine descendentă, iar aceste margini sunt conectate la nodurile cunoscute ca nodurile copil . Nodul rădăcină este etichetat cu nivelul 0. Nodurile care au același părinte sunt cunoscute ca fratii . Arbore binar :Aici, numele binar însuși sugerează două numere, adică 0 și 1. Într-un arbore binar, fiecare nod dintr-un arbore poate avea cel mult două noduri copil. Aici, maxim înseamnă dacă nodul are 0 noduri, 1 nod sau 2 noduri.

Pentru a afla mai multe despre arborele binar, faceți clic pe linkul de mai jos:
https://www.javatpoint.com/binary-tree Arborele de căutare binar :Arborele de căutare binar este o structură de date neliniară la care este conectat un nod n numărul de noduri. Este o structură de date bazată pe noduri. Un nod poate fi reprezentat într-un arbore de căutare binar cu trei câmpuri, adică partea de date, copil stânga și copil dreapta. Un nod poate fi conectat la cele mai multe două noduri copil dintr-un arbore de căutare binar, astfel încât nodul conține doi pointeri (fiul stâng și indicatorul copil din dreapta).
Fiecare nod din subarborele din stânga trebuie să conțină o valoare mai mică decât valoarea nodului rădăcină, iar valoarea fiecărui nod din subarborele din dreapta trebuie să fie mai mare decât valoarea nodului rădăcină.

Un nod poate fi creat cu ajutorul unui tip de date definit de utilizator cunoscut ca structura, așa cum se arată mai jos:

 struct node { int data; struct node *left; struct node *right; } 

Mai sus este structura nodului cu trei câmpuri: câmp de date, al doilea câmp este indicatorul din stânga al tipului de nod, iar al treilea câmp este indicatorul din dreapta al tipului de nod.

Pentru a afla mai multe despre arborele binar de căutare, faceți clic pe linkul de mai jos:

https://www.javatpoint.com/binary-search-tree

arborele AVL

Este unul dintre tipurile de arbore binar, sau putem spune că este o variantă a arborelui de căutare binar. Arborele AVL satisface proprietatea arbore binar precum și al arbore binar de căutare . Este un arbore de căutare binar cu auto-echilibrare care a fost inventat de Adelson Velsky Lindas . Aici, auto-echilibrarea înseamnă că echilibrarea înălțimii subarborelui din stânga și subarborelui din dreapta. Această echilibrare este măsurată în termeni de factor de echilibrare .

Putem considera un arbore ca un arbore AVL dacă arborele respectă arborele de căutare binar, precum și un factor de echilibrare. Factorul de echilibrare poate fi definit ca diferența dintre înălțimea subarborelui din stânga și înălțimea subarborelui din dreapta . Valoarea factorului de echilibrare trebuie să fie 0, -1 sau 1; prin urmare, fiecare nod din arborele AVL ar trebui să aibă valoarea factorului de echilibrare fie ca 0, -1 sau 1.

imagini de reducere

Pentru a afla mai multe despre arborele AVL, faceți clic pe linkul de mai jos:

https://www.javatpoint.com/avl-tree

Arborele Roșu-Negru

Arborele roșu-negru este arborele binar de căutare. Condiția prealabilă a arborelui roșu-negru este că ar trebui să știm despre arborele binar de căutare. Într-un arbore de căutare binar, valoarea subarborelui din stânga ar trebui să fie mai mică decât valoarea acelui nod, iar valoarea subarborelui din dreapta ar trebui să fie mai mare decât valoarea nodului respectiv. După cum știm că complexitatea de timp a căutării binare în cazul mediu este log₂n, cel mai bun caz este O(1), iar cel mai rău caz este O(n).

Când se efectuează orice operație asupra arborelui, dorim ca arborele nostru să fie echilibrat, astfel încât toate operațiunile precum căutarea, inserarea, ștergerea etc., să dureze mai puțin și toate aceste operațiuni vor avea complexitatea de timp de Buturuga₂n.

Arborele roșu-negru este un arbore de căutare binar cu auto-echilibrare. Arborele AVL este, de asemenea, un arbore de căutare binar de echilibrare a înălțimii de ce avem nevoie de un copac roșu-negru . În arborele AVL, nu știm câte rotații ar fi necesare pentru a echilibra arborele, dar în arborele Roșu-negru sunt necesare maximum 2 rotații pentru a echilibra arborele. Conține un bit suplimentar care reprezintă fie culoarea roșie, fie culoarea neagră a unui nod pentru a asigura echilibrarea arborelui.

Splay arbore

Structura de date a arborelui splay este, de asemenea, arbore de căutare binar în care elementul recent accesat este plasat la poziția rădăcină a arborelui prin efectuarea unor operații de rotație. Aici, întinderea înseamnă nodul accesat recent. Este un autoechilibrare arborele de căutare binar care nu are nicio condiție de echilibru explicită, cum ar fi AVL copac.

Ar putea fi o posibilitate ca înălțimea arborelui splay să nu fie echilibrată, adică înălțimea ambelor sub-arbori din stânga și din dreapta poate diferi, dar operațiunile din arborele splay sunt în ordinea de calm timp unde n este numărul de noduri.

Arborele Splay este un arbore echilibrat dar nu poate fi considerat ca un arbore echilibrat in inaltime deoarece dupa fiecare operatie se efectueaza rotatie care duce la un arbore echilibrat.

Treap

Structura de date Treap provine din structura de date Tree și Heap. Deci, cuprinde proprietățile structurilor de date arbore și heap. În arborele de căutare binar, fiecare nod din subarborele din stânga trebuie să fie egal sau mai mic decât valoarea nodului rădăcină și fiecare nod din subarborele din dreapta trebuie să fie egal sau mai mare decât valoarea nodului rădăcină. În structura de date heap, atât subarborele din dreapta cât și din stânga conțin chei mai mari decât rădăcina; prin urmare, putem spune că nodul rădăcină conține cea mai mică valoare.

În structura de date treap, fiecare nod are ambele cheie și prioritate unde cheia este derivată din arborele de căutare binar și prioritatea este derivată din structura de date heap.

The Treap Structura datelor urmează două proprietăți care sunt prezentate mai jos:

• Fiul drept al unui nod>=nodul curent și copilul stâng al unui nod<=current node (binary tree)< li>
• Copiii oricărui subarbore trebuie să fie mai mari decât nodul (heap)

B-arborele

B-tree este echilibrat m-mod copac unde m definește ordinea arborelui. Până acum, am citit că nodul conține o singură cheie, dar b-tree poate avea mai mult de o cheie și mai mult de 2 copii. Menține întotdeauna datele sortate. În arborele binar, este posibil ca nodurile frunzelor să fie la niveluri diferite, dar în arborele b, toate nodurile frunzei trebuie să fie la același nivel.

Dacă ordinea este m, atunci nodul are următoarele proprietăți:

• Fiecare nod dintr-un arbore b poate avea maxim m copii
• Pentru copii minimi, un nod frunză are 0 copii, nodul rădăcină are minim 2 copii și nodul intern are plafon minim de m/2 copii. De exemplu, valoarea lui m este 5 ceea ce înseamnă că un nod poate avea 5 copii, iar nodurile interne pot conține maximum 3 copii.
• Fiecare nod are maxim (m-1) chei.

Nodul rădăcină trebuie să conțină cel puțin 1 cheie și toate celelalte noduri trebuie să conțină cel puțin plafon de m/2 minus 1 chei.