Modèle d'arbre équilibré ordinaire
L'idée fondamentale consiste à maintenir l'équilibre d'un arbre via des opérations de division (split) et de fusion (merge). Les opérations de base incluent l'insertion, la suppression, la recherche par rang, la recherche de valeur, ainsi que la récupération du prédécesseur et du successeur. Les opérations avancées permettent la persistance et le traitement d'intervalles.
Cette structure maintient un ensemble de données où chaque nœud possède une valeur. Selon les propriétés de l'arbre binaire de recherche (BST), l'arbre respecte l'ordre des valeurs. De plus, le FHQ-Treap utilise une valeur auxliiaire, généralement aléatoire, pour assurer l'équilibre, satisfaisant ainsi la propriété de tas.
Structure de base et fonctions utilitaires
struct Noeud {
int gauche, droite, cle, priorite, nbElements;
} arbre[TAILLE];
int compteur = 0, racine = 0;
void mettreAJourTaille(int idx) {
arbre[idx].nbElements = 1 + arbre[arbre[idx].gauche].nbElements + arbre[arbre[idx].droite].nbElements;
}
int creerNoeud(int valeur) {
compteur++;
arbre[compteur].nbElements = 1;
arbre[compteur].cle = valeur;
arbre[compteur].priorite = rand();
return compteur;
}
Division (Split) par valeur
Cette fonction divise un arbre en deux sous-arbres en fonction d'une valeur clé. Si la clé du nœud courant est inférieure ou égale à k, le nœud et son sous-arbre gauche appartiennent à l'arbre de gauche, et on récure sur le sous-arbre droit. Sinon, le nœud va dans l'arbre de droite, et on traite le sous-arbre gauche.
void diviserParValeur(int noeud, int k, int &gauche, int &droite) {
if (!noeud) { gauche = droite = 0; return; }
if (arbre[noeud].cle <= k) {
gauche = noeud;
diviserParValeur(arbre[noeud].droite, k, arbre[noeud].droite, droite);
} else {
droite = noeud;
diviserParValeur(arbre[noeud].gauche, k, gauche, arbre[noeud].gauche);
}
mettreAJourTaille(noeud);
}
Division (Split) par rang
Divise l'arbre en deux parties : la première contient les k premiers éléments. Si k est inférieur ou égal à la taille du sous-arbre gauche, on divise ce sous-arbre ; sinon, on ajuste k en soustaryant la taille du sous-arbre gauche et le nœud courant, puis on traite le sous-arbre droit.
void diviserParRang(int noeud, int k, int &gauche, int &droite) {
if (!noeud) { gauche = droite = 0; return; }
int tailleGauche = arbre[arbre[noeud].gauche].nbElements;
if (k <= tailleGauche) {
droite = noeud;
diviserParRang(arbre[noeud].gauche, k, gauche, arbre[noeud].gauche);
} else {
gauche = noeud;
diviserParRang(arbre[noeud].droite, k - tailleGauche - 1, arbre[noeud].droite, droite);
}
mettreAJourTaille(noeud);
}
Fusion (Merge)
Fusionne deux arbres en respectant la propriété BST et la priorité de tas. Si la priorité du premier arbre est plus petite, il devient la racine, et on fusionne récursivement son sous-arbre droit avec le second arbre. Sinon, le second arbre devient la racine, et on fusionne le premier avec son sous-arbre gauche.
int fusionner(int gauche, int droite) {
if (!gauche || !droite) return gauche + droite;
if (arbre[gauche].priorite < arbre[droite].priorite) {
arbre[gauche].droite = fusionner(arbre[gauche].droite, droite);
mettreAJourTaille(gauche);
return gauche;
} else {
arbre[droite].gauche = fusionner(gauche, arbre[droite].gauche);
mettreAJourTaille(droite);
return droite;
}
}
Recherche du k-ième élément
Pour trouver le nœud avec le rang k, on parcourt l'arbre itérativement. Si k est inférieur ou égal à la taille du sous-arbre gauche, on va à gauche ; si k correspond au rang du nœud courant, on le retourne ; sinon, on ajuste k et on va à droite.
int obtenirRang(int noeud, int k) {
while (true) {
int tailleGauche = arbre[arbre[noeud].gauche].nbElements;
if (k <= tailleGauche) {
noeud = arbre[noeud].gauche;
} else if (k == tailleGauche + 1) {
return noeud;
} else {
k -= tailleGauche + 1;
noeud = arbre[noeud].droite;
}
}
}
Opérations de base sur l'arbre
Insertion
Divise l'arbre selon la valeur, fusionne l'arbre gauche avec un nouveau nœud, puis fusionne le résultat avec l'arbre droit.
if (operation == 1) { // insertion
int g, d;
diviserParValeur(racine, valeur, g, d);
racine = fusionner(fusionner(g, creerNoeud(valeur)), d);
}
Suppression
Pour supprimer un élément, divise l'arbre en trois parties : inférieure à la valeur, égale à la valeur, et supérieure. La partie égale est traitée en fusionnant ses sous-arbres, ignorant ainsi le nœud racine, puis on recombine le tout.
if (operation == 2) { // suppression
int g, m, d;
diviserParValeur(racine, valeur, g, d);
diviserParValeur(g, valeur - 1, g, m);
m = fusionner(arbre[m].gauche, arbre[m].droite);
racine = fusionner(fusionner(g, m), d);
}
Rang par valeur
Pour obtenir le rang d'une valeur, on divise l'arbre pour isoler les éléments inférieurs ; la taille de cet arbre plus un donne le rang.
if (operation == 3) { // rang par valeur
int g, d;
diviserParValeur(racine, valeur - 1, g, d);
printf("%d\n", arbre[g].nbElements + 1);
racine = fusionner(g, d);
}
Prédécesseur et successeur
Pour le prédécesseur, divise l'arbre pour obtenir les éléments inférieurs, puis récupère le dernier élément de cet arbre. Pour le successeur, divise pour obtenir les éléments supérieurs et récupère le premier.
if (operation == 5) { // prédécesseur
int g, d;
diviserParValeur(racine, valeur - 1, g, d);
printf("%d\n", arbre[obtenirRang(g, arbre[g].nbElements)].cle);
racine = fusionner(g, d);
}
if (operation == 6) { // successeur
int g, d;
diviserParValeur(racine, valeur, g, d);
printf("%d\n", arbre[obtenirRang(d, 1)].cle);
racine = fusionner(g, d);
}
Arbre équilibré avancé pour les opérations d'intervalle
Strucutre étendue avec marqueur de retournement
struct NoeudAvance {
int gauche, droite, cle, priorite, nbElements, marqueur;
} arbreAvance[TAILLE];
void appliquerRetournement(int noeud) {
if (noeud && arbreAvance[noeud].marqueur) {
arbreAvance[noeud].marqueur = 0;
std::swap(arbreAvance[noeud].gauche, arbreAvance[noeud].droite);
if (arbreAvance[noeud].gauche) arbreAvance[arbreAvance[noeud].gauche].marqueur ^= 1;
if (arbreAvance[noeud].droite) arbreAvance[arbreAvance[noeud].droite].marqueur ^= 1;
}
}
Division avec propagation
void diviserAvecPropagation(int noeud, int k, int &gauche, int &droite) {
if (!noeud) { gauche = droite = 0; return; }
appliquerRetournement(noeud);
int tailleGauche = arbreAvance[arbreAvance[noeud].gauche].nbElements;
if (k <= tailleGauche) {
droite = noeud;
diviserAvecPropagation(arbreAvance[noeud].gauche, k, gauche, arbreAvance[noeud].gauche);
} else {
gauche = noeud;
diviserAvecPropagation(arbreAvance[noeud].droite, k - tailleGauche - 1, arbreAvance[noeud].droite, droite);
}
mettreAJourTailleAvancee(noeud);
}
Fusion avec propagation
int fusionnerAvance(int gauche, int droite) {
if (!gauche || !droite) return gauche + droite;
appliquerRetournement(gauche);
appliquerRetournement(droite);
if (arbreAvance[gauche].priorite < arbreAvance[droite].priorite) {
arbreAvance[gauche].droite = fusionnerAvance(arbreAvance[gauche].droite, droite);
mettreAJourTailleAvancee(gauche);
return gauche;
} else {
arbreAvance[droite].gauche = fusionnerAvance(gauche, arbreAvance[droite].gauche);
mettreAJourTailleAvancee(droite);
return droite;
}
}
Retournement d'intervalle
Pour retourner l'intervalle [l, r], divise l'arbre pour extraire la partie cible, inverse son marqueur, puis recombine.
void retournerIntervalle(int l, int r) {
int a, b, c, d;
diviserParRangAvance(racineAvancee, r, a, b);
diviserParRangAvance(a, l - 1, c, d);
arbreAvance[d].marqueur ^= 1;
racineAvancee = fusionnerAvance(fusionnerAvance(c, d), b);
}
Construction initiale
int construireArbre(int debut, int fin) {
if (debut > fin) return 0;
int milieu = (debut + fin) >> 1;
int noeud = creerNoeudAvance(milieu);
arbreAvance[noeud].gauche = construireArbre(debut, milieu - 1);
arbreAvance[noeud].droite = construireArbre(milieu + 1, fin);
mettreAJourTailleAvancee(noeud);
return noeud;
}