Understanding Trees
Intro to Trees
Trees are relation-based data structure, which specializes in representing a hierarchical structure. Like a linked list, nodes contain both elements of data and pointers marking their relation to immediate nodes. A node can have zero or more children in a tree. Trees are non-linear data structures. This means that, unlike some other data structures like Arrays or Stacks, trees have no set start or end.
Tree Structure
The first node that is put into a Tree is called the root (hence why it’s called a tree, This node can have child nodes that can only be accessed by first accessing the root node. That second node can then have its own children and so on and so on. The tree is storing all of the data in a hierarchical manner, this means that if we want to get to a child node, we first have to go through the root and then to the parent and continue until we finally reach our desired node. Here are some terms used for a tree data structure :
- a Leaf is a node that doesn't have any children.
- the Root is the initial node that every other node is linked to, the top node.
- the Parent is the node that has reference to another node.
- a Child is any node that has a parent node linked to it
- a Sibling a node that shares the same parent as another node.
- The Height (h) of the tree is the distance (edge count) between the farthest leaf to the root.
- The Level of a node is the distance between the root and the node in question.
Advantages & Disadvantages of Trees
Some advantages of using trees are that they are Ideal for storing hierarchical relationships. Trees are Dynamic in size and never have a start or an end. They enable quick insert and delete operations. As great as trees are there are some disadvantages. Even though they are quick and dynamic to insert and delete nodes, trees are very slow at rearranging nodes. Also, child nodes hold no information about their parent node.
