Tree

-

What is Tree?


A tree is a data structure, each node points to a number of nodes. A tree is an example of non-linear data structures. A tree structure is a way of representing the hierarchical nature of a structure in a graphical form.


  • The root of a tree is the node with no parents.
  • A node with no children is called a leaf node.
  • Children of the same parent are called siblings.
  • A node "p" is an ancestor of node "q" if there exists a path from "root" to "q" and "p" appears on the path. The node "q" is called descendant of p.
  • Set of all node at a given depth is called the level of the tree. The root node is at level zero.
  • The height of the tree is the maximum height among all the nodes in the tree and depth of the tree is the maximum depth among all the nodes in the tree.

Binary Tree

A tree is called a binary tree if each node has zero child, one child or two children.

 Types of binary tree

  • Strict Binary Tree: If each node has exactly two children or no children.
  • Full Binary Tree: If each node has exactly two children and all the leaf node are at the same level.
  • Complete Binary Tree: If all leaf nodes are at height "h" or "h-1" and also without missing any number in the sequence.

Application of Binary Tree

  • Expression trees are used in compilers.
  • Huffman coding trees that are used in the data compression algorithm.
  • Binary Search Tree (BST), which supports search, insertion, and deletion on the collection of items in O(logn).
  • Priority Queues (PQ), which support search and deletion of minimum or maximum on the collection of items in logarithmic time (in worst case).
  • One reason to use trees might be because you want to store information that naturally forms a hierarchy. For example, the file system on a computer.
  • Manipulate hierarchical data.
  • Make information easy to search.
  • Manipulate sorted lists of data.
  • As a workflow for compositing digital images for visual effects.
  • Router algorithms.
  • Form of a multi-stage decision-making.
Location: Asia

Comments

Post a Comment

Popular posts from this blog

AVL (Adelson-Velskii and Landis) Trees

-
Image
What is AVL Tress? A binary tree is said to be an AVL Tree if: It is a binary search tree. For any node, the height of left subtree of node and height of right subtree of node differ by at most 1. Minimum/Maximum number of Nodes in AVL Tree Let the height of an AVL Tree is h and N(h) indicate the number of nodes in AVL Tree. Minimum number of nodes with height h is: N(h) = N(h-1) + N(h-2) + 1 N(h-1) indicates the minimum number of nodes with height h-1 . N(h-2) indicates the minimum number of nodes with height h-2 .   AVL Tree Declaration The declaration of AVL is similar to that of BST (Binary Search Tree). We include the height sldo as a part of a declaration. public class AVLTree {          int key, height;           AVLTree  left, right;           AVLTree  (int data) {                 key = d;                 height = 1;          }                 public int findHight( AVLTree  root ) {                 if(root
Read more

How to Build REST API Using PHP

-
Image
Create REST API in PHP API stands for Application Programming Interface and the idea behind API is to connect different applications irrespective of their platforms to share information. Generally, API takes requests from different applications, processes it and gives back the response. What is REST API? REST stands for Representational State Transfer and it means that the request and the response should contain a representation of the information i.e., should be in a certain format. So basically, the requests must use proper HTTP methods and the response must be in a proper format like JSON or XML instead of plain text. REST API is nothing but a normal API with a set of principles. We need to follow a set of rules while creating and consuming REST API. The rules include the following : 1. Use appropriate HTTP methods while performing API calls. The following are the four primary HTTP methods which should be used to send and receive API requests.       a. GET   
Read more