Lezione numero 21 del corso di Algoritmi e Strutture Dati 2020/2021

Lezione numero 21 del corso di Algoritmi e Strutture Dati 2020/2021, Università di Ferrara - Alberi red-black. Nota: le lezioni 6,8,9,12,18,22,24,29 e 30 sono dedicate a esercizi e laboratorio, e riservate ai soli studenti dell' Università di Ferrara. Su questo canale vengono pubblicate unicamente le lezioni di teoria.

[@guidosciavicco4969]

Al minuto 23 il ragionamento è invertito: se x è rosso, allora l'altezza nera di A e B sará certamente inferiore (di uno) rispetto all'altezza nera di x, mentre se x è nero, allora l'altezza nera di A e B potrebbe essere la stessa (lo è in un sottoalbero se la sua radice è rossa) oppure essere inferiore (di uno) come nel caso precedente. In ogni caso la conclusione è corretta. Inoltre, nell'annotare gli appunti, ho invertito nomi dei casi 2 e 3 del 'fixup'.