{"id":30530,"date":"2019-10-31T21:36:01","date_gmt":"2019-10-31T18:36:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska\/"},"modified":"2019-10-31T21:36:01","modified_gmt":"2019-10-31T18:36:01","slug":"binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","status":"publish","type":"post","link":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","title":{"rendered":"Arbre binaire ou comment pr\u00e9parer un arbre de recherche binaire","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Pr\u00e9lude<\/h2>\n

\nCet article est d\u00e9di\u00e9 aux arbres binaires de recherche. R\u00e9cemment, j'ai \u00e9crit un article sur la compression des donn\u00e9es par la m\u00e9thode de Huffman.<\/a><\/noindex> \u00c0 l'\u00e9poque, je n'ai pas beaucoup pr\u00eat\u00e9 attention aux arbres binaires, car les m\u00e9thodes de recherche, d'insertion et de suppression n'\u00e9taient pas pertinentes. Maintenant, j'ai d\u00e9cid\u00e9 d'\u00e9crire un article sp\u00e9cifiquement sur les arbres. Commen\u00e7ons. <\/p>\n

Un arbre est une structure de donn\u00e9es compos\u00e9e de n\u0153uds reli\u00e9s par des ar\u00eates. On peut dire qu'un arbre est un cas particulier d'un graphe. Voici un exemple d'arbre : <\/p>\n

\"Arbre
\n
\nCe n'est pas un arbre binaire de recherche ! Tout est sous le cat !
\n<\/a><\/noindex><\/p>\n

Terminologie<\/h2>\n

<\/p>\n

Racine<\/h4>\n

\nLa racine de l'arbre<\/i> est le n\u0153ud le plus \u00e9lev\u00e9. Dans cet exemple, il s'agit du n\u0153ud A. Dans un arbre, il ne peut y avoir qu'un seul chemin menant de la racine \u00e0 n'importe quel autre n\u0153ud ! En r\u00e9alit\u00e9, tout n\u0153ud peut \u00eatre consid\u00e9r\u00e9 comme la racine de son sous-arbre correspondant.<\/p>\n

Parents\/enfants<\/h4>\n

\nTous les n\u0153uds, \u00e0 l'exception de la racine, ont exactement une ar\u00eate reliant vers un autre n\u0153ud. Le n\u0153ud situ\u00e9 au-dessus du n\u0153ud actuel s'appelle le parent<\/i> de ce n\u0153ud. Le n\u0153ud situ\u00e9 en dessous du n\u0153ud actuel et connect\u00e9 \u00e0 lui s'appelle l'enfant<\/i> de ce n\u0153ud. Prenons un exemple. Si nous prenons le n\u0153ud B, alors son parent sera le n\u0153ud A, et ses enfants seront les n\u0153uds D, E et F.<\/p>\n

Feuille<\/h4>\n

\nUn n\u0153ud qui n'a pas d'enfants sera appel\u00e9 feuille de l'arbre. Dans l'exemple, les feuilles seront les n\u0153uds D, E, F, G, I, J, K.<\/p>\n

C'est la terminologie de base. D'autres concepts seront abord\u00e9s plus loin. Donc, un arbre binaire est un arbre dans lequel chaque n\u0153ud aura au maximum deux enfants. Comme vous l'avez devin\u00e9, l'arbre de l'exemple ne sera pas binaire, car les n\u0153uds B et H ont plus de deux enfants. Voici un exemple d'arbre binaire :<\/p>\n

