Balanced tree.pngTræet som datastruktur bruges i mange sammenhænge. De bruges både i forbindelse med opbevaring af data og i forbindelse med sortering. Fordelen ved en træstruktur er, at den er fleksibel og kan bruges forholdsvis effektivt både til sekventiel gennemlæsning af data og til direkte opslag. Et træ vises som regel med roden øverst og med grene, der vokser ned ad.

Filsystemer er ofte lavet så filerne kan tilgås i en træstruktur.

Terminologi

---

Der bruges en række ord med specielle betydninger, når det drejer sig om træstrukturer.

• En knude indeholder information og referencer til andre knuder.
• Roden er den knude som er udgangspunktet for træet. Den er rød på figuren.
• En gren forbinder to knuder. Normalt går referencen fra en knude nærmere roden til en knude længere væk.
• Et blad eller en bladknude er en knude, der ikke refererer til knuder længere nede i træet. De er vist som grønne på figuren.
• Et undertræ besår af en knude og alle knuder, der er referencer til herfra. Det gælder både direkte og indirekte referencer.
• Et træs højde er det maksimale antal niveauer i træet.

Gængse træstrukturer

---

• AVL-træ
• B-træ
• B+-træ
• Binær heap
• Binært søgetræ
• IPR-træ

datastrukturer

Baum (Graphentheorie) | Tree data structure | Árbol (estructura de datos) | 木構造 (データ構造) | Medis (duomenų struktūra) | Tree | Drzewo (informatyka) | Topologia em árvore | Дерево (структура даних) | 树 (数据结构)