1. Home
  2. Docs
  3. Discrete Structure
  4. Trees
  5. Application of Trees

Application of Trees

  • Binary Search Tree
  • Decision Tree
  • Game Tree
  • Prefix Codes

Binary Search Tree:

A binary tree is a finite set of elements that is either empty or partitioned into three disjoint subsets.

• The first subset contains the single elements called root of the tree.

Note: The binary tree is so named because each node can have at most two child nodes.

Strictly Binary Tree:

A binary tree is called strictly binary tree if every non-leaf node in a binary tree has non-empty left and right sub-tree.

Complete(Full) Binary Tree:

A strictly binary tree in which all the leaf nodes lies on same level is called complete binary tree.

Decision Tree:

A decision tree is a tree-like graph or model that uses a branching process to help make decisions.

• Each internal node in the tree represents a decision, and each branch represents a possible outcome of that decision. The leaf nodes of the tree represent the final outcomes of the decision process.

Game Tree:

A game tree is a tree-like graph that represents all possible moves in a game.

• The nodes of the tree represent the game states, and the edges of the tree represent the moves that can be made from one state to another.

Prefix Codes:

A prefix code is a code in which no codeword is a prefix of any other codeword. This means that no codeword can be formed by simply adding more bits to another codeword.

• Prefix codes are often used to encode data in a way that is efficient and minimizes the number of bits required. For example, prefix codes are used to encode text in Morse code and Huffman coding.

• One way to construct a prefix code is to use a binary tree. Each node in the tree represents a codeword, and the path from the root node to a leaf node represents the codeword for that leaf node.

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *