Binary tree

As a binary tree is known in graph theory, a special form of a graph, and indeed it is a rooted tree in which each node has at most two child nodes. Most will require that the child nodes can be divided into left and right child unique. An illustrative example of such a binary tree is the pedigree, in which, however, the parents are attributable to the child node.

A binary tree is either empty, or it consists of a root with a left and right subtree, which in turn are binary trees. If a subtree is empty, is referred to the corresponding child node as missing.

Most often, the root is in graphical representations (such as in the adjacent ) above and the leaves placed at the bottom. Accordingly, a path from the root towards a leaf from the top to the bottom.

• 3.1 Binary search tree
• 3.2 Partially ordered tree
• 3.3 Fully balanced binary tree
• 3.4 Further binary trees

• 4.1 in-order index
• 4.2 Left / Right Index
• 4.3 Representation by an array

• 5.1 Recursive implementations
• 5.2 Iterative implementation
• 5.3 descent to the first or last element

• 7.1 Pseudocode

• 8.1 complexity
• 8.2 metric rotation

Terminology

The terms node, edge, which by definition is a directed edge (or bow and arrow), taken from the general graph. If it shows clear enough from the context, is also spoken only of edge.

In a directed graph can be assigned to a node out-degree both as in-degree. Usually, binary trees to be construed as an out - tree. In such a rooted tree there is exactly one node that has in-degree 0. It is referred to as the root. All other nodes have in-degree 1, the out-degree is the number of child nodes is limited and the binary tree to a maximum of 2. So that his order is an out -tree ≤ 2

Node with out-degree ≥ 1 is called internal nodes, those with out-degree 0 as leaves or external nodes. For binary trees - and only there - is sometimes found the name Half Sheet for a node with out-degree 1 (English sometimes: non- branching node). Then, a sheet is a double half- sheet.

Other terms

A binary tree is called ordered if each internal node, a left and a right child has any additional (and not only a right child), as well as the left node "small", the right node is " bigger" than the observation nodes. It is called the full, if each node is either sheet (ie not a child has ), or two ( ie both a left such a right ) has children - so there's no half leaf. For the full property and the terms are occasionally saturated or strictly used. Is called full binary tree to be complete when all the sheets have the same depth, wherein the depth of a node is defined as the number of sheets to the root.

The height of a rooted tree is the maximum depth occurring. Many authors put them higher by 1, since one so the empty tree height 0 and consisting of only the root tree can give the level 1, which allows to take certain recursive definitions shorter. ( And since depth is an attribute of a node, but the amount of the whole tree, it does not necessarily indicate confusion. ) In this article, the latter definition is persevered.

Inductively it can be shown that a complete binary tree of height h ( h ≥ 1), the one often referred to as a bra, exactly

• 2h-1 nodes,
• 2h -1-1 internal nodes (non- leaf, but possibly root),
• 2t nodes at depth t (0 ≤ t ≤ h-1), thus in particular
• 2h-1 leaves

Possesses. A representation of a binary tree in which the nodes are represented by right-angled triangles and the arcs with rectangles, called Pythagorean binary tree.

The binary tree is degenerate if each node is either leaf (number of children is 0 ) or half sheet (number of children is 1). In this case, the tree is a list dar. Special forms are the ordered lists in which a tree consists only of left or right only of children.

Abzählungen

• Just as a tree with n vertices has n-1 edges, has a binary tree with n nodes n-1 edges.
• A binary tree with n nodes has n 1 ( immediate ) insertion points.
• Has a binary tree with b leaves and h half- leaves. Every half- sheet and an insertion point at each leaf two, so 2b h ( immediate ) insertion points
• I is the number of the inner node ( including root, without half-blades ), is calculated as I = b -1.

Applications

Binary search tree

The in practice probably the most important application of binary trees are binary search trees, by which the AVL trees, red -black trees and splay trees are to be expected. When search trees there are " key " to the node, after which they are "linear" in the Search Tree. This order is then based the maximum efficiency of searches.

Partially ordered tree

