Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing

2-3 Trees and Basic Operations on them

2-3 Trees, like any other AVL trees or B-trees, are just a type of Height Balanced Tree. 2-3 Trees are the B-trees of order 3. Like every other B-tree, the leaf nodes of such trees are always at the same depth; hence, the height needs to be consistently adjusted on each update, either insertion or deletion.

The time complexity of various operations like Search, Insert, or deletion is O(logN).

Properties of 2-3 trees

The nodes of a 2-3 tree are classified into three categories. One type of node, also called the 2-node, has only one value and two sub-nodes. At the same time, the 3-node(s) have two data items and three sub-nodes. The third type of node is the leaf node. The data items stored in a 2-3 tree are always sorted, and each node in such trees can only be of one type of these three. The insertions in 2-3 trees are done through the leaf nodes only, and the height is adjusted accordingly.

The primary operations performed on a 2-3 tree are as follows:

  1. Searching
  2. Insertion
  3. Deletion

Let us try to understand each of them one by one:

Searching

In order to find any specific target value from a 3-order B-tree, you can use this recursive algorithm that returns either TRUE if the value is present or FALSE if the data item specified is not present in the tree in O(logN) time. Let us represent our 2-3 tree as Tr and try to search a value, say target.

The base case for the algorithm would be:

  1. If the tree is empty, Return FALSE (the empty tree cannot contain any value).
  2. If you reach the leaf node and still do not find the target, return FALSE.
  3. If you find the target at the current node, return TRUE.

Instructions that are called recursively:

As we know that the Tr is already a sorted tree, we use the binary search approach.

1. In case that target>Node.leftInfo, recursively call search for the left subtree of the node you are currently checking.

2. And if the target>Node.rightInfo, we search the target in the right subtree of the node we checked.

3. Otherwise, if the target is larger than the node.leftInfo but smaller than the Node.rightInfo, then explore the middle subtree.

2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them

Insertion

While inserting your data in a 2-3 tree, you can find three possible cases. These cases are explained here briefly. As insertion is done only at the leaf nodes in a tree, the potential instances you are likely to encounter are:

Case 1: The leaf node has only one data item. The insertion is pretty simple in this case, as you can directly insert the value at that node itself.

2-3 Trees and Basic Operations on them

Case 2: Leaf nodes have two data items, but the parent contains only one data item. In such a case, the leaf node is temporarily converted into a 3-item node with three data items. Then the middle element is moved to the parent node to split the current node, eliminating any three-item nodes from the tree.

2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them

Case 3: Leaf nodes have two data elements as well as their parent node. In such cases, the process of case 2 is repeated until no 3 item nodes are left in the hierarchy, hence automatically adjusting the height of your tree.

2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them

Deletion

While deleting any node from the 2-3 tree (3 order B-tree), the value to be deleted is simply replaced by the next value from the in-order traversal of the 2-3 tree.

If the node is left empty after the deletion of the value, it is merged with the adjacent node. Using examples can help us better understand the omission of values from a 2-3 tree. Let us look at the following tree and delete the two values, 54 and 79.

To delete the data item with value 54, first exchange its value with its successor in in-order traversal, which would be 79. Now the data item to be deleted is present in the leaf node, and hence easily remove the data item.

Now to delete the next item, 79, from the tree, exchange it with its successor to bring it to the leaf node and hence delete it from the tree.

But here, after removing the data item 79 from the tree, the node left behind is empty, and as we know that a 2-3 tree can never have any empty node, hence bring down the lowest data element from the parent node and merge it with its left adjacent node.

In the given 2-3 tree below, delete the values: 69, 72, 99, 81 from it.

2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them

After deletion of Node item 69.

2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them
2-3 Trees and Basic Operations on them



ADVERTISEMENT
ADVERTISEMENT