{"id":27017,"date":"2018-01-02T20:46:12","date_gmt":"2018-01-02T15:16:12","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27017"},"modified":"2018-01-02T20:46:12","modified_gmt":"2018-01-02T15:16:12","slug":"applications-tree-data-structure","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/applications-tree-data-structure\/","title":{"rendered":"Applications of tree data structure"},"content":{"rendered":"<p><strong>Difficulty Level: <\/strong>Rookie<\/p>\n<p><strong>Why Tree?<\/strong><br \/>\nUnlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.<span id=\"more-10442\"><\/span><\/p>\n<p>1) 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:<\/p>\n<p>file system<br \/>\n\u2014\u2014\u2014\u2013<\/p>\n<pre>     \/   &lt;-- root\r\n  \/      \\\r\n...        home\r\n      \/          \\\r\n   ugrad        course\r\n    \/          \/    |    \\\r\n  ...        cs101 cs112 cs113\r\n<\/pre>\n<p>2) 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). <a href=\"http:\/\/en.wikipedia.org\/wiki\/Self-balancing_binary_search_tree\" target=\"_blank\" rel=\"noopener\">Self-balancing search trees <\/a>like <a href=\"http:\/\/en.wikipedia.org\/wiki\/AVL_tree\" target=\"_blank\" rel=\"noopener\">AVL<\/a> and <a href=\"http:\/\/en.wikipedia.org\/wiki\/Red-black_tree\" target=\"_blank\" rel=\"noopener\">Red-Black trees<\/a> guarantee an upper bound of O(Logn) for search.<\/p>\n<p>3) We can insert\/delete keys in moderate time (quicker than Arrays and slower than Unordered Linked Lists). <a href=\"http:\/\/en.wikipedia.org\/wiki\/Self-balancing_binary_search_tree\" target=\"_blank\" rel=\"noopener\">Self-balancing search trees <\/a>like <a href=\"http:\/\/en.wikipedia.org\/wiki\/AVL_tree\" target=\"_blank\" rel=\"noopener\">AVL<\/a> and <a href=\"http:\/\/en.wikipedia.org\/wiki\/Red-black_tree\" target=\"_blank\" rel=\"noopener\">Red-Black trees<\/a> guarantee an upper bound of O(Logn) for insertion\/deletion.<\/p>\n<p>4) Like Linked Lists and unlike Arrays, Pointer implementation of trees don\u2019t have an upper limit on number of nodes as nodes are linked using pointers.<\/p>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Tree_%28data_structure%29#Common_uses\" target=\"_blank\" rel=\"noopener\">As per Wikipedia<\/a>, following are the common uses of tree.<br \/>\n1. Manipulate hierarchical data.<br \/>\n2. Make information easy to search (see tree traversal).<br \/>\n3. Manipulate sorted lists of data.<br \/>\n4. As a workflow for compositing digital images for visual effects.<br \/>\n5. Router algorithms.<\/p>\n[ad type=&#8221;banner&#8221;]\n","protected":false},"excerpt":{"rendered":"<p>Applications of tree data structure &#8211; Data Structure &#8211;  Unlike Array and Linked List, which are linear data structures, tree is hierarchical data structure.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140,73012],"tags":[80617,80623,80621,80618,80619,80620,80622,80555],"class_list":["post-27017","post","type-post","status-publish","format-standard","hentry","category-binay-tree","category-data-structures","tag-application-of-binary-tree-in-data-structure","tag-application-of-binary-tree-in-data-structure-pdf","tag-application-of-binary-tree-in-real-life","tag-application-of-graph-data-structure","tag-application-of-tree-data-structure-in-real-life","tag-application-of-tree-in-data-structure-ppt","tag-application-of-trees-in-data-structure-pdf","tag-applications-of-binary-search-tree-in-real-life"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27017","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27017"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27017\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27017"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27017"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27017"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}