What TREES are you thinking of?
When I say the word trees, what’s the first picture that comes into your mind? Perhaps it’s the gigantic green trees at your favorite national park with roots forming a trunk as wide as your SUV? Or maybe it’s a picture of your family tree that comes into mind because you’re family oriented. One thing is certain, If you’re in the world of coding, TREES(the ones known as non- linear data structures) wouldn’t fail to cross your mind.
TREES in Data Structures can be imaged similarly to how family trees work. For instance, family trees and TREES in data structures are very similar to how they are identified and organized hierarchically with relationships from all generations including grandparents, parents, children, and siblings etc.
In addition, you may find organizations also using similar trees of hierarchy.
So, What is a TREE data structures you ask?
A tree is a collection of entities called nodes which are connected by directed (or undirected) edges. A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.
Parts of a TREE data structure
The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child.The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child. Other important concepts to understand are height and depth. The height of a tree is the length of the longest path to a leaf. The depth of a node is the length of the path to its root.
General properties:
Root-Topmost node
Parent- Node that comes before
Child- Node that comes after
Leaf- Node with no children
Ancestor- Node reachable from child to parent
Descendant- Node reachable from parent to child
Internal Node- Node with at least one child
Height (tree)- number of edges on longest downward path from root to leaf
Height (node)- number of edges on longest downward path from node to leaf
level 1 + number of edges between the node and the root
Depth-number of edges between the node and the root
Size- number of nodes in the tree
Types of Trees?
There are different types of trees that you can work with. The most common type of tree is a binary tree. This type of tree is so named because each parent node can only have two children. Other types of trees consist of a parent node being able to have more than 2 children.
The deciding factor of which tree type to use is performance. Since trees are data structures, performance is measured in terms of inserting and retrieving data.
Implementation
Each node in a tree can have an arbitrary number of children, and that number is not known in advance, the general tree can be implemented using a first child/next sibling method. Each node will have TWO pointers: one to the leftmost child, and one to the rightmost sibling. The following picture illustrates this
A General Tree
A general tree is a tree where each node may have zero or more children (a binary tree is a specialized case of a general tree). General trees are used to model applications such as file systems.
Binary Trees
A binary tree in which each node has exactly zero or two children is called a full binary tree. In a full tree, there are no nodes with exactly one child.
A complete binary tree is a tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.
Balanced Trees
Binary Search Trees
An important property of a Binary Search Tree is that the value of a Binary Search Tree node is larger than the value of the offspring of its left child, but smaller than the value of the offspring of its right child.”
“A Binary Search Tree is sometimes called ordered or sorted binary trees, and it keeps its values in sorted order, so that lookup and other operations can use the principle of binary search” — Wikipedia
Binary Search Trees are used for the following reasons by programmers:
- Fast search, insertion, deletion- especially when balanced
- Simple implementation for good performance
- Sort as you instead of sorting all at once
- Does Not have to reallocate memory to grow ( such as a hash table)
