Structuri de Date și Algoritmi - Curs 4

Curs 4 – Arbori binari

Structura unui nod. Definirea nodului

Nod

Arbore

Curs 4 – Arbori binari

Preordine (RSD)

Inordine (SRD)

Postordine (SDR)

Curs 4 – Arbori binari

Curs 4 – Arbori binari de căutare

< Rad > Rad

Rotire simplă dreapta (inserăm un nod în A)

Rotire simplă stânga (inserăm un nod în C)

Rotire dublă dreapta: stânga-dreapta (inserăm un nod în B1 sau B2)

Rotire dublă stânga: dreapta-stânga (inserăm un nod în B1 sau B2)

Ştergerea unui nod

Ştergere directă dacă nodul are un copil sau e nod frunză

Dacă nodul are şi subarbore drept şi stâng, se determină minimul în subarborele drept. El înlocuieşte nodul considerat, fiind ulterior şters.

!!! Reechilibrarea arborelui (de la părintele nodului şters, spre rădăcină)

Cazuri întâlnite la reechilibrare – rotiri simple (4 cazuri)

Caz 1 – rotire simplă stânga

Cazuri întâlnite la reechilibrare – rotiri simple (4 cazuri)

Caz 2 – rotire simplă dreapta

Cazuri întâlnite la reechilibrare – rotiri simple (4 cazuri)

Caz 3 – rotire simplă stânga

Cazuri întâlnite la reechilibrare – rotiri simple (4 cazuri)

Caz 4 – rotire simplă dreapta

Cazuri întâlnite la reechilibrare – rotiri duble (2 cazuri)

Caz 1 – rotire dublă stânga (dreapta – stânga)