A data structure is an arrangement
of data in a computer’s memory (or sometimes on a disk). Data structures
include arrays, linked lists, stacks, binary trees, and hash tables, among
others.
Tree is an acyclic connected graph where each node has zero or more children nodes and at most one parent node.
Tree is an acyclic connected graph where each node has zero or more children nodes and at most one parent node.
Properties of Tree data structure
Depth: It is the length of the path from the root to that node. It is counted by the number of edges traversed.
Height: It is the longest path from that node to its leaves. The height of a tree is the height of the root.
Leaf node: It has no children. Its only path is up to its parent.
Types of trees
Binary: Each node has
zero, one, or two children. This assertion makes many tree operations simple
and efficient.
Binary Search: A
binary tree where any left child node has a value less than its parent node and
any right child node has a value greater than or equal to that of its parent
node.
Traversal
Three different methods of traversal are possible for binary trees. They are 'preorder', 'postorder',
and 'in-order'. They differ from each other by the order in which they visit the current node, left subtree and right subtree.
Preorder: Current node, left
subtree, right subtree
Postorder: Left subtree, right
subtree, current node
In-order: Left subtree, current
node, right subtree
Data structure has many categories such as Lists, Trees, Hashes and Stacks. Each has its own way of organizing data, managing and fetching it from computer. I really like how you described very thoroughly about trees structure. However, other categories should be mentioned as well. Describing it as a whole, we can see how useful data structure to managing, organizing and fetching large amounts of data from computer. In addition, it can also be used to encrypt data and make it hard for unauthorized people to access it.
ReplyDeleteHi,
ReplyDeleteYour post is very informative and detailed. However, there are many different kinds of trees such B-trees, AVL trees, and Red-black trees. A binary tree is just a special case of B-trees. Also, a binary tree is only efficient when it is balanced. You could've elaborate more on that to make your post better.
Data structures always go hand-in-hand with algorithms. Without one, the other cannot be efficient. In my opinion, the most important data structure is Graph because it is the most general data structure and I think everything is derived from it.
A concise yet thorough overview of trees. The tone is a bit dry and could use some of your own insights on the subject as well as some explanations of the properties of trees that are less technical so that readers can better grasp the concepts you're introducing. I found it interesting that trees by definition are considered sets. I had pretty much come to the realization recently that they likely need to be as I struggled through some bugs I was having related to them, but finding out that it is formally part of their definition is good to know.
ReplyDelete