Binary tree

From Wikipedia for FEVERv2
Jump to navigation Jump to search

Not to be confused with B-tree. Binary tree_sentence_0

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. Binary tree_sentence_1

A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root. Binary tree_sentence_2

Some authors allow the binary tree to be the empty set as well. Binary tree_sentence_3

From a graph theory perspective, binary (and K-ary) trees as defined here are actually arborescences. Binary tree_sentence_4

A binary tree may thus be also called a bifurcating arborescence—a term which appears in some very old programming books, before the modern computer science terminology prevailed. Binary tree_sentence_5

It is also possible to interpret a binary tree as an undirected, rather than a directed graph, in which case a binary tree is an ordered, rooted tree. Binary tree_sentence_6

Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted. Binary tree_sentence_7

A binary tree is a special case of an ordered K-ary tree, where k is 2. Binary tree_sentence_8

In mathematics, what is termed binary tree can vary significantly from author to author. Binary tree_sentence_9

Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily order (as left/right) the children either. Binary tree_sentence_10

In computing, binary trees are used in two very different ways: Binary tree_sentence_11

Binary tree_unordered_list_0

  • First, as a means of accessing nodes based on some value or label associated with each node. Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting. The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular, it is significant in binary search trees. However, the arrangement of particular nodes into the tree is not part of the conceptual information. For example, in a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by balancing) without changing the meaning.Binary tree_item_0_0

Binary tree_unordered_list_1

  • Second, as a representation of data with a relevant bifurcating structure. In such cases, the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with Huffman coding and cladograms. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.Binary tree_item_1_1

Definitions Binary tree_section_0

Recursive definition Binary tree_section_1

To actually define a binary tree in general, we must allow for the possibility that only one of the children may be empty. Binary tree_sentence_12

An artifact, which in some textbooks is called an extended binary tree is needed for that purpose. Binary tree_sentence_13

An extended binary tree is thus recursively defined as: Binary tree_sentence_14

Binary tree_unordered_list_2

  • the empty set is an extended binary treeBinary tree_item_2_2
  • if T1 and T2 are extended binary trees, then denote by T1 T2 the extended binary tree obtained by adding a root r connected to the left to T1 and to the right to T2 by adding edges when these sub-trees are non-empty.Binary tree_item_2_3

Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles. Binary tree_sentence_15

Using graph theory concepts Binary tree_section_2

A binary tree is a rooted tree that is also an ordered tree (a.k.a. plane tree) in which every node has at most two children. Binary tree_sentence_16

A rooted tree naturally imparts a notion of levels (distance from the root), thus for every node a notion of children may be defined as the nodes connected to it a level below. Binary tree_sentence_17

Ordering of these children (e.g., by drawing them on a plane) makes it possible to distinguish a left child from a right child. Binary tree_sentence_18

But this still doesn't distinguish between a node with left but not a right child from a one with right but no left child. Binary tree_sentence_19

The necessary distinction can be made by first partitioning the edges, i.e., defining the binary tree as triplet (V, E1, E2), where (V, E1 ∪ E2) is a rooted tree (equivalently arborescence) and E1 ∩ E2 is empty, and also requiring that for all j ∈ { 1, 2 } every node has at most one Ej child. Binary tree_sentence_20

A more informal way of making the distinction is to say, quoting the Encyclopedia of Mathematics, that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees. Binary tree_sentence_21

Types of binary trees Binary tree_section_3

Tree terminology is not well-standardized and so varies in the literature. Binary tree_sentence_22

Binary tree_unordered_list_3

  • A rooted binary tree has a root node and every node has at most two children.Binary tree_item_3_4

Binary tree_unordered_list_4

  • A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a recursive definition. A full binary tree is either:Binary tree_item_4_5
    • A single vertex.Binary tree_item_4_6
    • A tree whose root node has two subtrees, both of which are full binary trees.Binary tree_item_4_7
  • In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2 nodes at the last level h. An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree. A complete binary tree can be efficiently represented using an array.Binary tree_item_4_8

Binary tree_unordered_list_5

  • A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. An example of a perfect binary tree is the (non-incestuous) ancestry chart of a person to a given depth, as each person has exactly two biological parents (one mother and one father). Provided the ancestry chart always displays the mother and the father on the same side for a given node, their sex can be seen as an analogy of left and right children, children being understood here as an algorithmic term. A perfect tree is therefore always complete but a complete tree is not necessarily perfect.Binary tree_item_5_9
  • In the infinite complete binary tree, every node has two children (and so the set of levels is countably infinite). The set of all nodes is countably infinite, but the set of all infinite paths from the root is uncountable, having the cardinality of the continuum. That's because these paths correspond by an order-preserving bijection to the points of the Cantor set, or (using the example of a Stern–Brocot tree) to the set of positive irrational numbers.Binary tree_item_5_10
  • A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1. One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".)Binary tree_item_5_11
  • A degenerate (or pathological) tree is where each parent node has only one associated child node. This means that the tree will behave like a linked list data structure.Binary tree_item_5_12

Properties of binary trees Binary tree_section_4

Combinatorics Binary tree_section_5

Methods for storing binary trees Binary tree_section_6

