Arbre 2-3-4
Contenu du snippet
#include <stdio.h>
#include <stdlib.h>
#define new(t) malloc(sizeof(t))
#define assert(b) if (!(b)){ printf("erreur ligne %d\n", __LINE__); exit(1); }
struct arbre234 {
int num;
struct arbre234 * node[4];
void * key[3];
};
void split4(struct arbre234 *ar, struct arbre234 **b, struct arbre234 **c, void **k){
assert(ar->num == 4);
*k = ar->key[1];
*b = new(struct arbre234);
*c = new(struct arbre234);
b[0]->num = 2;
c[0]->num = 2;
b[0]->node[0] = ar->node[0];
b[0]->node[1] = ar->node[1];
c[0]->node[0] = ar->node[2];
c[0]->node[1] = ar->node[3];
b[0]->key[0] = ar->key[0];
c[0]->key[0] = ar->key[2];
}
void addKey(struct arbre234 *a, int n, void * val){
int i;
assert(a!= NULL && (a->num == 2 || a->num == 3));
a->node[a->num] = NULL;
for (i = a->num - 1 ; i>n; i--){
a->key[i] = a->key[i-1];
}
a->key[n] = val;
a->num ++ ;
}
void insert__(struct arbre234 *p, int n, struct arbre234 *a, int cmp(void*, void*), void * val){
if (a == NULL){
addKey(p, n, val);
return;
}
assert(a->num == 2 || a->num == 3 || a->num == 4);
if (a->num == 4){
struct arbre234 *b, *c;
void *k;
int i;
split4(a, &b, &c, &k);
for (i=p->num ; i>n; i--)
p->node[i] = p->node[i-1];
for (i=p->num - 1 ; i>n; i--)
p->key[i] = p->key[i-1];
p->key[n] = k;
p->node[n] = b;
p->node[n+1] = c;
p->num ++;
free(a);
if (cmp(val, k) == -1){
insert__(p, 0, b, cmp, val);
}else{
insert__(p, 1, c, cmp, val);
}
}else{
if (cmp(val, a->key[0]) == -1){
insert__(a, 0, a->node[0], cmp, val);
}else if (a->num == 2){
insert__(a, 1, a->node[1], cmp, val);
}else{
if (cmp(val, a->key[1]) == -1){
insert__(a, 1, a->node[1], cmp, val);
}else{
insert__(a, 2, a->node[2], cmp, val);
}
}
}
}
void insert_(struct arbre234 *a, int cmp(void*, void*), void * val){
assert(a != NULL); assert(a->num == 2 || a->num == 3);
if ( cmp(val, a->key[0]) == -1 ){
insert__(a, 0, a->node[0], cmp, val);
}else{
if (a->num == 2){
insert__(a, 1, a->node[1], cmp, val);
}else{
if (cmp(val, a->key[1]) == -1 ){
insert__(a, 1, a->node[1], cmp, val);
}else{
printf("%d > %d\n", *((int*)val), *((int*)a->key[1]) );
insert__(a, 2, a->node[2], cmp, val);
}
}
}
}
struct arbre234 * insert(struct arbre234 *a, int cmp(void*, void*), void * val){
assert(a == NULL || a->num == 2 || a->num == 3 || a->num == 4);
if (a == NULL || a->num == 0){
struct arbre234 *ar = new(struct arbre234);
ar->num = 2;
ar->node[0] = NULL;
ar->node[1] = NULL;
ar->key[0] = val;
return ar;
}else if (a->num == 4){
struct arbre234 *r = new(struct arbre234);
r->num = 2;
split4(a, &r->node[0], &r->node[1], &r->key[0]);
insert_(r, cmp, val);
free(a);
return r;
}else{
insert_(a, cmp, val);
return a;
}
}
int cmpi(int a, int b){
if (a == b) return 0;
if (a < b) return -1;
return 1;
}
int cmpip(void *a, void *b){
return cmpi(*((int*)a), *((int*)b));
}
void spaces(int n){
int i;
for (i=0;i<n;i++) printf(" ");
}
void print_arbre(struct arbre234 *a, int t){
int i;
if (a == NULL) return;
print_arbre(a->node[0], t+1);
for (i=0;i<a->num-1;i++){
spaces(t); printf("%d\n", * ((int*) a->key[i]));
print_arbre(a->node[i+1], t+1);
}
}
void free_tree(struct arbre234 *a){
int i;
if (a == NULL) return;
for (i=0;i<a->num;i++)
free_tree(a->node[i]);
free(a);
}
int main(){
struct arbre234 * ar = NULL;
int tab[20] = {0,19,5,3,2,7,1,4,6,15,14,18,17,12,13};
int i;
for (i=0;i<20;i++){
printf("insertion de %d\n", tab[i]);
ar = insert(ar, cmpip, & tab[i] );
print_arbre(ar, 0);
}
free_tree(ar);
return 1;
}
Compatibilité : C
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.