Binary tree of research

In Data-processing, a binary tree of research (ABR) is a binary tree in which each node has a key , such as each node of the left under-tree has a key lower or equal to that of the node considered, and that each node of the under-tree right has a key higher or equal to this one - according to the implementation of the ABR, one will be able to prohibit or not keys of equal value. The nodes which one additions become sheets of the tree.

Operations

Seek

Research in a binary tree of a node having a particular key is a recursive process. One starts by examining the root. If its key is the sought key, the algorithm finishes and returns the root. If it is strictly lower, then it is in the left under-tree, on which one then carries out recursively research. The same if the key of the root is strictly higher than the required key research continues on the right under-tree. If one reaches a sheet whose key is not that required, one knows whereas the required key does not belong to any node. One can compare it with the dichotomizing search which proceeds about in the same way except that it reaches directly each element of a table instead of following bonds.

This operation requires a time in O (ln N) in the average case, but O (N) in the case criticizes where the tree is completely unbalanced and resembles a chained list.

Insertion

The insertion of a node starts with a research: one seeks the key of the node to insert; when one arrives at a sheet, one adds the node like wire of the sheet by comparing his key with that of the sheet: if it is lower, the new node will be on the left; if not it will be on the right.

Complexity is obviously the same one as for research: O (ln N) in the average case and O (N) in the critical case.

Suppression

Several cases are to be considered, once the node to be removed was found starting from its key:

Removal of a sheet : It is enough to remove it tree considering which it does not have of wire.
Suppression of a node with a child : It should be removed tree by replacing it by his son.
Suppression of a node with two children : Let us suppose that the node to be removed is called NR (the node of value 7 in the graph below). One then replaces it by his successor nearest (the node on the left of the right under-tree - below, the node of value 9) or his nearer predecessor (the node on the right of the left under-tree - below, the node of value 6). That makes it possible to keep a structure of tree binary of research. Then one again applies the procedure of suppression to NR , which is now a sheet or a node with only one son.

For an effective implementation, it is disadvised using only the successor or the predecessor because that contributes to unbalance the tree.

In all the cases this operation requires to traverse the tree of the root to a sheet: the execution time is thus proportional to the depth of the tree which is worth N in worst case, from where a maximum complexity in O (N) .

Ordered course

One can easily recover the elements of a binary tree of research in the order of their keys by traversing the left under-tree recursively, then by adding the root, then by traversing the right under-tree recursively. One can obviously do it in the inverse order while starting with the right under-tree.

The course of the tree is made in O (N) , since it must pass by each node.

Sorting

One can consequently implement a Algorithme of sorting simple but not very effective, while inserting all the keys which one wants to sort in a new binary tree of research, then by traversing in an ordered way this tree like above.

The worst execution time is in O (N ²) , obtained when the keys are already ordered: one obtains a chained Liste then. For example, if one gives in this order keys 1,2,3,4,5, one obtains the tree (Vacuum, 1, (Vacuum, 2, (Vacuum, 3, (Vacuum, 4, (Vacuum, 5))))). There is to avoid this problem, in many ways most common being the Arbre balanced. One can then arrive at a worse case in O (N ln N) .

Binary types of trees of research

There exist many types of binary trees of research. The trees AVL and the trees red-black are two types of balanced trees. A Arbre splay is a binary tree of research which automatically brings closer to the root the elements used frequently. In one, each node has also a priority higher than each one of its sons.

External bonds

an introduction to the binary trees of research

Random links: