Arbre binaire D) Equilibrage (Balancing)
Description
Bonjour,
Le temps d'exécution des principales méthodes dépend largement de la hauteur de l'arbre binaire.
Le nombre maximal m de nœuds que l'on peut mettre dans un arbre de hauteur h est m = 2ʰ-1:
Inversement, on obtient la hauteur minimale hₘₙ d'un arbre binaire de n nœuds: hₘₙ = ⌈log₂(n+1)⌉.
En C ou C++: int hmn = ceil(log2(n+1));
Nous parlons (inhabituellement) d'un arbre binaire équilibré lorsque aucun niveau de ses nœuds ne dépasse la hauteur minimale (c'est-à-dire lorsque sa hauteur maximale est égale à sa hauteur minimale).
Attention: la disposition des nœuds dans un arbre équilibré n'est pas unique (exemple avec h=3, n=5):
La méthode habituelle pour équilibrer un arbre binaire de recherche quelconque semble être celle qui utilise un array (ou vector) d'adresses do nœuds.
En connaitriez-vous d'autres ?
Il est donc inutile d'utiliser vector.
Bonne lecture ...
CodeS-SourceS: Arbre binaire B) Affichage (simple)
CodeS-SourceS: Arbre binaire C) Recherche
WikipediA: Binary search tree
GeeksforGeeks: Convert a normal BST to Balanced BST
Le temps d'exécution des principales méthodes dépend largement de la hauteur de l'arbre binaire.
Le nombre maximal m de nœuds que l'on peut mettre dans un arbre de hauteur h est m = 2ʰ-1:
h m=2ʰ-1 arbre
0 0 -
1 1 00
2 3 01
00 02
3 7 03
01 05
00 02 04 06
4 15 07
03 11
01 05 09 13
00 02 04 06 08 10 12 14
5 31 ...
Inversement, on obtient la hauteur minimale hₘₙ d'un arbre binaire de n nœuds: hₘₙ = ⌈log₂(n+1)⌉.
En C ou C++: int hmn = ceil(log2(n+1));
Nous parlons (inhabituellement) d'un arbre binaire équilibré lorsque aucun niveau de ses nœuds ne dépasse la hauteur minimale (c'est-à-dire lorsque sa hauteur maximale est égale à sa hauteur minimale).
Attention: la disposition des nœuds dans un arbre équilibré n'est pas unique (exemple avec h=3, n=5):
3 │ 1 │ 2 │
1 4 │ 0 2 │ 1 3 │ ...
0 2 │ 3 4 │ 0 4 │
La méthode habituelle pour équilibrer un arbre binaire de recherche quelconque semble être celle qui utilise un array (ou vector) d'adresses do nœuds.
En connaitriez-vous d'autres ?
Code avec complément pour l'équilibrage
//// TreeNode.h
struct TreeObj {
virtual int Compare(TreeObj *obj)=0;
}; // return <0: this < obj; return 0: this == obj; return >0: this > obj
struct TreeNode {
TreeNode *left,*right;
TreeObj *object;
TreeNode(TreeObj *obj) {left=0; right=0; object=obj;} // constructor: obj != 0
bool InsertRecur(TreeNode *nod) { // récursif
int cmp=object->Compare(nod->object);
if (cmp<0) {
if (nod->left) return Insert(nod->left);
else {nod->left=this; return true;}
} else if (cmp>0) {
if (nod->right) return Insert(nod->right);
else {nod->right=this; return true;}
}
return false; // cmp==0
}
bool Insert(TreeNode *nod) { // non récursif (itératif): nod != 0
int cmp;
do {
cmp=object->Compare(nod->object);
if (cmp<0) {
if (nod->left) nod=nod->left; else {nod->left=this; return true;}
} else if (cmp>0) {
if (nod->right) nod=nod->right; else {nod->right=this; return true;}
}
} while (cmp);
return false;
}
void TraversalRecur(void (*Do)(TreeNode*)) { // récursif
if (left) left->TraversalRecur(Do);
Do(this);
if (right) right->TraversalRecur(Do);
}
void Traversal(void (*Do)(TreeNode*)) { // non récursif (itératif) avec stack
std::stack<TreeNode*> stk;
TreeNode *nod=this;
do {
while (nod) {stk.push(nod); nod=nod->left;}
if (stk.empty()) return;
nod=stk.top(); stk.pop();
Do(nod);
nod=nod->right;
} while (1);
}
TreeNode *SearchRecur(TreeObj *obj) { // récursif
int cmp=object->Compare(obj);
if (cmp<0)
{if (left) return left->SearchRecur(obj); else return 0;}
if (cmp>0)
{if (right) return right->SearchRecur(obj); else return 0;}
return this;
}
TreeNode *Search(TreeObj *obj) { // non récursif (itératif)
int cmp;
TreeNode *nod=this;
do {
cmp=nod->object->Compare(obj);
if (cmp<0) {
if (nod->left) nod=nod->left;
} else if (cmp>0) {
if (nod->right) nod=nod->right;
}
} while (cmp!=0);
return nod;
}
void ToVectorRecur(std::vector<TreeNode*> *arr) {
if (left) left->ToVectorRecur(arr);
arr->push_back(this);
if (right) right->ToVectorRecur(arr);
}
void ToVector(std::vector<TreeNode*> *arr) {
std::stack<TreeNode*> stk;
TreeNode *nod=this;
do {
while (nod) {stk.push(nod); nod=nod->left;}
if (stk.empty()) return;
nod=stk.top(); stk.pop();
arr->push_back(nod);
nod=nod->right;
} while (1);
}
int SizeRecur() { // récursif
return 1+((left)?left->SizeRecur():0)+((right)?right->SizeRecur():0);
}
int Size() { // non récursif (itératif) avec stack
std::stack<TreeNode*> stk;
TreeNode *nod=this;
int siz=0;
do {
while (nod) {stk.push(nod); nod=nod->left;}
if (stk.empty()) return siz;
nod=stk.top(); stk.pop();
++siz;
nod=nod->right;
} while (1);
}
};
TreeNode* ArrayToTreeRecur(TreeNode *arr[],int a,int b) { // arr[] ordonné !
if (a>b) return 0;
int m=(a+b)/2;
TreeNode *r=arr[m];
r->left=ArrayToTreeRecur(arr,a,m-1);
r->right=ArrayToTreeRecur(arr,m+1,b);
return r;
}
TreeNode* ArrayToTree(TreeNode *arr[],int a,int b) { // arr[] ordonné !
if (a>b) return 0;
int m,h=0,A[32],B[32];
TreeNode *r=arr[(a+b)/2];
do {
if (a=b) {arr[a]->left=arr[a]->right=0; continue;}
m=(a+b)/2;
A[h]=m+1; B[h]=b; ++h;
arr[m]->left=*arr+(m-1)/2;
arr[m]->right=*arr+(m+1)/2;
b=a+m-1;
} while (h>0);
return r;
}Comme le montre la dernière ligne de l'output sur la console, les arrays A[32] et B[32] (► TreeNode* VectorToTree(TreeNode *arr[],int a,int b) {...}) suffisent pour un nombre de nœuds plus grand qu'un milliard !
Il est donc inutile d'utiliser vector.
Insert 48 objets:
HQ H M AYL LF XF RCV C GG WK
NQDU WF FOZV RTK PR P G RP RVYS MWCY
Y C PEV KEF MZ IMKK SVW R NZK CXF
TL GYP FAD OO FXZ CO JUV VABO GPO YLF
BNPL VRVI YA YEH Q QRQP X J
┌── AYL
│ │ ┌── BNPL
│ └── C
│ │ ┌── CO
│ │ ┌── CXF
│ │ │ └── FAD
│ │ ┌── FOZV
│ │ │ │ ┌── FXZ
│ │ │ └── G
│ └── GG
│ │ ┌── GPO
│ └── GYP
┌── H
── HQ
│ ┌── IMKK
│ │ │ ┌── J
│ │ └── JUV
│ ┌── KEF
│ ┌── LF
└── M
│ ┌── MWCY
│ │ └── MZ
│ ┌── NQDU
│ │ │ ┌── NZK
│ │ │ │ └── OO
│ │ │ ┌── P
│ │ │ │ └── PEV
│ │ └── PR
│ │ │ ┌── Q
│ │ │ │ └── QRQP
│ │ └── R
│ ┌── RCV
│ │ │ ┌── RP
│ │ │ ┌── RTK
│ │ │ │ └── RVYS
│ │ │ │ └── SVW
│ │ │ │ └── TL
│ │ │ │ └── VABO
│ │ │ │ └── VRVI
│ │ │ ┌── WF
│ │ └── WK
│ │ └── X
└── XF
└── Y
│ ┌── YA
│ │ └── YEH
└── YLF
Size=47
Après équilibrage:
┌── AYL
│ └── BNPL
┌── C
│ └── CO
│ └── CXF
┌── FAD
│ │ ┌── FOZV
│ │ │ └── FXZ
│ └── G
│ └── GG
│ └── GPO
┌── GYP
│ │ ┌── H
│ │ │ └── HQ
│ │ ┌── IMKK
│ │ │ └── J
│ │ │ └── JUV
│ └── KEF
│ │ ┌── LF
│ │ │ └── M
│ └── MWCY
│ └── MZ
│ └── NQDU
── NZK
│ ┌── OO
│ │ └── P
│ ┌── PEV
│ │ └── PR
│ │ └── Q
│ ┌── QRQP
│ │ │ ┌── R
│ │ │ │ └── RCV
│ │ └── RP
│ │ └── RTK
│ │ └── RVYS
└── SVW
│ ┌── TL
│ │ └── VABO
│ ┌── VRVI
│ │ └── WF
│ │ └── WK
└── X
│ ┌── XF
│ │ └── Y
└── YA
└── YEH
└── YLF
Size=47
Après équilibrage:
┌── AYL
│ └── BNPL
┌── C
│ └── CO
│ └── CXF
┌── FAD
│ │ ┌── FOZV
│ │ │ └── FXZ
│ └── G
│ └── GG
│ └── GPO
┌── GYP
│ │ ┌── H
│ │ │ └── HQ
│ │ ┌── IMKK
│ │ │ └── J
│ │ │ └── JUV
│ └── KEF
│ │ ┌── LF
│ │ │ └── M
│ └── MWCY
│ └── MZ
│ └── NQDU
── NZK
│ ┌── OO
│ │ └── P
│ ┌── PEV
│ │ └── PR
│ │ └── Q
│ ┌── QRQP
│ │ │ ┌── R
│ │ │ │ └── RCV
│ │ └── RP
│ │ └── RTK
│ │ └── RVYS
└── SVW
│ ┌── TL
│ │ └── VABO
│ ┌── VRVI
│ │ └── WF
│ │ └── WK
└── X
│ ┌── XF
│ │ └── Y
└── YA
└── YEH
└── YLF
Size=47
n = 0, h = 0
n = 1, h = 1
n = 2, h = 2
n = 3, h = 2
n = 4, h = 3
n = 5, h = 3
n = 6, h = 3
n = 7, h = 3
n = 8, h = 4
n = 9, h = 4
n = 10, h = 4
n = 11, h = 4
n = 12, h = 4
n = 13, h = 4
n = 14, h = 4
n = 15, h = 4
n = 16, h = 5
n = 17, h = 5
n = 18, h = 5
n = 19, h = 5
n = 1000000000, h = 30
Bonne lecture ...
Liens:
CodeS-SourceS: Arbre binaire A) Insertion et ParcoursCodeS-SourceS: Arbre binaire B) Affichage (simple)
CodeS-SourceS: Arbre binaire C) Recherche
WikipediA: Binary search tree
GeeksforGeeks: Convert a normal BST to Balanced BST
Codes Sources
A voir également
- Arbre binaire D) Equilibrage (Balancing)
- Calculer la hauteur d'un arbre ✓ - Forum C / C++ / C++.NET
- Arbre de tournoi - Forum PHP
- Comment dessiner un arbre généalogique - Forum PHP
- Comment dessiner un arbre facilement - Forum Java
- Générateur arbre généalogique - Forum Java
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.