COMPARISON TREE

 

Difference between Full and Complete Binary Tree

A binary tree is a type of data structure where each node can only have two offspring at most named as “left” and “right” child.

A Binary Tree

There are different types of binary tree but here we are going to discuss about the difference of Complete binary tree and Full binary tree.

 Full Binary Tree:

A full binary tree is a binary tree in which all of the nodes have either 0 or 2 offspring. In other terms, a full binary tree is a binary tree in which all nodes, except the leaf nodes, have two offspring.

A Full Binary Tree

Let, i be the number of internal nodes
 n be the  total number of nodes
l be number of leaves
λ be number of levels

Then,

The number of leaves is (i + 1).
The total number of nodes is (2i + 1).
The number of internal nodes is (n – 1) / 2.
The number of leaves is (n + 1) / 2.
The total number of nodes is (2l – 1).
The number of internal nodes is (l – 1).
The number of leaves is at most (2λ – 1).

Complete Binary Tree:

A binary tree is said to be a complete binary tree if all its levels, except possibly the last level, have the maximum number of possible nodes, and all the nodes in the last level appear as far left as possible.

A Complete Binary Tree

There are 2 points that you can recognize from here,  

1. The leftmost side of the leaf node must always be filled first.
2. It isn’t necessary for the last leaf node to have a right sibling.

Check the following examples to understand the full and complete binary tree in a better way.

Example 1:

Neither complete nor full

• Node C has just one child therefore, it is not a Full binary tree. 
• Node C also has a right child but no left child, therefore it is also not a Complete binary tree. 

Hence, the binary tree shown above is neither complete nor full binary tree.

Example 2:

Full but not complete

• All of the nodes have either 0 or 2 offspring, therefore, it is a Full binary tree. 
• It is not a Complete binary tree because node B has no children whereas node C has children, and according to a complete binary tree, nodes should be filled from the left side.

Hence, the binary tree shown above is a Full binary tree and it is not a Complete binary tree.

Example 3:

Complete but not full

• It is a complete binary tree as all the nodes are left filled.
• Node B has just one child, therefore, it is not a full binary tree.

Hence, the binary tree shown above is a Complete binary tree and it is not a Full binary tree.

Example 4:

Complete and full

• It is a Complete binary tree because all the nodes are left filled.
• All of the nodes have either 0 or 2 offspring, therefore, it is a full binary tree.

Hence, the binary tree shown above is both a complete and a full binary tree.

S. No.	Complete Binary Tree	Full Binary Tree
1.	In a complete binary tree, a node in the last level can have only one child.	In a full binary tree, a node cannot have just one child.
2.	In a complete binary tree, the node should be filled from the left to right.	There is no order of filling nodes in a full binary tree.
3.	Complete binary trees are mainly used in heap-based data structures.	Full binary tree has no application as such but is also called a proper binary tree.
4.	A complete binary tree is also called almost complete binary tree.	A full binary tree also called  proper binary tree or 2-tree.

difference between B-tree and Binary tree:

S.NO	B-tree	Binary tree
1.	In a B-tree, a node can have maximum ‘M'(‘M’ is the order of the tree) number of child nodes.	While in binary tree, a node can have maximum two child nodes or sub-trees.
2.	B-tree is called a sorted tree as its nodes are sorted in inorder traversal.	While binary tree is not a sorted tree. It can be sorted in inorder, preorder, or postorder traversal.
3.	B-tree has a height of log(M*N) (Where ‘M’ is the order of tree and N is the number of nodes).	While binary tree has a height of log2(N) (Where N is the number of nodes).
4.	B-Tree is performed when the data is loaded into the disk.	Unlike B-tree, binary tree is performed when the data is loaded in the RAM(faster memory).
5.	B-tree is used in DBMS(code indexing, etc).	While binary tree is used in Huffman coding and Code optimization and many others.
6.	To insert the data or key in B-tree is more complicated than a binary tree.	While in binary tree, data insertion is not more complicated than B-tree.
7.	B-tree is a self-balancing tree. The height of the tree is automatically adjusted on each update.	A binary tree is not a self-balancing tree.

Comparison of Searching methods in Data Structures

the basic differences between two searching techniques, the sequential search and binary search.

Sequential Search	Binary Search
Time complexity is O(n)	Time complexity is O(log n)
Finds the key present at first position in constant time	Finds the key present at center position in constant time
Sequence of elements in the container does not affect.	The elements must be sorted in the container
Arrays and linked lists can be used to implement this	It cannot be implemented directly into the linked list. We need to change the basic rules of the list to implement this
Algorithm is iterative in nature	Algorithm technique is Divide and Conquer.
Algorithm is easy to implement, and requires less amount of code.	Algorithm is slightly complex. It takes more amount of code to implement.
N number of comparisons are required for worst case.	Log n number of comparisons are sufficient in worst case.

Difference between Binary Search Tree and AVL Tree

Binary Search Tree:

A binary Search Tree is a node-based binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

Binary Search Tree

AVL Tree: 

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one.

AVL Tree

Difference between Binary Search Tree and AVL Tree

