{"id":2463,"date":"2016-02-16T12:48:57","date_gmt":"2016-02-16T11:48:57","guid":{"rendered":"http:\/\/smart--grid.net\/?page_id=2463"},"modified":"2022-12-03T22:58:58","modified_gmt":"2022-12-03T21:58:58","slug":"arbres-et-arborescences","status":"publish","type":"page","link":"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/","title":{"rendered":"Trees and trees"},"content":{"rendered":"<div data-elementor-type=\"wp-page\" data-elementor-id=\"2463\" class=\"elementor elementor-2463\">\n\t\t\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-c458822 elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"c458822\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-46b88b9\" data-id=\"46b88b9\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-0d775a0 elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"0d775a0\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Graph theory<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-797580e\" data-id=\"797580e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-1982e5e elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"1982e5e\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/complex-systems-ai.com\/en\/\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Home page<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t<div class=\"elementor-column elementor-col-33 elementor-top-column elementor-element elementor-element-70b117e\" data-id=\"70b117e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-11450cb elementor-align-justify elementor-widget elementor-widget-button\" data-id=\"11450cb\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"button.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<div class=\"elementor-button-wrapper\">\n\t\t\t\t\t<a class=\"elementor-button elementor-button-link elementor-size-sm\" href=\"https:\/\/fr.wikipedia.org\/wiki\/Arbre_(th%C3%A9orie_des_graphes)\" target=\"_blank\" rel=\"noopener\">\n\t\t\t\t\t\t<span class=\"elementor-button-content-wrapper\">\n\t\t\t\t\t\t\t\t\t<span class=\"elementor-button-text\">Wiki<\/span>\n\t\t\t\t\t<\/span>\n\t\t\t\t\t<\/a>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<section class=\"elementor-section elementor-top-section elementor-element elementor-element-5f432e5b elementor-section-boxed elementor-section-height-default elementor-section-height-default\" data-id=\"5f432e5b\" data-element_type=\"section\" data-e-type=\"section\">\n\t\t\t\t\t\t<div class=\"elementor-container elementor-column-gap-default\">\n\t\t\t\t\t<div class=\"elementor-column elementor-col-100 elementor-top-column elementor-element elementor-element-6810c54e\" data-id=\"6810c54e\" data-element_type=\"column\" data-e-type=\"column\">\n\t\t\t<div class=\"elementor-widget-wrap elementor-element-populated\">\n\t\t\t\t\t\t<div class=\"elementor-element elementor-element-2630dbf9 elementor-widget elementor-widget-text-editor\" data-id=\"2630dbf9\" data-element_type=\"widget\" data-e-type=\"widget\" data-widget_type=\"text-editor.default\">\n\t\t\t\t<div class=\"elementor-widget-container\">\n\t\t\t\t\t\t\t\t\t<p><\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_82_2 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewbox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewbox=\"0 0 24 24\" version=\"1.2\" baseprofile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/#Arbres-et-arboresences\" >Trees and arboresences<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/#Terminologie\" >Terminology<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/#Definition-theorie-des-graphes\" >Definition: graph theory<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/#Arbre-binaire\" >Binary tree<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/trees-and-trees\/#Arbre-de-recherche\" >Research tree<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Arbres-et-arboresences\"><\/span>Trees and arboresences<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Trees and arborescences are particular graphs often used to represent the<a href=\"https:\/\/complex-systems-ai.com\/en\/help-with-the-decision\/\">help with the decision<\/a>, data, or for calculating the <a href=\"https:\/\/complex-systems-ai.com\/en\/algorithmic\/complexity-in-time\/\">complexity<\/a>.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">A tree is an organized set of nodes in which each node has <em>one father and one<\/em>, except a node which we call <em>root<\/em>. If a node <strong>p<\/strong> is the <em>father<\/em> of the knot <strong>f<\/strong>, so <strong>f<\/strong> is a <em>son<\/em> of <strong>p<\/strong>; if <strong>f<\/strong> has no son, so she is a <em>sheet<\/em>. It is possible to store any type of information in nodes or links.<\/div>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Terminologie\"><\/span>Terminology<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">A node is defined by its <em>label<\/em> and his <em>sub-trees<\/em>. It is therefore possible to represent a tree by a tuple &lt;e,a<sub>1<\/sub>,\u2026,To<sub>k<\/sub>&gt; in which <strong>e<\/strong> is the node label and <strong>To<sub>i<\/sub><\/strong> are its subtrees.<\/div>\n<p><\/p>\n<p><\/p>\n<p>For example, calculators organize the expressions <a href=\"https:\/\/complex-systems-ai.com\/en\/logic-math-27\/\">math<\/a> depending on the priority of the operators and their depth: (y\/2 \u2013 x)*(75+z) will be represented by &lt;*,&lt;-,,&gt;,&gt;,&lt;+,,&gt;&gt;. The operation is then done by a particular traversal of the tree:<\/p>\n<p><\/p>\n<p><\/p>\n<ul class=\"wp-block-list\">\n<li>the descendants of a node are the nodes of its subtrees;<\/li>\n<li>an ancestor of a node is either its father or an ancestor of its father;<\/li>\n<li>the path from a node to the root is made up of all its ancestors;<\/li>\n<li>the brother of a node is a son of his father other than himself.<\/li>\n<\/ul>\n<p><\/p>\n<p><\/p>\n<p>A tree is often represented by a <a href=\"https:\/\/complex-systems-ai.com\/en\/graph-theory-2\/\">graph<\/a> to make it easier to read:<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2483\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre.png\" alt=\"tree\" width=\"175\" height=\"210\" title=\"\"><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The nodes of a tree are distributed by <em>depths<\/em> (or levels). The depth 0 contains only the root, the depth 1 its children etc. The <em>height<\/em> of a tree is the number of depths, or the size of the longest path from a node to the root.<\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Definition-theorie-des-graphes\"><\/span>Definition: graph theory<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>Given an undirected graph comprising <strong>not<\/strong> vertices, the following properties are equivalent:<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #ffdcd3; border: 2px solid #ff7964; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">\n<ol style=\"text-align: justify;\">\n<li>The graph is connected and without cycle,<\/li>\n<li>The graph is cycleless and has n-1 edges,<\/li>\n<li>The graph is connected and admits n-1 edges,<\/li>\n<li>The graph is cycleless, and by adding an edge, then we create one and only one elementary cycle,<\/li>\n<li>The graph is connected, and by removing any edge it is no longer connected,<\/li>\n<li>There is one chain and only one between all pairs of vertices.<\/li>\n<\/ol>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>A tree is a directed graph without circuit admitting a root such that for any other vertex there is a unique path from the root to this vertex. A tree has properties similar to a tree.<\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-binaire\"><\/span>Binary tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">In a binary tree, each node has a left child and a right child, which can be zero subtrees. A binary tree is complete if all of its leaves have the same depth and all of its nodes that are not leaves have two children.<\/div>\n<p><\/p>\n<p><\/p>\n<p>Let us determine the total number of leaves and nodes of a complete binary tree.<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">\n<p>At depth 0 there is a leaf, the root. Suppose the complete binary tree has 2<sup>(h-1)<\/sup> leaves up to the task <strong>h<\/strong>. So, at the height h + 1, each of these leaves becomes a node with two threads, so we have a number of leaves of 2 * 2<sup>(h-1)<\/sup> = 2<sup>h<\/sup>. CQFD.<\/p>\n<p style=\"text-align: justify;\">In addition, the number of nodes of the complete binary graph is equal to the sum of the leaf number of the complete binary trees of lower height. We deduce that the total number of node is \u2211<sub>(i = 0)<\/sub><sup>(h-1)<\/sup> 2<sup>i<\/sup> = 2<sup>h<\/sup> -1. Conversely, if a complete binary graph has n nodes, then its height is according to the preceding formula log<sub>2<\/sub> (n) +1. We deduce that any binary tree has at least log height<sub>2<\/sub> (n) +1.<\/p>\n<\/div>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 3px; border: 2px dotted #a5a5a5; background-color: #f6f9fa;\">A balanced binary tree or AVL tree is a binary tree such that the heights of the two subtrees of any node in the tree differ by at most 1. A subtree of an AVL tree is also an AVL tree.<\/div>\n<p><\/p>\n<p><\/p>\n<p>The indicator on the vertices shows the difference between the height of the left subtree and the height of the right subtree.<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img fetchpriority=\"high\" decoding=\"async\" class=\"alignnone wp-image-2522\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre2.png\" alt=\"binary tree\" width=\"361\" height=\"324\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre2.png 361w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre2-300x269.png 300w\" sizes=\"(max-width: 361px) 100vw, 361px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>When the tree is unbalanced, it is then necessary to swap the parent vertices and the root while maintaining the order of the sub-trees (see the continuation on research trees).<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img decoding=\"async\" class=\"alignnone wp-image-2531\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre31.png\" alt=\"binary tree\" width=\"549\" height=\"602\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre31.png 549w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre31-274x300.png 274w\" sizes=\"(max-width: 549px) 100vw, 549px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>We can enlarge the definition on trees of higher degree (ternary tree etc). Only the coefficient 2 is modified according to the number of wires defined by the type of shaft.<\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<p><\/p>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Arbre-de-recherche\"><\/span>Research tree<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p><\/p>\n<p><\/p>\n<p>A search tree is a data structure making it possible to represent a set of values if we have an order relation on them. The standard operations on search trees are: inserting, deleting or finding a value. These operations are inexpensive if the shaft is balanced. In order to facilitate understanding, we will work on binary search trees (ABR).<\/p>\n<p><\/p>\n<p><\/p>\n<div style=\"padding: 5px; background-color: #d5edff; border: 2px solid #3c95e8; -moz-border-radius: 9px; -khtml-border-radius: 9px; -webkit-border-radius: 9px; border-radius: 9px;\">Let be a set of values <strong>E<\/strong> provided with an order relation, and either <strong>TO<\/strong> a binary tree. The tree <strong>TO<\/strong> is an ABR of <strong>E<\/strong> if for any node <strong>p<\/strong> of <strong>TO<\/strong>, the value of <strong>p<\/strong> is strictly greater than the values of its left subtree, and is strictly smaller than the values in its right subtree; provided the values are unique. The values are called <em>keys<\/em>.<\/div>\n<p><\/p>\n<p><\/p>\n<p>The smallest value is the last left descendant of the root, and the largest is the last right descendant of the root. Other logical criteria can be deduced from the definition:<\/p>\n<p><\/p>\n<p><\/p>\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2568\" src=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre4.png\" alt=\"search tree\" width=\"596\" height=\"374\" title=\"\" srcset=\"https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre4.png 596w, https:\/\/complex-systems-ai.com\/wp-content\/uploads\/2016\/02\/arbre4-300x188.png 300w\" sizes=\"(max-width: 596px) 100vw, 596px\" \/><\/figure>\n<\/div>\n<p><\/p>\n<p><\/p>\n<p>The three actions are then carried out through ABR routes.<\/p>\n<p><\/p>\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t<\/div>","protected":false},"excerpt":{"rendered":"<p>Graph theory Wiki home page Trees and tree structures Trees and tree structures are special graphs often used to represent decision support, \u2026 <\/p>","protected":false},"author":1,"featured_media":0,"parent":2204,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-2463","page","type-page","status-publish","hentry"],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2463","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/comments?post=2463"}],"version-history":[{"count":8,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2463\/revisions"}],"predecessor-version":[{"id":18402,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2463\/revisions\/18402"}],"up":[{"embeddable":true,"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/pages\/2204"}],"wp:attachment":[{"href":"https:\/\/complex-systems-ai.com\/en\/wp-json\/wp\/v2\/media?parent=2463"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}