2-3 Trees and 2-3-4 Trees

2-3 Trees 

A 2-3 Tree is a data(tree) structure where every bode with children has either two children and two data elements 

2-3 Tree Structure

Properties 

1. Every internal node is a 2-node or a 3-node 
2. All leaves are at the same level 
3. All data is kept in sorted order.

Operations

1. Search 

               Similar to BST, since the data elements in each node is ordered 

2. Insertion

              Works by searching for the proper location of the key and adds it there. If the node becomes a 4-node, then the split from the 2-nodes and the middle key is moved up to the parent.

3. Deletion 

            Reverse of insertion

2-3-4 trees 

2-3-4 trees are self balancing data structure. The time complexity for the trees involve O(log(n))

Properties: 

• Every node is a 2-, 3- or a 4- node and hold 1,2,or 3 data elements respectuvely 
• All leaves are kept at same depth 
• All data is kept in sorted order.

Operations and working functions are similar to 2-3 Trees as explained above.

Blogs to refer: 1,2 

AVL Trees

AVL Tree is a self balancing Binary Search tree named after Soviet inventors George Adelson Velsky and Evangi Landis.

A height balanced BST is known as Avl which can have at most 1 difference with children.Height at leaves usually start with 0 but for AVL trees we do it from 1(for the ease of understanding).Here the difference between the left and right subtrees cannot be more than one for all nodes.Operations like Lookup, insertion and deleting all take  O(log(n)) time in both the average and worst case.

Operations:

Searching: Process is similar to search in ordinary Binary search tree.

Insertion: To make sure given tree remains AVL after every insertion. 

So we must rebalance, without violating the BST rule. The Insert operation involves two rotation 

1. Left Rotation 
2. Right Rotation

Steps to follow for Insertion:

1. Perform standard BST insert
2. Starting from w, find first unbalanced node
3. Rebalance the tree in the following ways accordingly 
1. Left Left case (Right Rotation)
2. Left right case (Left and right rotation)
3. Right Right case (Left Rotate)
4. Right left case (Right and Left Rotation)

AVL Tree Rebalancing

Algorithm

1.Perform normal BST insertion 2.Current node must be one of the ancestors of the newly inserted node. Update the height of the current node. 3.Get the balance factor(left-right subtree height) of the current node 4.If balance factor is greater than 1, then the current node is unbalanced and wer are either in the 1st case or second case to check whether it is 1st compare the newly inserted key with the key in left subtree root. 5.If balance factor is less than -1, then the current node is balanced and wer are either in 3rd case or 4th case.To check if it is 3rd ,compare the newly inserted node with node in the right subtree.


Deletion: Deletion follows the same procedure as Insertion except in place of insert we delete.


Blogs to follow: 1, 2, 3

Binary Search Trees (BST)

Binary Search Tree is a node based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with key's less than the node's key
• The right subtree of a node contains only nodes with keys greater than node's key
• The left and right subtree each must also be a binary search tree
• The tree must not have no duplicate nodes

The above properties provide an ordering among keys such that operations like 

1. Search
2. Min 
3. Max 

can be done fast enough.The tree actions are 

1. Search 
2. Insert 
3. Delete

There are many types of binary trees. Few among them are self balancing trees like 

1. AVL Trees
2. Red Black Trees
3. Splay Trees

All operations take time directly proportional to the height of the tree. Complexity at worst crosses O(h).

Optimal Binary Search Tree

If we do not plan to modify a search tree and if we know how exactly often each item will be accessed.We can construct an optimal binary search tree (with an average cost of looking up an item).

Also refer to Day - Stout - Warren Algorithm or DSW algorithm.

Trees: An Introduction

Trees are very flexible, versatile and powerful non-liner data structure that can be
used to represent data items possessing hierarchical relationship between the grand father
and his children and grand children as so on.


The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly above something is called its parent. For example, a is a child of f and f is the parent of a. Finally, elements with no children are called leaves.

Advantages of Trees

1. Trees can serve as a hierarchy 
2. Trees provide moderate access/search
3. Trees provide Moderate/insertion Deletion
4. Have no upper limit 

Main applications of trees include:

1. Manipulate hierarchical data.
2. Make information easy to search .
3. Manipulate sorted lists of data.
4. Router algorithms
5.  Form of a multi-stage decision-making.

A Tree Classification

---

