Arbre binaire D) Equilibrage (Balancing)

Soyez le premier à donner votre avis sur cette source.

Vue 579 fois - Téléchargée 47 fois

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:
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 Parcours
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

 

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de William VOIROL

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.