Drzewo AVL C++

[flacznik (Kamil Kubik)]

Witam - na zajeciach dostalem za zadanie napisac kod do drzewa AVL :

#include using namespace std; class Wezel{ //definition d’un noeud } class Drzewo{ // public: virtual void inserer() = 0; virtual void supprimer() = 0; ~CArbre(){ }; } class DrzewoBinarne : public Drzewo{ //dziedziczy z drzewa //idorzucanie i kasowanie lisci } class DrzewoEkilibr : public DrzewoBinarne{ //dziedziczy od drzewa //obrot w lewo/prawo }

Znalazlem kod na stonie internetowej, ale nie wiem niestety jak go zaimplementowac do mojego zadania z dziedziczeniem i klasami virtualnymi… oto przyklad drzewa avl z ktorego chcialbym skorzystac:

struct AVLNode { AVLNode * p, * left, * right; int key, bf; }; // Definicja klasy obsługującej drzewo AVL //---------------------------------------- class AVL { public: AVLNode * root; // korzeń drzewa int count; // liczba węzłów AVL(); ~AVL(); AVLNode * rotationRR(AVLNode * A); AVLNode * rotationLL(AVLNode * A); AVLNode * rotationRL(AVLNode * A); AVLNode * rotationLR(AVLNode * A); bool insert(AVLNode * n); AVLNode * search(int key); int maxKey(AVLNode * x); int minKey(AVLNode * x); AVLNode * maxNode(AVLNode * x); AVLNode * minNode(AVLNode * x); AVLNode * pred(AVLNode * x); AVLNode * succ(AVLNode * x); AVLNode * remove(AVLNode * x); void preorder(AVLNode * x); void inorder(AVLNode * x); void postorder(AVLNode * x); void walk(AVLNode * x); void coutAVLcount(); };…

Prosze o pomoc w implementacji mojego drzewa w 4 klasach ktore dzidzicza jedna z drugiej… Z gory dzieki

[kostek135]

W czym dokładnie masz problem? Taka ogólna zasada tego to “budowanie domu z małych cegiełek”. Mamy węzeł, on przechowuje etykietę i ma jakąś listę incydencji. Drzewo, zapewne drzewo n-arne, mówiąc dokładniej, nieskierowany graf spójny, bez cykli. Składa się z węzłów. Drzewo binarne, to specjalny rodzaj drzewa n-arngo, którego zasada, jest taka, że każdy węzeł ma maksymalnie dwoje dzieci. AVL różni się już tylko tym od binary tree, że w trakcie wykonywania algorytmu, jeśli zostanie zachwiana równowaga drzewa, tj. wysokość |h| jakichkolwiek dwóch poddrzew wyniesie ostro więcej niż 1. należy wykonać rotację, która przywróci równowagę. Rotację wykonujemy na poddrzewach widzianych z węzła który zgłasza niezachowanie równowagi, ale to oczywiste chyba.