Drzewo Zbalansowane

Witam,

Jestem studentem pierwszego roku Informatyki Stosowanej. Na zaliczenie mam takie oto zadanie:

Proszę utworzyć drzewo zbalansowane, zawierające dane co najmniej 20 osób (imię, nazwisko, unikalny numer) porządkowanie alfabetycznie według nazwiska. Proszę zaimplementować algorytm zwracający wszystkie dane osoby o zadanym nazwisku.

Niestety nie wiele rozumiem z " Drzewa zbalansowanego " oraz "algorytm zwracający wszystkie dane osoby o zadanym nazwisku".

Nie proszę o wykonanie za mnie zadania a jedynie opis słowny obu zagadnień.

Poczytaj o AVL i drzeach czerwono-czarnych - to są drzewa zbalansowane.

http://edu.i-lo.tarnow.pl/inf/utils/002_roz/mp002.php

Mam takie trochę OT pytanie. Widział ktoś kiedyś jakąś implementacje drzew czerwono-czarnych nie będącą przepisaniem pseudokodu z Cormena? Jest to trochę większym wysiłkiem intelektualnym niż drzewo AVL, ale z pomocą kredek nie ma dużego problemu.

zwykłe BST przecie też może być zbalansowane
a kopiec też drzewo

drzewo niezbalansowane

a to jak naj bardziej

Witam ponownie,

Nie wiem czy dobrze to rozumiem. Jeśli wczytam listę 10 nazwisk to ich drzewo AVL będzie wyglądało w ten sposób?

Jak do tego ma się drzewo czerwono czarne?

Póki co klasy mam takie:

 class Person
{
      int ID; // unikalny identyfikator
      char nazwisko[30];
      char imie[30];
};

class Lista
{
      Person tab[30];
};

Do nich dojdą jeszcze metody przeszukiwanie nazwiska.

PS. Póki co zaczynam wprowadzanie do tematyki algorytmów i struktur danych więc proszę o wyrozumiałość.

Pozdrawiam

Mamy ci przekopiować tu opis RB z wikipedii czy mamy zrobić dla ciebie streszczenie?
Odpowiedź - ma się nijak.

http://qmatica.com/DataStructures/Trees/BST.html
tutaj możesz pooglądać sobie jak te drzewka działają
http://people.ksp.sk/~kuko/bak/
tutaj podobnie ale z opisem czemu tak sie dzieje