A partially ordered tree T is a special tree,

• Whose nodes are labeled
• Come whose markings of an ordered range of values
• Where ' x is true with the root: All nodes of T' for each subtree T are marked greater than or equal to x.

Intuitively, this means that the root of each subtree represents a minimum for this subtree The values ​​of the subtree take in the direction of the leaves or to remain the same.

Such trees are frequently used in heaps.

Fully balanced binary tree

A complete balanced binary tree is a full binary tree, wherein the distances between any two sheets differ from the root by more than one from one another. A complete binary tree is a fully balanced binary tree. ( See also Balanced tree or AVL tree).

Other binary trees

Also Fibonacci trees and binary heaps are based on binary trees.

Representation and access

The figure shows an obvious way of storing. It approximately corresponds to the C- structure:

Struct node {/ / 1 object = 1 Node    char key;    struct node * left_child;    struct node * right_child; Object }; struct node * anchor; / / Pointer to the root To better distinguish the objects they are beziehentlich with the keys "F ", " G", " J" and " P" provided. These keys are also made for simplicity as the target of the reference ( instead of real memory addresses). As usual, to a pointer value 0 express that it refers to any object, so there is no child at this point.

The great advantage of the tree opposite the array lies in the flexible memory management: With the emergence or offenses of an object also can it arise or pass away performing memory, while the entries are firmly connected to the array with that.

In -order index

If in each node the number of elements of the corresponding subtree held, the prospect of an element by virtue of his will in-order index accomplished in much the same way as the prospect with a key in the binary search tree. However, this has the unfortunate implication that insert and delete operation always require corrections up to the root, which then also change the in-order indices of nodes. The approach should therefore be of questionable value for non static binary trees, and in the ordinary static array index with respect is superior to maturity.

The overhead is O ( h) where h is the height of the tree.

Left / right index

Each node can be specified precisely by binary digits by a variable length chain. The requirement could be as follows:

Each node in a binary tree can be unambiguously assigned to a binary string.

With height- balanced trees, the binary string is limited in length by O (log ( n ) ), so that it may fit into an unsigned integer. A possible encoding of the variable length in a fixed length word can be the binary string after the first "1" to begin.

The maximum cost for the access is O ( h).

Representation by an array

A binary tree can be represented by an array having a length corresponding substantially to the number of nodes of the tree, or more precisely 2H -1 h than the height of the tree. Indexing starts with 1, with reference to the root. Then she sits " line by line" on: all nodes of the same depth are numbered consecutively from left to right. This means that the readout of the array from the left corresponds to a level-order traversal (or breadth-first traversal ) of the tree. If the binary tree is not full, exuberant nodes must be occupied by a placeholder, so that so wasted 2h-1 -n memory cells.

This numbering has the nice property that it is easy to calculate the indices of the connected nodes. In array A Ai is a node, then A2i is his left and his right A2i 1 child; the rounded half refers to the parent Aj.

In the genealogy of the indexing scheme is also known under the term Kekule numbering.

Since no explicit pointers are required in the imaging of a binary tree in an array to children or parent node, the data structure is also referred to as an implicit data structure.

One application of this representation, the binary heap is used for sorting of items.

Traversal

Denotes the systematic traversal of the tree examining the node in a certain order. A special case is the linearization, wherein the elements in the order of traversal are inserted into a list.

There are several ways to traverse the nodes of binary trees. We distinguish:

• Pre-order (also depth-first ) or main sequence (also depth-first search ) (W -L- R): First, the root (W) is considered, then the left (L), including the right (R) subtree through.
• Post-order or ancillary order ( L -R -W): First, the left (L ), then the right (R ) subtree is traversed, and finally the root (W ) is considered.

• In-order or symmetric sequence (L -W R): First, the left (L ) subtree is traversed, then the root considered (W ), and finally the right (R) subtree through.
• Reverse in-order or anti- symmetric sequence (R -W -L): First, the right (R) subtree is traversed, then the root (W ) are considered and finally the left (L) subtree through.
• Level -order (including breadth-first, breadth-first search German ): Starting with the tree root, the levels are traversed from left to right.

