# 2 – 3 Trees Algorithm

In this article, we will learn the concept of **2 – 3 trees with its algorithm**.

Submitted by Shivangi Jain, on July 29, 2018

## 2 – 3 Trees

A 2 – 3 trees also known 3 – 2 trees is a tree in which each vertex, except leaf has 2 or 3 sons and one or two keys per node, and every path from the root to leaf is of the same length. The tree consisting of a single vertex is a 2 – 3 trees.

Let T be a 2 – 3 trees of height h. The number of vertices of T is between (2^h+1 - 1) and (3^h+1 - 1)/2, and the number of leaves is in between 2^h and 3^h.

Inserting a key K into a B tree T of height h is done in a single pass down the tree, requiring O (h) disk accesses. The CPU time required is O (th) = O (t log n). the B tree insert procedure uses B tree split child to guarantee that the recursion never descends to a full node.

**2 - 3 Trees**

## Algorithm

1. B tree insert (T, K) 2. r = root [T] 3. if n[r] = 2t – 1 4. then s = ALLOCATE – NODE () 5. root [T] = s 6. leaf [s] = FALSE 7. n [s] = 0 8. c1 [s] = r 9. B – TREE – SPLIT – CHILD (s, 1, r) 10. B – TREE – INSERT – NONFULL (s, k) 11. Else 12. B – TREE – INSERT – NONFULL (r, k)

The lines 4 to 10 deals with the case in which the root node r is full – the root is split and a new node s (having two children) becomes the root. Splitting the root is the only way to increase the height of a B tree. Unlike a binary search tree, a B tree increases in height at the top instead of at the bottom. Afterwards, the procedure finishes by calling B – TREE – INSERT – NONFULL to perform the insertion of key k in the tree rooted at the non-full root node. B – TREE – INSERT – NONFULL recurses as necessary down the tree, at all times guaranteeing that the node to which it recurses is not full by calling B – TREE- SPLIT – CHILD as necessary.

B – TREE – INSERT – NONFULL inserts a key K into the node x, which is assumed to be non-full when the procedure is called. The operation of B – TREE – INSERT and the recursive operation of B – TREE – INSERT – NONFULL guarantees that this assumption is true.

## Algorithm

1. B – TREE – INSERT – NONFULL (x, k) 2. i = n [x] 3. If leaf [x] 4. Then while i>= 1 and k< key(i) [x] 5. Do key(i+1)[x] = key (i) [x] 6. i = i – 1 7. key (i+1) [x] = k 8. n[x] = n[x] + 1 9. DISK_ WRITE (x) 10. Else while i>= 1 and K < key (i)[x] 11. Do i = i – 1 12. i = i + 1 13. DISK _ READ (c(i)[k]) 14. If n [c(i)[x]] = 2t - 1 15. Then B – TREE – SPLIT – CHILD (x, I, c(i)[x]) 16. If k> key (i)[x] 17. Then i = i + 1 18. B – TREE – INSERT – NONFULL (c(i)[x], k)

**References:**

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- P and NP problems and solutions | Algorithms
- Midpoint Circle Algorithm
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

Comments and Discussions!