You get a bonus - 1 coin for daily activity. Now you have 1 coin

Binary tree

Lecture



Binary tree is a hierarchical data structure in which each node has no more than two descendants (children). As a rule, the first is called the parent node, and children are called left and right heirs.

For practical purposes, two subspecies of binary trees are commonly used — the binary search tree and the binary heap.

Recursive definition

There is the following recursive definition of a binary tree (see BNF):

   :: = (  ) |  nil.

That is, a binary tree is either empty or consists of data and two subtrees (each of which may be empty). An obvious but important fact to understand is that each subtree in turn is also a tree. If a node has both subtrees empty, then it is called a leaf node (leaf vertex) or a terminal element.

For example, shown on the right in fig. 1 tree, according to this grammar could be written as:

  (m 
     (e 
         (c 
             (a nil nil)
             nil
         )
         (g 
             nil
             (k nil nil)
         )
      )
      (s
         (p (o nil nil) (s nil nil))
         (y nil nil)
      )
  )
  Binary tree

Fig. 1. Binary search tree, in which the keys are Latin characters ordered alphabetically.

Each node in the tree defines a subtree , the root of which it is. The vertex m = (data, left, right) has two children (left and right) left and right and, accordingly, two subtrees (left and right) with left and right roots.

Application

Many useful data structures are based on a binary tree:

  • Binary search tree
  • Binary heap
  • AVL-tree
  • Red and black tree
  • Matrix tree
  • Fibonacci tree
  • Suffix Tree

Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Discrete Math. Set theory. Graph theory. Combinatorics.

Terms: Discrete Math. Set theory. Graph theory. Combinatorics.