Chapter 6: TREES – 1. What is a Tree? Binary Tree Theory.

Tram Ho

6.1 What is a Tree?

A tree is a data structure similar to a linked list but instead of each node simply pointing to the next node in a linear fashion, in a tree each node points to some other node. Tree is an example of a nonlinear data structure. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.

In the ADT (Abstract Data Type) tree, the order of the elements doesn’t matter. If we need ordering information, linear data structures such as linked lists, stacks, queues, etc. can be used.

6.2 Glossary(Glossary)

image.png

  • The root of a tree is a node that has no parents. There can be at most one root node in a tree (node ​​A in the above example).
  • An edge refers to a parent-child link (all links in the figure).
  • A node that has no children is called a leaf node (E, J, K, H and I).
  • Child nodes with the same parent are called siblings (siblings – B, C, D are siblings of A and E, F are siblings of B).
  • A node p is the ancestor of node q if there exists a path from the origin to q and p occurs along the way. Node q is called descendant of p. For example, A, C and G are ancestors of K.
  • The set of all nodes at a certain depth is called the level of the tree (B, C and D are the same level). Root button is at zero.
  • The node depth is the length of the path from the root to the node (the depth of G is 2, A – C – G).
  • The height of a node is the length of the path from that node to the deepest node. The height of the tree is the length of the path from the root to the deepest node in the tree. A tree with only one node (root) has zero height. In the previous example, the height of B is 2 (B – F – J).
  • The height of the tree is the greatest height among all the nodes in the tree and the depth of the tree is the greatest depth among all the nodes in the tree. For a given tree, depth and height return the same value. But for individual nodes, we can get different results.

image.png

  • The size of a node is the number of child nodes it has including itself (the size of the C subtree is 3).
  • If every node in the tree has only one child node (except for the leaf nodes), we call such trees skew trees . If every node has only left children, we call them left skew trees . Similarly, if every node has only right children, we call them right skew trees .

image.png

6.3 Binary Trees

A tree is called a binary tree if each node has no children, one child, or two children. An empty tree is also a valid binary tree. We can imagine a binary tree consisting of a root and two discrete binary trees, called the left and right subtrees of the root.

image.png

Types of Binary Trees

Strict Binary Tree: A binary tree is called a Strict Binary Tree if each node has exactly two children or no children.

image.png

Full Binary Tree: A binary tree is called a Full Binary Tree if each node has exactly two child nodes and all the leaf nodes are at the same level.

image.png

Complete Binary Tree: Before defining the Complete Binary Tree, let us assume that the height of the binary tree is h. In a complete binary tree, if we number the nodes by starting from the root (assuming the root node has 1) then we get a complete sequence from 1 to the number of nodes in the tree.

While traversing, we should also number NULL pointers. A binary tree is said to be a complete binary tree if all the leaf nodes are at height h or h – 1 and also do not lack any numbers in the sequence.

image.png

Properties of Binary Trees

For the following properties, let us assume that the height of the tree is h. Also, assume that the root node is at zero height.

image.png

image.png

From the diagram below, we can infer the following properties:

  • The number of nodes n in a complete binary tree is
    2 H + first first 2 ^ { h + 1 } – 1 . Since there are h levels, we need to add all the nodes in each level
  • The number of nodes n in a complete binary tree ranges from
    2 H 2^h (minimum) to
  • The number of leaf nodes in a complete binary tree is
    2 H 2^h .
  • The number of NULL (wasted pointers) links in a complete binary tree has
    n n nodes aren + first n + 1 .

Structure of Binary Trees

Now let’s define the structure of the binary tree. For simplicity, assume that the data of the nodes are integers. One way to represent a node (containing data) is to have two links pointing to the left and right child nodes along with the data fields as shown below:

image.png

Note: In a tree, the default flow is from parent to child and directed branches are not required to be shown. For this section, we assume that both representations shown below are the same.

image.png

Operations on Binary Trees

Basic Operations

  • Add an element to the tree
  • Remove an element from the tree
  • Search in the tree
  • Browse trees

Auxiliary(backend) Operations

  • Find the size of the tree
  • Find the height of the tree
  • Find the level with the maximum total
  • Find the least common ancestor (LCA) for a given pair of nodes and many others.

Some applications of Binary Trees

Here are some applications where binary trees play an important role:

  • Expression trees are used in the compiler.
  • Huffman cipher trees are used in data compression algorithms.
  • Binary Search Tree (BST), which supports searching, inserting and deleting on a set of items in
    O ( l o g n ) O (logn) (average).
  • Priority Queue (PQ), which supports finding and deleting min (or max) on a collection of items in logarithmic (worst case) time.
Share the news now

Source : Viblo