TREES (DATA STRUCTURE)
Definition of a Tree
Trees can be defined as a collection of entities together to stimulate a hierarchy. A tree
is a non-linear data structure that stores elements in hierarchy order. A tree is
composed of nodes, each node contains a value and reference to its child nodes. The
node at the top of a tree is called the root while nodes at the base of the tree are
called the leaf, example of a tree is organisation chart. Trees are usually upside-down.
A tree is extremely useful for certain kinds of computations of Sums of a category. E.g.,
the total salaries paid to employees. This will be an implementation of all computations
which involve all the employees in the tree. An algorithm that systematically visits all
the items in a tree is called a tree traversal.
Definition of Concepts (1 of 3)
Root → This is the node at the topmost part of the tree.
Child → A direct descendant of a node in a tree. It is the immediate successor to
that mode.
Parent (of a node) → The node that is directly linked to a child node. It is the
immediate predecessor of that mode.
Siblings → A set of nodes having the same parent.
Leaf → A node with no child
Path: The sequence of consecutive edges from source node to destination node.
Edge: The link between two nodes.
Degree of a node → The number of children a node has.
Level of a node → The number of connections between the node and the root.
Dept of a node.
Height of a node → This is the number of connections between the node and the
root.
Height of a node → This is the number of connections between the leaf and the
node in longest path. It is the number of edges in the longest path from that node
to a leaf.
Height of a tree: The height of the root node.
Dept of a node: The dept of the tree is the total number of edges between the
root and the leaf on the largest path. It is also the length of path from root to that
mode.
Level of tree: height of a tree
n-nodes = (n – 1) edges
Binary Trees
Binary Trees is an extremely important and useful category of tree structure. A binary
tree is an N-ary tree for which N is two.
- Each node can have at most two entities.
Properties
The maximum node is 2L whereby Level is L
The maximum of node of height h = 2h + 1 – 1
Minimum of node of height = h + 1
1
Binary tree and its types
i. Full/ proper/ Strict
ii. Complete Binary tree
iii. Perfect Binary tree
iv. Degenerate Binary tree
v. Balanced trees.
1) Full Tree
- It is a binary tree where each node contains either 0 or 2 children. Each node
will contain exactly two children except leaf node.
2) Complete Binary tree
It is a binary tree where all the levels are completely filled except the last level. And
in the last level has nodes has left as possible.
3) Perfect Binary tree
- It is a binary tree as when all internal nodes have two children and all the
leaves nodes are at the same level.
4) Degenerate Binary tree
- It is a binary tree when all the internal node have just one child. Also called
left skilled binary tree/right skilled binary tree.
Advantages of Binary Trees
i. There is a relationship between binary trees and the binary number system.
ii. Binary trees are also very useful for the representation of mathematical
expressions involving the binary operations such as addition and
multiplication.
TREE-BASICS
The following is a mathematical definition of a tree:
Definition (Tree) A tree, T, is a finite, non-empty set of nodes, with the following
properties:
1. A designated node of the set, r, is called the root of the tree; and
2. The remaining nodes are partitioned into subsets, , , ..., , each of which is a tree.
For convenience, we shall use the notation to denote the tree T.
Notice that this definition is recursive—that is, a tree is defined in terms of itself!
Fortunately, we do not have a problem with infinite recursion because every tree has
a finite number of nodes and because in the base case, a tree has n=0 subtrees.
It follows from the definition that the minimal tree is a tree comprising a single root
node. For example is such a tree. When there is more than one node, the remaining
nodes are partitioned into subtrees.
2
3
