As a student in computer science, I am using BT(Binary Tree) to work on our project which requires us to create a parser for Scheme. To do it, I looked up many materials about Tree. In this post, I simply show you some what I got recently.
The tree is one of the most powerful of the advanced data structures and it often pops up in even more advanced subjects such as AI and compiler design.
In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes.
Mathematically, it is a tree, more specifically an arborescence: an acyclic connected graph where each node has zero or more children nodes and at most one parent node. Furthermore, the children of each node have a specific order.
In the big family, there are two important members: BT(Binary Tree) and BST(Binary Search Tree)
A binary tree is a tree-like structure that is rooted and in which each vertex has at most two children and each child of a vertex is designated as its left or right child (West 2000, p. 101). In other words, unlike a proper tree, the relative positions of the children is significant.
In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:[1]
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
It is very common to use Tree data structure in computer science. Why Tree? Unlike Array and Linked List, which are linear data structures, tree is hierarchical (or non-linear) data structure.
As per Wikipedia, following are the common uses of tree.
1. Manipulate hierarchical data.
2. Make information easy to search (see tree traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms.
References:
http://www.cs.bu.edu/teaching/c/tree/binary/
http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Common_uses
http://www.geeksforgeeks.org/applications-of-tree-data-structure/
http://www.i-programmer.info/babbages-bag/477-trees.html
Hi, this is a great post on Binary Tree, arguably the most used data structure in CS. I liked your mathematical perspective to interpret it as a type of graph or "Arborescence". I was also in the process of implementing the Parser for Scheme using Binary Tree, and it surprised me how recursion was useful for that. Also, the 4th and 5th common uses were new to me; I might want to look into them. Thanks for your post.
ReplyDelete