Medžiai yra hierarchinės Duomenų struktūros, juose tarp medžio elementų egzistuoja "tėvų-vaikų" santykiai. Kiekvienas elementas yra susietas su vienu ar daugiau elementų. Medžio elementai yra vadinami medžio viršūnėmis. Kitaip nei gamtoje, ši duomenų struktūra dažniausiai vaizduojama iš viršaus į apačią, kai aukščiau esanti viršunė vadinama tėvu. Elementas, kuris neturi tėvo, vadinamas šaknimi ar šakniniu elementu. Elementai neturintys vaikų vadinami lapais. Viršunės, kurios nėra lapai, dar vadinamos vidinėmis viršūnėmis.

Medžio aukščiu vadinamas atstumas nuo šaknies iki toliausiai esančio lapo. Medžio viršūnės lygis nusako jos eilės tvarką skaičiuojant nuo šaknies (šaknis yra 1 lygio, jos vaikas 2...).

Dvejetainiai medžiai

---

Dvejetainis medis (binary tree) – tai toks medis, kurio kiekviena viršūnė turi ne daugiau kaip 2 vaikus, kurie vadinami dešiniuoju ir kairiuoju medžio pomedžiu.

Pilnas (full): dvejetainis medis, kurio visos viršūnės arba neturi vaikų, arba jų turi 2.

Tobulas (perfect): dvejetainis medis, kuriuo visi lapai yra viename aukštyje

Užbaigtas (complete): tobulas dvejetainis medis. Ši sąvoka yra kartais naudojama pilnam medžiui, kurio lapai yra arba h arba h -1 aukštyje, apibrėžti

Pilnas h aukščio medis turi 2^h-1 viršūnių, o bet kuris h aukščio dvejetainis medis turi ne daugiau nei 2^h-1 viršūnių. Atitinkamai N viršūnių dvejetainių medžių minimalus aukštis yra $\backslash lceil\; \backslash log\_2\; \{N+1\}\; \backslash rceil$.

Dvejetainis paieškos medis

Dvejetainis paieškos medis (binary search tree) – tai dvejetainis medis, kuris surūšiuotas pagal reikšmes jo viršūnėse. Kiekvienai viršūnei jis tenkina tokias tris savybes:

1. n-osios viršūnės reikšmė yra didesnė už visas reikšmes jos kairiąjame pomedyje.
2. n-osios viršūnės reikšmė yra mažesnė už visas reikšmes jos dešiniąjame pomedyje.
3. Kairysis ir dešinysis pomedžiai yra dvejetainiai paieškos medžiai.

Pasukimas

---

Medžio pasukimas tai operacija dvejetainiame paieškos medyje, skirta pakeisti viršūnių padėtį, nepažeidžiant medžio sąvybių. Yra du operacijos tipai: pasukimas į kairę ir į dešinę. Atliekant pasukimą viena medžio viršūnė kyla, kita - leidžiasi. Dažniausiai ši operacija reikalinga pomedžių aukščiams pakeisti.

Pavyzdžiui, jei turėtume tokį medį:

       D
      / \
     /   \
    B     E
   / \
  A   C

jis galėtų būti pasuktas ir atrodyti taip:

     B
    / \
   /   \
  A     D
       / \ 
      C   E 

Tai būtų pasukimas į dešinę. Jei norėtume iš antro medžio pereiti prie pirmo, reikėtų atlikti pasukimą į kairę.

Jei užrašytume mūsų medžius kaip (kairysis pomedis, viršūnė, dešinysis pomedis), tada pirmas medis atrodytų taip: ((A, B, C), D, E), antras - taip: (A, B, (C, D, E)). Toks užrašymas gali padėti išsiaiškinti painius atvėjus.

Besibalansuojantys medžiai

---

• Raudonai-Juodas medis
• AVL medis
• B medis
• 2-3-4 medis

Nuorodos

---

• ADT lentelės ir medžiai (paskaitų konspektas).

Duomenų struktūros

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