Recursive implementations

Preorder ( node ) {      print ( knots )      if knoten.links ≠ null then          preorder ( knoten.links )      if knoten.rechts ≠ null then          preorder ( knoten.rechts ) } postorder ( node ) {      if knoten.links ≠ null then          postorder ( knoten.links )      if knoten.rechts ≠ null then          postorder ( knoten.rechts )      print ( knots ) } inOrder ( node ) {      if knoten.links ≠ null then          inOrder ( knoten.links )      print ( knots )      if knoten.rechts ≠ null then          inOrder ( knoten.rechts ) } A traversal over the hierarchy consists of each node exactly one call a recursive traversal functions. The effort at n nodes is so.

Iterative implementation

An iterative implementation makes it possible to complete only a single traversal step and set up a program loop with a beginning and end and the actions on the nodes visited in the usual manner.

An example is shown only the in-order traversal, the case of binary search trees in particular plays a major role, since this sequence corresponds to the sort order.

InOrderNext ( knots, direction ) {      / / Direction = 0 ( turnleft = "reverse in-order " )      / / Or = 1 ( turnright = " in-order " )      knotenY = knoten.kind [ direction ] / / one step in the given direction      if knotenY ≠ null then {          direction = 1 - direction / / reflects Left <- > Right          / / Down to the leaves on children in the mirrored direction          knotenZ = knotenY.kind [ direction ]          while knotenZ ≠ null {              knotenY = knotenZ              knotenZ = knotenY.kind [ direction ]          }          return knotenY      }      / / Rise to the root about ancestors in the given direction      knotenY = node      do {          knotenZ = knotenY          knotenY = knotenZ.elter          if knotenY = null return null / / ( knotenZ is the root :)                               / / That is, there is no element in this direction      Until knotenZ } ≠ knotenY.kind [ direction ]      / / KnotenY is the first ancestor in the mirrored direction == > Result      return knotenY } A traversal over the tree contains a descent ( in the direction of the arc ), and a rise ( in the opposite direction ) per sheet. A tree of n nodes having n-1 sheets, so that a step is about Gesamttraversierung. The cost for a single traversal is so average, in O (1) and in the worst case in O ( h) with h as the height of the tree.

Descent to the first or last element

Much like a single traversal does the search after the first or last element.

First last ( binary tree, direction ) {      / / Direction = Left (first ) or right (last )      knotenY = binärBaum.wurzel      if knotenY = null then return binary tree / / the empty tree      / / Down to the leaves      do {          knotenZ = knotenY          knotenY = knotenZ.kind [ direction ]      = Null } until knotenY      return knotenZ } The overhead is O ( h) where h is the height of the tree.

Insertion, insertion

It is assumed that the navigation is carried out already at a insertion. Insertion point is a node and a direction (right or left). A direct insertion into a binary tree is always a right (or left ) half- sheet, an indirect is the immediate neighbor in the specified direction and specified together with the opposite direction the same location in the binary tree - a real paste but the paste function must still up to the half leaf descend, which represents the immediate insertion.

To insert is allowed to refer the child to the required direction of the node to the new element, so this is inserted correctly. The complexity of the insert operation is thus constant.

After inserting the new element is a leaf of the binary tree.

In the following example, a node is inserted with the key "J" in a binary tree at the insertion point ("M", left).

S S            / \ / \           / \ / \          G W G W         / \ / \        / \ == > / \       D M D M      / \ \ / \ / \     B B F F P P Y Repeated insertion at always the same point, it may happen that the tree degenerates into a linear list.

When deleting one must distinguish clearly more cases. It is important, for example, how many children the node has.

Case A: To Node has more than one child.

If the node is a leaf removed (nodes without children ), then simply deleting the node. If the node to be deleted just a child, this is put in the place of the deleted node.

Case B: For Node has two children.

In this case, the deletion can be performed both on the left and on the right subtree. In order to maintain the in-order - order, but a descent to a half leaf is inevitable.

