Les arbres binaires

Arbre binaire

Les arbres binaires se définissent de façon récursive. Un arbre binaire T est une relation définie sur un ensemble fini de nœuds et qui satisfait une des deux conditions suivantes:

• l’ensemble ne contient aucun nœud, ou• l’ensemble est constitué de trois sous-ensembles

disjoints de nœuds:– un nœud unique appelé racine– un arbre binaire appelé sous-arbre de gauche– un arbre binaire appelé sous-arbre de droite.

Exemple d’arbre binaire

Notation: Noeud, enfant,arête, parent, ancêtre,

descendant, chemin, profondeur, hauteur, niveau, feuille, noeud interne, sous-arbre.

Arbre binaire plein et complet

Arbre binaire plein: Chaque noeud est soit une feuille ou possède exactement deux enfants

Arbre binaire complet: Si la hauteur de l’arbre est d, alors tous les niveau sont complets, sauf possiblement le dernier. Les feuilles au dernier niveau sont complètement à gauche.

Arbre binaire plein (1)

Théorème: Dans un arbre binaire plein, le nombre de feuilles est un de plus que le nombre de noeuds internes.

Preuve (par induction mathématique sur le nombre de noeuds internes):

Base: S’il y a un seul noeud interne alors le nombre de feuilles est 2.

Hypothèse d’induction: Supposons qu’un arbre binaire plein avec n-1 noeuds internes contient n feuilles.

Arbre binaire plein (2)

Pas d’induction: Soit T, un arbre binaire avec n noeuds internes.

Il existe un nœud interne P dont les deux enfants (P1 et P2) sont des feuilles.

Soit T’ l’arbre obtenu en enlevant P1 et P2 de T.

Donc, T’ contient n-1 nœuds internes

Par hypothèse d’induction, T’ est un arbre binaire plein avec n feuilles

Arbre binaire plein (3)

Toutes les feuilles de T’ (sauf P) sont aussi des feuilles de T.

P est une feuille de T’ mais pas de T

Le nombre de feuille dans T est donc:

nombre de feuilles dans T’- le nœud P

+ les deux feuilles P1 et P2

Donc T contient n+1 feuilles.

Classe abstraite

template <class Elem> class BinNode {public: virtual Elem& val() = 0; virtual void setVal(const Elem&) = 0; virtual BinNode* left() const = 0; virtual void setLeft(BinNode*) = 0; virtual BinNode* right() const = 0; virtual void setRight(BinNode*) = 0; virtual bool isLeaf() = 0;};

Classe avec pointeurs (1)

// Binary tree node classtemplate <class Elem>class BinNodePtr : public BinNode<Elem> {private: Elem it; // La valeur du noeud BinNodePtr* lc; // pointe à gauche BinNodePtr* rc; // pointe à droitepublic:BinNodePtr() { lc = rc = NULL; }

BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) { it = e; lc = l; rc = r; }

Classe avec pointeurs (2) Elem& val() { return it; }

void setVal(const Elem& e) { it = e; } BinNode<Elem>* left() const { return lc; } void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; } BinNode<Elem>* right() const { return rc; } void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; } bool isLeaf() { return (lc == NULL) && (rc == NULL); }

};

Parcours (1)

Une méthode permettant de visiter tous les nœuds d’un arbre dans un ordre quelconque est appelée un parcours (ou une fouille).

Un parcours où chaque nœud est visité exactement une fois est appelé une énumération.

Parcours (2)

• Parcours en préordre: on visite un nœud avant de visiter ses enfants.

• Parcours en postordre: on visite un nœud apès avoir visiter ses enfants.

• Parcours en ordre: on visite d’abord le sous-arbre de gauche, puis la racine et enfin le sous-arbre de droite.

Parcours (3)

