Tree data structure

Tree Data Structure

Tree

Tree is a non-linear data structure [arrays, linked lists, stacks, and queues are linear data structure] made up of nodes and edges that are directed. Here the direction is from parent to children.

A tree can be empty with no nodes or a tree may consists of root node and zero or one or more sub-trees.

Tree has the following properties;

• Only one node is the root node (root does not have an incoming edge/link).

• Every other node is connected by a directed edge from exactly one other node. The node connected by a directed edge is the child node and the node where the link comes from is the parent node.

• Every node can have any number of children.

• If a node B has a path from node A, then A is called ancestor and B is called descendant.

• Nodes without any children is called leaf node (external node).

• Nodes with at least one child is called internal node.

• Set of nodes that have edges coming in from same node are called siblings.

• The number of edges from the root to a node is called the depth of the node.

• The number of edges from the root node to the deepest leaf node is the height of the tree.

• A set of nodes and edges that are connecting a node with its descendants is called as the path. The length of a path is 1 less than the number of nodes on that path.

• The number of children that a node has is called as degree of that node.

• A node B of a tree with all of its descendants is called as sub-tree with B as its root node.

 ***************

Go to Data structures main page

tree data structure

properties of tree data structure

terminologies used in defining tree data structure

terms you need to know about tree data structure

what is tree in data structure

definition of tree

important terminologies in tree data structure

Sorting algorithms compared on stable, in-place, comparison properties

Sorting algorithms compared on stable, in-place, and comparison properties

Stable sort - Sorting stability means that records with the same key retain their relative order before and after the sort.

 

In-place sort - A sort algorithm in which the sorted items occupy the same storage as the unsorted ones is in-place sort algorithm.

 

Comparison sort - It is an algorithm that compares two keys (values) and nothing else to find which one should appear first in the sorted list. 

Sorting algorithm	Stable?	Comparison?	In-place?
Quick sort	NO	YES	YES
Merge sort	YES	YES	NO
Heap sort	NO	YES	YES
Insertion sort	YES	YES	YES
Selection sort	NO	YES	YES
Bubble sort	YES	YES	YES
Least Significant Digit Radix sort	YES	NO
Most Significant Digit Radix sort	NO	NO	YES
Shell sort	NO	YES	YES

**********

Go to sorting algorithms - time complexity page

What is comparison sort?

What is In-place sort? 

What is stable sort?

compare different sorting algorithms on stable property, in-place property and comparison property,