Please enable JavaScript.
Coggle requires JavaScript to display documents.
M8 - Algorithms and Data Structures - Coggle Diagram
M8 - Algorithms and Data Structures
1 Introduction
1.4 Fundamental Data Structures
Trees
A
tree
(more accurately, a
free tree
) is a connected
acyclic graph
Trees have several important properties:
the number of edges in a tree is always one less than the number of its vertices:
|E| = |V| − 1
for every two vertices in a tree, there always exists exactly one simple path from one of these vertices to the other.
This property makes it possible to select an arbitrary vertex in a free tree and consider it as the root of the so-called rooted tree.
Rooted Trees
A rooted tree is usually depicted by placing its
root on the top (level 0 of the tree)
, the
vertices adjacent
to the root below it (
level 1
), the
vertices two edges apart
from the root still below (
level 2
), and so on.
An obvious application of trees is for describing hierarchies
trees also are helpful in analysis of recursive
algorithms.
For any
vertex v
in a
tree T
, all the vertices on the simple path from the root to that vertex are called
ancestors of v.
The vertex itself is usually considered its
own ancestor
the set of ancestors that excludes the vertex itself is referred to as the set of
proper ancestors.
If (u, v) is the last edge of the simple path from the root to vertex v (and u != v),
u is said to be the parent of v and v is called a child of u
vertices that have the same parent are said to be
siblings
A vertex with no children is called a
leaf
a vertex with at least one child is called
parental
1 more item...
The
depth
of a vertex v is the length of the simple path from the root to v.
The
height
of a tree is the length of the longest simple path from the root to a leaf.
Ordered Trees
An ordered tree is a rooted tree in which all the children of each vertex are ordered.
It is convenient to assume that in a tree’s diagram, all the children are ordered left to right.
Binary Tree
a binary tree may also be empty
A binary tree can be defined as an ordered tree in which
every vertex has no more than two children
and each child is designated as either a left child or a right child of its parent
Since left and right subtrees are binary trees as well, a binary tree can also be defined recursively.
Note that a number assigned to each parental vertex is larger than all the numbers in its left subtree and smaller than all the numbers in its right subtree.
Such trees are called
binary search trees
.
binary search trees can be generalized to more general types of search trees called multiway search trees, which are indispensable for efficient access to very large data sets.
Therefore, the following inequalities for the
height h
of a binary tree with
n nodes
are especially important for analysis of such algorithms:
1 more item...
We can avoid this inconvenience by using nodes with just two pointers, as we did for binary trees. Here, however, the left pointer will point to the first child of the vertex, and the right pointer will point to its next sibling. Accordingly, this representation is called the
first child–next sibling representation.
4 Decrease-and-Conquer
4.5 Variable-Size-Decrease Algorithms
Searching and Insertion in a Binary Search Tree
When we need to search for an element of a given value v in such a tree, we do it recursively in the following manner
If the tree is not empty, we compare v with the tree’s root K(r). If they match, a desired element is found and the search can be stopped;
Thus, on each iteration of the algorithm, the problem of searching in a binary search tree is reduced to searching in a smaller binary search tree.
the worst-case efficiency of the search operation fall into Θ(n).
the average-case efficiency turns out to be in Θ(log n)
Since insertion of a new key into a binary search tree is almost identical to that of searching there, it also exemplifies the variable size-decrease technique and has the same efficiency characteristics as the search operation
5 Divide-and-Conquer
5.3 Binary Tree Traversals and Related Properties
The most important divide-and-conquer algorithms for binary trees are the three classic traversals:
In the preorder traversal, the root is visited before the left and right subtrees are visited (in that order)
In the inorder traversal, the root is visited after visiting its left subtree but before visiting the right subtree
In the postorder traversal, the root is visited after visiting the left and right subtrees (in that order).