template <class Elem>void preorder(BinNode<Elem>* subroot) { if (subroot == NULL) return; visit(subroot); // Faire une action preorder(subroot->left()); preorder(subroot->right());}

Exemple de parcours

// Retourne le nombre de nœuds dans l’arbretemplate <class Elem>int count(BinNode<Elem>* subroot) { if (subroot == NULL) return 0; // Rien à compter return 1 + count(subroot->left()) + count(subroot->right());}

Implémentation (1)

Implémentation (2)

caxx )2(4

Implémentation avec union(1)

enum Nodetype {leaf, internal};

class VarBinNode { // Nœud génériquepublic: Nodetype mytype; // Type de nœud

union { struct { // Nœud interne VarBinNode* left; VarBinNode* right; Operator opx; } intl; Operand var; // Feuille };

Implémentation avec union(2) // Constructeur pour les feuilles

VarBinNode(const Operand& val) { mytype = leaf; var = val; } // Constructeur pour les nœuds internes VarBinNode(const Operator& op, VarBinNode* l, VarBinNode* r) {

mytype = internal; intl.opx = op; intl.left = l; intl.right = r; } bool isLeaf() { return mytype == leaf; } VarBinNode* leftchild() { return intl.left; } VarBinNode* rightchild() { return intl.right; }};

Implémentation avec union(3)

// Parcours en préordrevoid traverse(VarBinNode* subroot) {if (subroot == NULL) return;

if (subroot->isLeaf()) cout << ”Feuille: “ << subroot->var << endl; else { cout << ”Nœud interne: “ << subroot->intl.opx << endl; traverse(subroot->leftchild()); traverse(subroot->rightchild()); }}

Héritage (1)

class VarBinNode { // Classe abstraite public: virtual bool isLeaf() = 0;};

// Feuilleclass LeafNode : public VarBinNode { private: Operand var; public: LeafNode(const Operand& val) { var = val; } // Constructor bool isLeaf() { return true; } Operand value() { return var; }};

Héritage (2)

// Nœud interneclass IntlNode : public VarBinNode {private: VarBinNode* left; VarBinNode* right; Operator opx; public: IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) { opx = op; left = l; right = r; } bool isLeaf() { return false; } VarBinNode* leftchild() { return left; } VarBinNode* rightchild() { return right; }

Operator value() { return opx; }};

Héritage (3)

// Parcours en préordrevoid traverse(VarBinNode *subroot) { if (subroot == NULL) return; if (subroot->isLeaf()) // Feuille cout << "Leaf: " << ((LeafNode*)subroot)->value() << endl; else { // Nœud interne cout << "Internal: " << ((IntlNode*)subroot)->value() << endl; traverse(((IntlNode*)subroot)->leftchild()); traverse(((IntlNode*)subroot)->rightchild()); }}

Espace mémoire (1)

Du théorème sur les arbre binaire plein:• La moitié des pointeurs sont null.

If leaves store only data, then overhead depends on whether the tree is full.

Ex: Tous les nœuds sont similaires avec deux pointeurs aux enfants.

• Espace total requis: (2p + d)n• Espace pour pointeurs: 2pn• Si p = d, alors l’espace pour pointeurs est 2p/(2p + d) = 2/3.

Espace mémoire(2)

Si on élimine les pointeurs aux feuilles, la fraction d’espace perdu est alors:

Ce qui fait 1/2 si p = d.

Remarque: De l’espace supplémentaire est tout de même nécessaire afin de pouvoir différencier une feuille d’un nœud interne.

dp

p

dnpn

pn

)2)(2/(

)2)(2/(

Implémentation avec tableau (1)

Position 0 1 2 3 4 5 6 7 8 9 10 11

Parent -- 0 0 1 1 2 2 3 3 4 4 5

Fils de Gauche 1 3 5 7 9 11 -- -- -- -- -- --

Fils de Droite 2 4 6 8 10 -- -- -- -- -- -- --

Frère de gauche -- -- 1 -- 3 -- 5 -- 7 -- 9 --

Frère de droite -- 2 -- 4 -- 6 -- 8 -- 10 -- --

Implémentation avec tableau(2)

Parent (r) = (r-1)/2 si r0

Leftchild(r) = 2r+1 si 2r+1 < n

Rightchild(r) = 2r+2 si 2r+2 < n

Leftsibling(r) = r-1 si r>0 est pair

Rightsibling(r) = r+1 si rn est impair