Tree – Binary and Search

Trees are particular graphs often used to represent decision support, data, or complexity calculations.

A tree is an organized set of nodes in which each node has one father and only one, except for one so-called root node. If a node p is the father of the node f, then f is a child of p; if f has no son, then it is a leaf. It is possible to store any type of information in nodes or links.

Terminology

A node is defined by its label and subtrees. It is therefore possible to represent a tree by a tuple <e,a1,…,ak> in which e is the tag of the node and ai are its subtrees.

For example, calculators organize mathematical expressions according to the operators’ priority and their depth: (y/2-x)*(75+z) will be represented by <*,<-,,>,>,<+,,>>. The operation is then done by a particular route of the tree:

  • the descendants of a node are the nodes of its subtrees;
  • an ancestor of a node is either his father or an ancestor of his father;
  • the path of a node at the root is made up of all its ancestors;
  • the brother of a node is a son of his father other than himself.

A tree is often represented by a graph to facilitate reading:

arbre

The nodes of a tree are divided by depths (or levels). Depth 0 contains only the root, the depth 1 its threads etc. The height of a tree is the number of depths, or the size of the largest path of a node at the root.

Definition

Given an undirected graph with n vertices, the following properties are equivalent:

  1. The graph is connected without cycle
  2. The graphe is acyclic and has n-1 edges,
  3. The graph is connected and has n-1 edges,
  4. The graph is acyclic and if one adds an edge then it exists an unique elementary cycle,
  5. The graph is connected and if one deletes an edge then it becomes non-connected,
  6. It exists an unique path between any pair of vertices

Binary tree

In a binary tree, each node has a left son and a right son, which can be null subtrees. A binary tree is said complete if all its leaves have the same depth and all its vertices that are not leaves have two sons.

Let’s determine the total number of leaves and nodes of a complete binary tree.

At depth 0, there is only the root. Supose the complete binary tree has 2(h-1) leaves at depth h. Then at depth h+1, each of these leaves becomes a father with two leaves, 2*2(h-1) = 2h. QED.

The number of nodes of the complete binary graph is equal to the sum of the number of leaves of the complete binary trees of lower height. We deduce that the total number of nodes is ∑(i=0)(h-1) 2i = 2h -1. Conversely, if a complete binary graph has n nodes, then its depth is from the previous formula log2 (n)+1.

A balanced binary tree or AVL tree is a binary tree such that the depth of the two subtrees of any tree node differ by no more than 1. A subtree of an AVL tree is also an AVL tree.

arbre2

When the tree is unbalanced, it is necessary to swap the parent vertices and the root while keeping the order of the sub-trees (see more on the search trees).

arbre3

We can enlarge the definition on trees of higher degree (ternary tree etc). Only the coefficient 2 is modified according to the number of sons defined by the type of tree.

Search tree

A search tree is a data structure that can be used to represent a set of values if there is an order relationship on them. Standard operations on search trees are: inserting, deleting or searching for a value. These operations are inexpensive if the tree is balanced. To facilitate understanding, we will work on binary search trees (BST).

Let E be a set of values with an order relation, and let A be a binary tree. The tree A is an BST of E if for every node p of A, the value of p is strictly greater than the values of its left subtree, and is strictly smaller than the values in its right subtree ; provided that the values are unique. The values are called keys.

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:

arbre4

The three actions are then done through BST route.

Publicités