Class 8  >  Applications of tree data structure

Applications of tree data structure - Notes - Class 8

1 Crore+ students have signed up on EduRev. Have you?

Applications of tree data structure

Applications of tree data structure - Notes - Class 8

Why Tree?
Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.
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:
file system 
———– 

     /   <-- root

  /      \

...        home

      /          \

   ugrad        course

    /          /    |    \

  ...        cs101 cs112 cs113

  • If we organize keys in form of a tree (with some ordering e.g., BST), we can search for a given key in moderate time (quicker than Linked List and slower than arrays). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Logn) for search.
  • We can insert/delete keys in moderate time (quicker than Arrays and slower than Unordered Linked Lists). Self-balancing search trees like AVL and Red-Black trees guarantee an upper bound of O(Logn) for insertion/deletion.
  • Like Linked Lists and unlike Arrays, Pointer implementation of trees don’t have an upper limit on number of nodes as nodes are linked using pointers.
Other Applications : 
  • Store hierarchical data, like folder structure, organization structure, XML/HTML data.
  • Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item
  • Heap is a tree data structure which is implemented using arrays and used to implement priority queues.
  • B-Tree and B+ Tree : They are used to implement indexing in databases.
  • Syntax Tree:  Scanning, parsing , generation of code and evaluation of arithmetic expressions in Compiler design
  • K-D Tree: A space partitioning tree used to organize points in K dimensional space.
  • Trie : Used to implement dictionaries with prefix lookup.
  • Suffix Tree : For quick pattern searching in a fixed text.
  • Spanning Trees and shortest path trees are used in routers and bridges respectively in computer networks
  • As a workflow for compositing digital images for visual effects.
  • Decision trees.
  • Organization chart of a large organization.
The document Applications of tree data structure - Notes - Class 8 is a part of Class 8 category.
All you need of Class 8 at this link: Class 8
Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Download as PDF

Download free EduRev App

Track your progress, build streaks, highlight & save important lessons and more!

Related Searches

Applications of tree data structure - Notes - Class 8

,

practice quizzes

,

Extra Questions

,

Semester Notes

,

Important questions

,

Previous Year Questions with Solutions

,

Applications of tree data structure - Notes - Class 8

,

Summary

,

Exam

,

shortcuts and tricks

,

study material

,

video lectures

,

Free

,

past year papers

,

Objective type Questions

,

Sample Paper

,

mock tests for examination

,

pdf

,

MCQs

,

ppt

,

Viva Questions

,

Applications of tree data structure - Notes - Class 8

;