Binary trees can be constructed from programming language primitives in several ways. Binary tree_sentence_23

Nodes and references Binary tree_section_7

In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Binary tree_sentence_24

Sometimes it also contains a reference to its unique parent. Binary tree_sentence_25

If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special sentinel node. Binary tree_sentence_26

This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative is threaded binary tree. Binary tree_sentence_27

In languages with tagged unions such as ML, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. Binary tree_sentence_28

For example, the following line of code in OCaml (an ML dialect) defines a binary tree that stores a character in each node. Binary tree_sentence_29

Arrays Binary tree_section_8

This method of storage is often used for binary heaps. Binary tree_sentence_30

Encodings Binary tree_section_9

Succinct encodings Binary tree_section_10

One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf. Binary tree_sentence_31

If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. Binary tree_sentence_32

This function accomplishes this: Binary tree_sentence_33

More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form. Binary tree_sentence_34

Encoding general trees as binary trees Binary tree_section_11

There is a one-to-one mapping between general ordered trees and binary trees, which in particular is used by Lisp to represent general ordered trees as binary trees. Binary tree_sentence_35

To convert a general ordered tree to a binary tree, we only need to represent the general tree in left-child right-sibling way. Binary tree_sentence_36

The result of this representation will automatically be a binary tree if viewed from a different perspective. Binary tree_sentence_37

Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to N 's next sibling --- that is, the next node in order among the children of the parent of N. This binary tree representation of a general order tree is sometimes also referred to as a left-child right-sibling binary tree (also known as LCRS tree, doubly chained tree, filial-heir chain). Binary tree_sentence_38

One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning or head of this list, through its left field. Binary tree_sentence_39

For example, in the tree on the left, A has the 6 children {B,C,D,E,F,G}. Binary tree_sentence_40

It can be converted into the binary tree on the right. Binary tree_sentence_41

The binary tree can be thought of as the original tree tilted sideways, with the black left edges representing first child and the blue right edges representing next sibling. Binary tree_sentence_42

The leaves of the tree on the left would be written in Lisp as: Binary tree_sentence_43

Binary tree_description_list_6

  • (((N O) I J) C D ((P) (Q)) F (M))Binary tree_item_6_13

which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child. Binary tree_sentence_44

Common operations Binary tree_section_12

There are a variety of different operations that can be performed on binary trees. Binary tree_sentence_45

Some are mutator operations, while others simply return useful information about the tree. Binary tree_sentence_46

Insertion Binary tree_section_13

Nodes can be inserted into binary trees in between two other nodes or added after a leaf node. Binary tree_sentence_47

In binary trees, a node that is inserted is specified as to which child it is. Binary tree_sentence_48

Leaf nodes Binary tree_section_14

To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent. Binary tree_sentence_49

Internal nodes Binary tree_section_15

Insertion on internal nodes is slightly more complex than on leaf nodes. Binary tree_sentence_50

Say that the internal node is node A and that node B is the child of A. Binary tree_sentence_51

(If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) Binary tree_sentence_52

A assigns its child to the new node and the new node assigns its parent to A. Binary tree_sentence_53

Then the new node assigns its child to B and B assigns its parent as the new node. Binary tree_sentence_54

Deletion Binary tree_section_16

Deletion is the process whereby a node is removed from the tree. Binary tree_sentence_55

Only certain nodes in a binary tree can be removed unambiguously. Binary tree_sentence_56

Node with zero or one children Binary tree_section_17

Suppose that the node to delete is node A. Binary tree_sentence_57

If A has no children, deletion is accomplished by setting the child of A's parent to null. Binary tree_sentence_58

If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child. Binary tree_sentence_59

Node with two children Binary tree_section_18

In a binary tree, a node with two children cannot be deleted unambiguously. Binary tree_sentence_60

However, in certain binary trees (including binary search trees) these nodes can be deleted, though with a rearrangement of the tree structure. Binary tree_sentence_61

Traversal Binary tree_section_19

Main article: Tree traversal Binary tree_sentence_62

Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. Binary tree_sentence_63

Depth-first order Binary tree_section_20

In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Binary tree_sentence_64

Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Binary tree_sentence_65

Pre-order is a special case of this. Binary tree_sentence_66

See depth-first search for more information. Binary tree_sentence_67

Breadth-first order Binary tree_section_21

Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. Binary tree_sentence_68

See breadth-first search for more information. Binary tree_sentence_69

Also called a level-order traversal. Binary tree_sentence_70

In a complete binary tree, a node's breadth-index (i − (2 − 1)) can be used as traversal instructions from the root. Binary tree_sentence_71

Reading bitwise from left to right, starting at bit d − 1, where d is the node's distance from the root (d = ⌊log2(i+1)⌋) and the node in question is not the root itself (d > 0). Binary tree_sentence_72

When the breadth-index is masked at bit d − 1, the bit values 0 and 1 mean to step either left or right, respectively. Binary tree_sentence_73

The process continues by successively checking the next bit to the right until there are no more. Binary tree_sentence_74

The rightmost bit indicates the final traversal from the desired node's parent to the node itself. Binary tree_sentence_75

There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer/s to its sibling/s. Binary tree_sentence_76

See also Binary tree_section_22

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Binary tree.