\"Arbre
\n
\nLes n\u0153uds de l'arbre peuvent contenir n'importe quelle information. Un arbre binaire de recherche est un arbre binaire dont les propri\u00e9t\u00e9s suivantes sont caract\u00e9ristiques :<\/p>\n

    \n
  1. Les deux sous-arbres - gauche et droit - sont des arbres binaires de recherche.<\/li>\n
  2. Pour tous les n\u0153uds du sous-arbre gauche d'un n\u0153ud X donn\u00e9, les valeurs des cl\u00e9s de donn\u00e9es sont inf\u00e9rieures \u00e0 la valeur de la cl\u00e9 de donn\u00e9es du n\u0153ud X lui-m\u00eame.<\/li>\n
  3. Pour tous les n\u0153uds du sous-arbre droit d'un n\u0153ud X donn\u00e9, les valeurs des cl\u00e9s de donn\u00e9es sont sup\u00e9rieures ou \u00e9gales \u00e0 la valeur de la cl\u00e9 de donn\u00e9es du n\u0153ud X lui-m\u00eame. <\/li>\n<\/ol>\n

    Cl\u00e9<\/i> une sorte de caract\u00e9ristique du n\u0153ud (par exemple, un nombre). La cl\u00e9 est n\u00e9cessaire pour pouvoir trouver l'\u00e9l\u00e9ment de l'arbre correspondant \u00e0 cette cl\u00e9. Exemple d'arbre binaire de recherche :<\/p>\n

    \"Arbre
    \n<\/p>\n

    Repr\u00e9sentation de l'arbre<\/h2>\n

    \nAu fur et \u00e0 mesure de l'avancement, je fournirai quelques (possiblement incomplets) extraits de code pour am\u00e9liorer votre compr\u00e9hension. Le code complet sera \u00e0 la fin de l'article. <\/p>\n

    L'arbre est constitu\u00e9 de n\u0153uds. La structure d'un n\u0153ud :<\/p>\n

    public class Node<T> {\n    private T data;\n    private int key;\n    private Node<T> leftChild;\n    private Node<T> rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n    public Node<T> getLeftChild() {\n        return leftChild;\n    }\n\n    public Node<T> getRightChild() {\n        return rightChild;\n    }\n\/\/...autres m\u00e9thodes du n\u0153ud\n}\n<\/code><\/pre>\n
    \nChaque n\u0153ud a deux descendants (il est tout \u00e0 fait possible que les descendants leftChild et\/ou rightChild contiennent la valeur null). Vous avez probablement compris que dans ce cas, le nombre data repr\u00e9sente les donn\u00e9es stock\u00e9es dans le n\u0153ud ; key est la cl\u00e9 du n\u0153ud.<\/p>\n
    Une fois le n\u0153ud compris, parlons des probl\u00e8mes pertinents concernant les arbres. Ici et ci-apr\u00e8s, par le terme \u00ab arbre \u00bb, je d\u00e9signerai un arbre binaire de recherche. La structure de l'arbre binaire :<\/p>\n
    public class BinaryTree<T> {\n     private Node<T> root;\n\n    \/\/m\u00e9thodes de l'arbre\n}\n<\/code><\/pre>\n
    Comme champ de la classe, nous n'aurons besoin que de la racine de l'arbre, car depuis la racine, en utilisant les m\u00e9thodes getLeftChild() et getRightChild(), on peut atteindre n'importe quel n\u0153ud de l'arbre.<\/p>\n
    Algorithmes dans l'arbre<\/h2>\n
    <\/p>\n
    La recherche<\/h3>\n
    \nSupposons que vous ayez un arbre construit. Comment trouver un \u00e9l\u00e9ment avec la cl\u00e9 key ? Il faut se d\u00e9placer progressivement de la racine vers le bas de l'arbre et comparer la valeur key avec la cl\u00e9 de chaque n\u0153ud : si key est inf\u00e9rieur \u00e0 la cl\u00e9 du n\u0153ud courant, passez au descendant gauche du n\u0153ud ; si sup\u00e9rieur, allez au droit ; si les cl\u00e9s sont \u00e9gales, le n\u0153ud recherch\u00e9 est trouv\u00e9 ! Le code correspondant :<\/p>\n
    public Node<T> find(int key) {\n    Node<T> current = root;\n    while (current.getKey() != key) {\n        if (key < current.getKey())\n            current = current.getLeftChild();\n        else\n            current = current.getRightChild();\n        if (current == null)\n            return null;\n    }\n    return current;\n}\n<\/code><\/pre>\n
    \nSi current devient \u00e9gal \u00e0 null, cela signifie que la recherche a atteint la fin de l'arbre (au niveau conceptuel, vous \u00eates dans un endroit inexistant de l'arbre \u2014 un descendant d'une feuille).<\/p>\n
    Consid\u00e9rons l'efficacit\u00e9 de l'algorithme de recherche dans un arbre \u00e9quilibr\u00e9 (un arbre dans lequel les n\u0153uds sont r\u00e9partis de mani\u00e8re plus ou moins uniforme). Dans ce cas, l'efficacit\u00e9 de la recherche sera O(log(n)), avec un logarithme en base 2. Regardez : si l'arbre \u00e9quilibr\u00e9 a n \u00e9l\u00e9ments, cela signifie qu'il y aura log(n) niveaux dans l'arbre. Et dans la recherche, \u00e0 chaque \u00e9tape de la boucle, vous descendez d'un niveau.<\/p>\n
    Insertion<\/h3>\n
    \nSi vous avez compris l'essence de la recherche, il vous sera facile de comprendre l'insertion. Il suffit de descendre jusqu'\u00e0 la feuille de l'arbre (en suivant les r\u00e8gles de descente d\u00e9crites dans la recherche) et de devenir son descendant \u2014 \u00e0 gauche ou \u00e0 droite, selon la cl\u00e9. Mise en \u0153uvre :<\/p>\n
       public void insert(T insertData, int key) {\n        Node current = root;\n        Node parent;\n        Node newNode = new Node(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n<\/code><\/pre>\n
    \nDans ce cas, il faut, en plus du n\u0153ud actuel, conserver des informations sur le parent du n\u0153ud actuel. Lorsque current deviendra \u00e9gal \u00e0 null, la variable parent contiendra la feuille dont nous avons besoin. 
    \nL'efficacit\u00e9 de l'insertion sera, comme pour la recherche, de O(log(n)).<\/p>\n
    D\u00e9sinstallation<\/h3>\n
    \nLa suppression est l'op\u00e9ration la plus complexe \u00e0 effectuer sur l'arbre. \u00c9videmment, il faut d'abord trouver l'\u00e9l\u00e9ment que nous allons supprimer. Mais ensuite ? Si l'on se contente d'assigner la valeur null \u00e0 sa r\u00e9f\u00e9rence, nous perdrons l'information sur le sous-arbre dont ce n\u0153ud est la racine. Les m\u00e9thodes de suppression d'un arbre sont divis\u00e9es en trois cas.<\/p>\n
    Premier cas. Le n\u0153ud \u00e0 supprimer n'a pas de descendants.<\/h4>\n
    \nSi le n\u0153ud \u00e0 supprimer n'a pas de descendants, cela signifie qu'il s'agit d'une feuille. On peut donc simplement assigner la valeur null aux champs leftChild ou rightChild de son parent. <\/p>\n
    Deuxi\u00e8me cas. Le n\u0153ud \u00e0 supprimer a un descendant.<\/h4>\n
    \nCe cas n'est pas tr\u00e8s compliqu\u00e9 non plus. Revenons \u00e0 notre exemple. Supposons que nous devions supprimer l'\u00e9l\u00e9ment avec la cl\u00e9 14. Convenez que puisqu'il est le descendant droit du n\u0153ud avec la cl\u00e9 10, tout descendant de ce n\u0153ud (dans ce cas, le droit) aura une cl\u00e9 sup\u00e9rieure \u00e0 10, il est donc facile de \"l'\u00e9monder\" de l'arbre et de relier directement le parent au descendant du n\u0153ud supprim\u00e9, c'est-\u00e0-dire de relier le n\u0153ud avec la cl\u00e9 10 au n\u0153ud 13. Il en serait de m\u00eame si nous devions supprimer un n\u0153ud qui est le descendant gauche de son parent. R\u00e9fl\u00e9chissez bien \u00e0 cela \u2014 c'est une analogie exacte. <\/p>\n
    Troisi\u00e8me cas. Le n\u0153ud a deux descendants.<\/h4>\n
    \nLe cas le plus complexe. Analysons par un nouvel exemple.<\/p>\n
    \"Arbre
    \n<\/p>\n
    Recherche du successeur.<\/h4>\n
    \n Supposons que nous devons supprimer un n\u0153ud avec la cl\u00e9 25. Qui allons-nous mettre \u00e0 sa place ? Quelqu'un de ses successeurs (descendants ou descendants des descendants) doit devenir le successeur<\/i>(celui qui prendra la place du n\u0153ud supprim\u00e9). <\/p>\n
    Comment d\u00e9terminer qui doit devenir le successeur ? Il est intuitivement clair que c\u2019est le n\u0153ud dans l\u2019arbre dont la cl\u00e9 est la suivante par ordre croissant apr\u00e8s celle du n\u0153ud supprim\u00e9. L\u2019algorithme est le suivant. Il faut se rendre \u00e0 son successeur droit (toujours \u00e0 droite, car il a d\u00e9j\u00e0 \u00e9t\u00e9 dit que la cl\u00e9 du successeur est sup\u00e9rieure \u00e0 celle du n\u0153ud supprim\u00e9), puis parcourir la cha\u00eene des successeurs gauches de ce successeur droit. Dans notre exemple, nous devons passer au n\u0153ud avec la cl\u00e9 35, puis descendre jusqu'\u00e0 la feuille en suivant la cha\u00eene de ses successeurs gauches \u2014 dans ce cas, cette cha\u00eene ne contient que le n\u0153ud avec la cl\u00e9 30. Strictement parlant, nous cherchons le n\u0153ud le plus petit dans l'ensemble des n\u0153uds sup\u00e9rieurs au n\u0153ud recherch\u00e9.<\/p>\n
    \"Arbre
    \n
    \nCode de la m\u00e9thode de recherche du successeur :<\/p>\n
        public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode; \/\/ parent du successeur\n        Node<T> successor = deleteNode; \/\/ successeur\n        Node<T> current = successor.getRightChild(); \/\/ simplement un n\u0153ud \"courant\"\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n        \/\/ \u00e0 la sortie de la boucle, nous avons le successeur et le parent du successeur\n        if (successor != deleteNode.getRightChild()) { \/\/ si le successeur ne co\u00efncide pas avec le successeur droit du n\u0153ud supprim\u00e9\n            parentSuccessor.setLeftChild(successor.getRightChild()); \/\/ alors son parent prend le descendant du successeur pour ne pas le perdre\n            successor.setRightChild(deleteNode.getRightChild()); \/\/ relions le successeur au successeur droit du n\u0153ud supprim\u00e9\n        }\n        return successor;\n    }\n<\/code><\/pre>\n
    \nCode complet de la m\u00e9thode delete :<\/p>\n
    public boolean delete(int deleteKey) {\n        Node current = root;\n        Node parent = current;\n        boolean isLeftChild = false; \/\/ En fonction de savoir si le n\u0153ud \u00e0 supprimer est un enfant gauche ou droit de son parent, la variable bool\u00e9enne isLeftChild prendra la valeur true ou false respectivement.\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) { \/\/ premier cas\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) { \/\/ deuxi\u00e8me cas\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else { \/\/ troisi\u00e8me cas\n            Node successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n<\/code><\/pre>\n
    \nLa complexit\u00e9 peut \u00eatre approxim\u00e9e \u00e0 O(log(n)).<\/p>\n
    Recherche du maximum\/minimum dans l'arbre<\/h3>\n
    \nIl est \u00e9vident que pour trouver la valeur minimale\/maximale dans l'arbre, il faut parcourir successivement la cha\u00eene des \u00e9l\u00e9ments gauche\/droit de l'arbre respectivement ; lorsque vous atteindrez une feuille, elle sera l'\u00e9l\u00e9ment minimal\/maximal.<\/p>\n
        public Node getMinimum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node getMaximum(Node startPoint) {\n        Node current = startPoint;\n        Node parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n<\/code><\/pre>\n
    \nComplexit\u00e9 \u2014 O(log(n))<\/p>\n
    Parcours sym\u00e9trique<\/h3>\n
    \nLe parcours consiste \u00e0 visiter chaque n\u0153ud de l'arbre dans le but d'effectuer une certaine action avec lui.<\/p>\n
    L'algorithme de parcours sym\u00e9trique r\u00e9cursif :<\/p>\n
      \n
    1. Effectuer une action avec l'enfant gauche<\/li>\n
    2. Effectuer une action avec soi-m\u00eame<\/li>\n
    3. Effectuer une action avec l'enfant droit<\/li>\n<\/ol>\n
      \nCode :<\/p>\n
          public void inOrder(Node current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\/\/Vous pouvez mettre tout ce que vous voulez ici\n            inOrder(current.getRightChild());\n        }\n    }\n<\/code><\/pre>\n
      <\/p>\n
      Conclusion<\/h2>\n
      \nEnfin ! Si j'ai manqu\u00e9 d'expliquer quelque chose ou si vous avez des remarques, n'h\u00e9sitez pas \u00e0 les laisser en commentaire. Comme promis, voici le code complet.<\/p>\n
      Node.java:<\/p>\n
      public class Node {\n    private T data;\n    private int key;\n    private Node leftChild;\n    private Node rightChild;\n\n    public Node(T data, int key) {\n        this.data = data;\n        this.key = key;\n    }\n\n    public void setLeftChild(Node newNode) {\n        leftChild = newNode;\n    }\n\n    public void setRightChild(Node newNode) {\n        rightChild = newNode;\n    }\n\n    public Node getLeftChild() {\n        return leftChild;\n    }\n\n    public Node getRightChild() {\n        return rightChild;\n    }\n\n    public T getData() {\n        return data;\n    }\n\n    public int getKey() {\n        return key;\n    }\n}\n\n<\/code><\/pre>\n
      \nBinaryTree.java:<\/p>\n
      public class BinaryTree<T> {\n    private Node<T> root;\n\n    public Node<T> find(int key) {\n        Node<T> current = root;\n        while (current.getKey() != key) {\n            if (key < current.getKey())\n                current = current.getLeftChild();\n            else\n                current = current.getRightChild();\n            if (current == null)\n                return null;\n        }\n        return current;\n    }\n\n    public void insert(T insertData, int key) {\n        Node<T> current = root;\n        Node<T> parent;\n        Node<T> newNode = new Node<>(insertData, key);\n        if (root == null)\n            root = newNode;\n        else {\n            while (true) {\n                parent = current;\n                if (key < current.getKey()) {\n                    current = current.getLeftChild();\n                    if (current == null) {\n                         parent.setLeftChild(newNode);\n                         return;\n                    }\n                }\n                else {\n                    current = current.getRightChild();\n                    if (current == null) {\n                        parent.setRightChild(newNode);\n                        return;\n                    }\n                }\n            }\n        }\n    }\n\n    public Node<T> getMinimum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getLeftChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getMaximum(Node<T> startPoint) {\n        Node<T> current = startPoint;\n        Node<T> parent = current;\n        while (current != null) {\n            parent = current;\n            current = current.getRightChild();\n        }\n        return parent;\n    }\n\n    public Node<T> getSuccessor(Node<T> deleteNode) {\n        Node<T> parentSuccessor = deleteNode;\n        Node<T> successor = deleteNode;\n        Node<T> current = successor.getRightChild();\n        while (current != null) {\n            parentSuccessor = successor;\n            successor = current;\n            current = current.getLeftChild();\n        }\n\n        if (successor != deleteNode.getRightChild()) {\n            parentSuccessor.setLeftChild(successor.getRightChild());\n            successor.setRightChild(deleteNode.getRightChild());\n        }\n        return successor;\n    }\n\n    public boolean delete(int deleteKey) {\n        Node<T> current = root;\n        Node<T> parent = current;\n        boolean isLeftChild = false;\n        while (current.getKey() != deleteKey) {\n            parent = current;\n            if (deleteKey < current.getKey()) {\n                current = current.getLeftChild();\n                isLeftChild = true;\n            } else {\n                isLeftChild = false;\n                current = current.getRightChild();\n            }\n            if (current == null)\n                return false;\n        }\n\n        if (current.getLeftChild() == null && current.getRightChild() == null) {\n            if (current == root)\n                current = null;\n            else if (isLeftChild)\n                parent.setLeftChild(null);\n            else\n                parent.setRightChild(null);\n        }\n        else if (current.getRightChild() == null) {\n            if (current == root)\n                root = current.getLeftChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getLeftChild());\n            else\n                current.setRightChild(current.getLeftChild());\n        } else if (current.getLeftChild() == null) {\n            if (current == root)\n                root = current.getRightChild();\n            else if (isLeftChild)\n                parent.setLeftChild(current.getRightChild());\n            else\n                parent.setRightChild(current.getRightChild());\n        } \n        else {\n            Node<T> successor = getSuccessor(current);\n            if (current == root)\n                root = successor;\n            else if (isLeftChild)\n                parent.setLeftChild(successor);\n            else\n                parent.setRightChild(successor);\n        }\n        return true;\n    }\n\n    public void inOrder(Node<T> current) {\n        if (current != null) {\n            inOrder(current.getLeftChild());\n            System.out.println(current.getData() + \" \");\n            inOrder(current.getRightChild());\n        }\n    }\n}\n<\/code><\/pre>\n
      P.S.<\/h2>\n
      <\/p>\n
      D\u00e9g\u00e9n\u00e9ration en O(n)<\/h3>\n
      \nBeaucoup d'entre vous ont peut-\u00eatre remarqu\u00e9 : et si nous faisions en sorte que l'arbre devienne d\u00e9s\u00e9quilibr\u00e9 ? Par exemple, en ajoutant des n\u0153uds avec des cl\u00e9s croissantes : 1,2,3,4,5,6\u2026 \u00c0 ce moment-l\u00e0, l'arbre ressemblera \u00e0 quelque chose de semblable \u00e0 une liste cha\u00een\u00e9e. Et oui, l'arbre perdra sa structure arborescente, et par cons\u00e9quent, son efficacit\u00e9 d'acc\u00e8s aux donn\u00e9es. La complexit\u00e9 des op\u00e9rations de recherche, d'insertion et de suppression deviendra similaire \u00e0 celle d'une liste cha\u00een\u00e9e : O(n). C'est l\u00e0 qu'appara\u00eet, selon moi, l'un des principaux inconv\u00e9nients des arbres binaires.<\/p>\n
      Seuls les utilisateurs enregistr\u00e9s peuvent participer au sondage. Connectez-vous<\/a><\/noindex>, s'il vous pla\u00eet.<\/p>\n
      Je ne suis pas sur Habr depuis longtemps, et j'aimerais savoir quels sujets d'articles aimeriez-vous voir plus souvent ?<\/h2>\n
        \n
      • \n
                            Structures de donn\u00e9es<\/p>\n<\/li>\n
      • \n
                            Algorithmes (DP, r\u00e9cursion, compression de donn\u00e9es, etc.)<\/p>\n<\/li>\n
      • \n
                            Application des structures de donn\u00e9es et des algorithmes dans la vie r\u00e9elle<\/p>\n<\/li>\n
      • \n
                            Programmation d'applications Android en Java<\/p>\n<\/li>\n
      • \n
                            Programmation d'applications web en Java<\/p>\n<\/li>\n<\/ul>\n
            2 utilisateurs ont vot\u00e9. 1 utilisateur s'est abstenu.
        \n
        Source : habr.com<\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"
        \u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430. \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u0434\u0435\u043b\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u044e \u043f\u0440\u043e \u0441\u0436\u0430\u0442\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0425\u0430\u0444\u0444\u043c\u0430\u043d\u0430. \u0422\u0430\u043c \u044f \u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043e\u0431\u0440\u0430\u0449\u0430\u043b \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u0434\u0435\u0440\u0435\u0432\u044c\u044f, \u0438\u0431\u043e \u043c\u0435\u0442\u043e\u0434\u044b \u043f\u043e\u0438\u0441\u043a\u0430, \u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u043d\u0435 \u0431\u044b\u043b\u0438 \u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b. \u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u0448\u0438\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0442\u0430\u0442\u044c\u044e \u0438\u043c\u0435\u043d\u043d\u043e \u043f\u0440\u043e \u0434\u0435\u0440\u0435\u0432\u044c\u044f. \u041f\u043e\u0436\u0430\u043b\u0443\u0439, \u043d\u0430\u0447\u043d\u0435\u043c. \u0414\u0435\u0440\u0435\u0432\u043e \u2014 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u0441\u043e\u0441\u0442\u043e\u044f\u0449\u0430\u044f \u0438\u0437 \u0443\u0437\u043b\u043e\u0432, \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u043d\u044b\u0445 \u0440\u0435\u0431\u0440\u0430\u043c\u0438. \u041c\u043e\u0436\u043d\u043e \u0441\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u2014 […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":22528,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-30530","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Binary Tree ou comment pr\u00e9parer un arbre binaire de recherche | ProHoster","description":"Pr\u00e9lude Cet article est d\u00e9di\u00e9 aux arbres binaires de recherche.","canonical_url":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"fr_FR","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47Binary Tree \u0438\u043b\u0438 \u043a\u0430\u043a \u043f\u0440\u0438\u0433\u043e\u0442\u043e\u0432\u0438\u0442\u044c \u0431\u0438\u043d\u0430\u0440\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e\u0438\u0441\u043a\u0430 | ProHoster","og:description":"\u041f\u0440\u0435\u043b\u044e\u0434\u0438\u044f \u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u043e\u0441\u0432\u044f\u0449\u0435\u043d\u0430 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u043c \u0434\u0435\u0440\u0435\u0432\u044c\u044f\u043c \u043f\u043e\u0438\u0441\u043a\u0430.","og:url":"https:\/\/prohoster.info\/fr\/blog\/administrirovanie\/binary-tree-ili-kak-prigotovit-binarnoe-derevo-poiska","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T18:36:01+00:00","article:modified_time":"2019-10-31T18:36:01+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"30530","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 01:39:20","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 03:33:27","updated":"2026-01-21 01:39:20","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts\/30530","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/comments?post=30530"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts\/30530\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media\/22528"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media?parent=30530"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/categories?post=30530"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/tags?post=30530"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}