One possibility is to set the left subtree to the position at which the node to be deleted was, and attach the right subtree to the left at the right tester point, as shown in the example ( "G" should be deleted):

S S            / \ / \           / \ / \          G W D W         / \ / \        / \ == > / \       D M F B      / \ / \ \     B F J P M                                          / \                                         J P However, the changes in the heights are smaller, if the node to be deleted by a ( direct ) neighbors (in the in-order - order) replaced. In the example " F" on the left neighbor of "G ", that is in the left subtree at the far right; " J " is the right neighbor of "G ", that is leftmost in the right subtree. The in -order sequence is "F " - " G" - "J". The right neighbor may have a right subtree must be attached to the place where the neighbor was.

In the following example, the node to be deleted "G" is replaced by its right neighbor "J":

S S             / \ / \            / \ / \           G W J W          / \ / \         / \ / \        D M == > D M       / \ / \ / \ / \      B F J P B F K P             \              K To give the tree as little opportunity to be one-sided, one can systematically alternated between left and right descent. Standing balance settings are available, it is natural to prefer the descent on the possibly higher side.

Repeatedly deleting it may happen that the tree degenerates into a linear list.

Because of the unavoidable Downs to the half- sheets, the complexity of the erase operation in the worst case O ( h), where h is the height of the tree. Since the descent of a single traversal corresponds ascents and descents in a Gesamttraversierung are equally as climbs, the average of abzusteigenden levels for growing number of nodes converges to 1

Pseudocode

The illustrations and the pseudo-code to show the removal of an element that has two children and a close grandson of a binary tree.

The new tree

Remove ( binary tree, node ) {      / / Assume that knoten.links ≠ zero knoten.rechts ≠ zero      / / And knoten.rechts.links ≠ null      knotenY = knoten.rechts      while knotenY ≠ null {          knotenZ = knotenY          knotenY = knotenZ.links      }      / / KnotenZ is the right neighbor of node      if knotenZ.rechts ≠ null then knotenZ.rechts.elter = knotenZ.elter      knotenZ.elter.links = knotenZ.rechts      knotenZ.rechts = knoten.rechts      knoten.rechts.elter = knotenZ      knotenZ.links = knoten.links      knoten.links.elter = knotenZ / / knoten.links ≠ null      if knoten.elter.links = node          then knoten.elter.links = knotenZ          else knoten.elter.rechts = knotenZ      knotenZ.elter = knoten.elter } Rotation in binary trees

Using rotations can convert a binary tree to another and thus influence properties, in particular heights of subtrees ( for example, in red-black trees and AVL trees ) or search depths of nodes ( eg, in splay trees ). Do not change the in-order sequence, so according to their application of the tree in terms of the symmetrical sequence equivalent.

Occasionally, double and triple rotations are required.

R Right - Rotate ( R) L              / \ -------- > / \             / R < -------- l \            L Left - Rotate ( L) R           / \ / \          l m m r Declaration on Right - Rotate ( R) "R" to the right sub-tree of "L". The original right subtree "m" of "L" for the left sub-tree of "R".

"L" for the left sub-tree of "R". The original left subtree "m" of "R" is for right subtree of "L".

In both cases, changes of the new tree, the suspension from above, whilst the suspension of the sub-trees, " L" and "R" remains the same.

Complexity

At a rotation up to 3 links are correct; So a rotation takes constant runtime O (1).

Rotation metric

The rotation distance between two binary trees with derselbem number of nodes is the minimum number of rotations needed to transform the first tree into the second. This metric is the amount BTn of binary trees with n nodes into a metric space, as the metric satisfies definiteness, symmetry and triangle inequality. The space BTn is a connected metric space with a diameter ≤ 2n - 6 Ie: At 2 different binary trees A and B ∈ BTn there is a natural number m ≤ 2n - 6 and T1, ..., Tm -1 ∈ BTn, so that T0: = a and T m: = B in each of Ti of Ti - 1, it is through rotation.

It is unclear whether there is a polynomial-time algorithm for computing the rotation distance.