Binary Tree

A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.

It can be represented as:  

1. Data 
2. Left pointer or Child
3. Right pointer or Child

Properties of a Binary tree

1) The maximum number of nodes at level ‘l’ of a binary tree is 2^(L-1).

Here level is number of nodes on path from root to the node (including root and node). Level of root is 1. This can be proved by induction.For root, L = 1, number of nodes = 2^(L-1) = 1.Assume that maximum number of nodes on level l is 2^(L-1).Since in Binary tree every node has at most 2 children, next level would have twice nodes, i.e. 2 * 2^(L-1)

2) Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1.

Here height of a tree is maximum number of nodes on root to leaf path. Height of a leaf node is considered as 1.

This result can be derived from point 2 above. A tree has maximum nodes if all levels have maximum nodes. So maximum number of nodes in a binary tree of height h is 1 + 2 + 4 + .. + 2^h-1. This is a simple geometric series with h terms and sum of this series is 2^h – 1.

3) In a Binary Tree with N nodes, minimum possible height or minimum number of levels is  ⌈Log(base2)(N+1)].

This can be directly derived from point 2 above. If we consider the convention where height of a leaf node is considered as 0, then above formula for minimum possible height becomes   

⌈ Log(base2)(N+1)⌉ – 1

4) A Binary Tree with L leaves has at least   ⌈ Log2L ⌉ + 1   levels

A Binary tree has maximum number of leaves when all levels are fully filled. Let all leaves be at level l, then below is true for number of leaves L.

   L   <=  2l-1  [From Point 1]

   Log2L <=  l-1

   l >=   ⌈ Log2L ⌉ + 1  

5) In Binary tree, number of leaf nodes is always one more than nodes with two children.

   L = T + 1

Where L = Number of leaf nodes

      T = Number of internal nodes with two children

Types of Binary trees:

1. Full Binary Tree ; A full binary tree is a binary tree which has exactly has either 2 children or  no children. (No. of leaf nodes=No, of internal nodes+1)
2. Complete Binary Tree: A complete Binary tree is a binary tree excepting the bottom which is filled from left to right.Its the best binary tree as it provides the best possible ration between the number of nodes and the height. O(log N) height h and nodes N. 2^(h+1)-1.
3. Strictly Binary tree: A strictly binary tree is a binary tree which has 2N -1 nodes i.e., no children or two children where N stands for degree.
4. Perfect Binary Tree:A perfect binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level.They are ambiguously also known as complete or full binary tree.
5. Balanced binary Tree:A balanced binary tree has the minimum possible maximum height (a.k.a. depth) for the leaf nodes, because for any given number of leaf nodes the leaf nodes are placed at the greatest height possible.

Tree Traversal 

Unlike other linear data structures, trees can be traversed in different ways.The ways to traverse trees are : 

1. Depth First Search 
1. Inorder Traversal     (Lc R Rc) //Where Lc=Left Child Rc= Right Child R=Root
2. Preorder Traversal   (R Lc Rc) //                   "
3. Postorder Traversal (Lc Rc R) //                   " 
2. Breadth first Search

References

More tree explanations shall be done with programs.

If you are given two traversal sequences, can you construct the binary tree?
It depends on what traversals are given. If one of the traversal methods is Inorder then the tree can be constructed, otherwise not.

Therefore, following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

And following do not.
Postorder and Preorder.
Preorder and Level-order.
Postorder and Level-order.

For example, Preorder, Level-order and Postorder traversals are same for the trees given in above diagram.

Preorder Traversal = AB
Postorder Traversal = BA
Level-Order Traversal = AB

So, even if three of them (Pre, Post and Level) are given, the tree can not be constructed.

Queue

Queue is a linear data structure which follows a FIFO(First In First Out) order.Classic example of queue can be a line in front of a bank cashier to deposit or withdraw money.

The primary difference between a stack and queue is that Stack is (Last In First Out) piling of data. Whereas as Queue is  First In First Out.

Queue data structure has two pointers.One being the front and other pointing the rear.

Operations of Queue:

1. Enqueue
2. Dequeue

Queue can be implemented using :

1. Array 
2. Linked list

Both have their own advantages or disadvantages.

Applications of Queue:

1. CPU scheduling & Disk Scheduling
2. IO buffers or asynchronous transfer 

More Links to follow.

Geeksforgeeks,org