I den här handledningen lär du dig om träddatastrukturen. Du kommer också att lära dig om olika typer av träd och de terminologier som används i träd.
Ett träd är en olinjär hierarkisk datastruktur som består av noder som är förbundna med kanter.
Ett träd
Varför träddatastruktur?
Andra datastrukturer som matriser, länkad lista, stack och kö är linjära datastrukturer som lagrar data sekventiellt. För att utföra någon operation i en linjär datastruktur ökar tidskomplexiteten med ökningen av datastorleken. Men det är inte acceptabelt i dagens beräkningsvärld.
Olika träddatastrukturer möjliggör snabbare och enklare åtkomst till data eftersom det är en icke-linjär datastruktur.
Trädterminologier
Nod
En nod är en enhet som innehåller en nyckel eller ett värde och pekar på sina undernoder.
De sista noderna i varje sökväg kallas bladnoder eller externa noder som inte innehåller en länk / pekare till undernoder.
Noden som har minst en undernod kallas en intern nod .
Kant
Det är länken mellan två noder.
Noder och kanter på ett träd
Rot
Det är ett träds översta nod.
Nodens höjd
Höjden på en nod är antalet kanter från noden till det djupaste bladet (dvs. den längsta vägen från noden till en bladnod).
Djup av en nod
Djupet på en nod är antalet kanter från roten till noden.
Trädets höjd
Höjden på ett träd är höjden på rotnoden eller djupet på den djupaste noden.
Höjd och djup för varje nod i ett träd
Grad av en nod
Graden av en nod är det totala antalet grenar av den noden.
Skog
En samling av ojämna träd kallas en skog.
Skapa skog från ett träd
Du kan skapa en skog genom att skära roten på ett träd.
Typer av träd
- Binärt träd
- Binärt sökträd
- AVL-träd
- B-träd
Trädgenomgång
För att kunna utföra någon operation på ett träd måste du nå till den specifika noden. Trädgenomgångsalgoritmen hjälper till att besöka en nödvändig nod i trädet.
För att lära dig mer, besök tree traversal.
Trädapplikationer
- Binära sökträd (BST) används för att snabbt kontrollera om ett element finns i en uppsättning eller inte.
- Heap är ett slags träd som används för högsortering.
- En modifierad version av ett träd som heter Tries används i moderna routrar för att lagra routningsinformation.
- De mest populära databaserna använder B-Trees och T-Trees, som är varianter av trädstrukturen vi lärde oss ovan för att lagra deras data
- Kompilatorer använder ett syntaxträd för att validera syntaxen för varje program du skriver.