Binary Search Tree	AVL Tree
In Binary Search Tree, every node does not follow the balance factor.	In AVL Tree, every node follows the balance factor i.e. 0, 1, -1.
Every Binary Search tree is not an AVL tree.	Every AVL tree is a Binary Search tree.
Simple to implement.	Complex to implement.
The height or depth of the tree is O(n).	The height or depth of the tree is O(logn)
Searching is not efficient when there are a large number of nodes in the Binary Search tree.	Searching is efficient because searching for the desired node is faster due to the balancing of height.
The Binary Search tree structure consists of 3 fields left subtree, data, and right subtree.	AVL tree structure consists of 4 fields left subtree, data, right subtree, and balancing factor.
It is not a balanced tree.	It is a balanced tree.
In Binary Search tree. Insertion and deletion are easy because no rotations are required.	In an AVL tree, Insertion and deletion are complex as it requires multiple rotations to balance the tree.

Red Black Tree vs AVL Tree

Red Black Tree: 

Properties:

1. Self-Balancing is provided by painting each node with two colors(Red or Black).
2. When the Tree is modified, a new tree is subsequently rearranged and repainted.
3. It requires 1 bit of color information for each node in the tree.
4. Time complexity: O(logn).

Constraints maintained by Red Black Tree:  

1. Root is always black.
2. All NULL leaves are black, and both children of a red node are black.
3. Every simple path from a given node to any of its descendant leaves contains the same number of black 
   nodes.
4. Path from root to farthest leaf is no more than twice as long as the path from the root to nearest leaf.
5. Time complexity: O(logn).

AVL(Adelson-Velskii and Landis) Tree
 

Properties:  

1. Height difference of the left and right subtree of the node should be less than 2.
2. Re-balancing is done when the heights of two child subtrees of a node differ by more than one.
3. Faster retrievals as strictly balanced.

Difference: 

Basis of comparison	Red Black Trees	AVL Trees
Lookups	Red Black Trees has fewer lookups because they are not strictly balanced.	AVL trees provide faster lookups than Red-Black Trees because they are more strictly balanced.
Colour	In this, the color of the node is either Red or Black.	In this, there is no color of the node.
Insertion and removal	Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.	AVL trees provide complex insertion and removal operations as more rotations are done due to relatively strict balancing.
Storage	Red Black Tree requires only 1 bit of information per node.	AVL trees store balance factors or heights with each node thus requiring storage for an integer per node.
Searching	It does not provide efficient searching.	It provides efficient searching.
Uses	Red-Black Trees are used in most of the language libraries like map, multimap, multiset in C++, etc.	AVL trees are used in databases where faster retrievals are required.
Balance Factor	It does not gave balance factor	Each node has a balance factor whose value will be 1,0,-1
Balancing	Take less processing for balancing i.e.; maximum two rotation required	Take more processing for balancing

Introduction to Red-Black

 Introduction to Red-Black

A Red-Black Tree is a self-balancing binary search tree where each node has an additional attribute: a color, which can be either red or black. The primary objective of these trees is to maintain balance during insertions and deletions, ensuring efficient data retrieval and manipulation.

Red Black Tree is a Binary Search Tree in which every node is colored either RED or BLACK.

Every Red Black Tree has the following properties.

Property #1: Red - Black Tree must be a Binary Search Tree.

Property #2: The ROOT node must be colored BLACK.

Property #3: The children of Red colored node must be colored BLACK. (There should not be two consecutive RED nodes).

Property #4: In all the paths of the tree, there should be same number of BLACK colored nodes.

Property #5: Every new node must be inserted with RED color.

Property #6: Every leaf (e.i. NULL node) must be colored BLACK.

Node Color: Each node is either red or black.

Root Property: The root of the tree is always black.

Red Property: Red nodes cannot have red children (no two consecutive red nodes on any path).

Black Property: Every path from a node to its descendant null nodes (leaves) has the same number of black nodes.

Leaf Property: All leaves (NIL nodes) are black.

Insertion into RED BLACK Tree

In a Red-Black Tree, every new node must be inserted with the color RED. The insertion operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is inserted with a color property. After every insertion operation, we need to check all the properties of Red-Black Tree. If all the properties are satisfied then we go to next operation otherwise we perform the following operation to make it Red Black Tree.

 

1. Recolor

2. Rotation

3. Rotation followed by Recolor

The insertion operation in Red Black tree is performed using the following steps...

Step 1 - Check whether tree is Empty.

Step 2 - If tree is Empty then insert the new Node as Root node with color Black and exit from the operation.

Step 3 - If tree is not Empty then insert the new Node as leaf node with color Red.

Step 4 - If the parent of new Node is Black then exit from the operation.

Step 5 - If the parent of new Node is Red then check the color of parent node's sibling of new Node.

Step 6 - If it is colored Black or NULL then make suitable Rotation and Recolor it.

Step 7 - If it is colored Red then perform Recolor. Repeat the same until tree becomes Red Black Tree.

Example:

Create a RED BLACK Tree by inserting the following sequence of numbers 8, 18, 5, 15, 17, 25, 40 & 80.

Sol:

insert (8):  Tree is Empty. So insert newNode as Root node with black color.

insert (18) :  Tree is not Empty. So insert newNode with red color.

insert (5) : Tree is not Empty. So insert newNode with red color.

insert (15) : Tree is not Empty. So insert newNode with red color.

insert (17) : Tree is not Empty. So insert newNode with red color.

insert (25) : Tree is not Empty. So insert newNode with red color.

insert (40) : Tree is not Empty. So insert newNode with red color.

insert (80) : Tree is not Empty. So insert newNode with red color.

finally, the above tree satisfies all the properties of the Red-Black Tree.