Introduction to 2-3 Tree

Estimated Time

1 hour

Prerequisites of the Experiment

Overview of the Experiment

The experiment features a series of modules with video lectures, hands-on practice exercises and quizzes for self analysis.

Learning Objectives of the Experiment

In this experiment, we will learn the following:

  • Structure, representation and implementation of 2-3 Tree data structure.
  • Insertion in a 2-3 tree.
  • Deletion from a 2-3 tree.
  • Find/Search in a 2-3 tree.

Experiment Modules & their Weightage

Module Weightage Expectation
Pre-test 15% Solve All Questions
2-3 Basics 25% Understand the 2-3 Tree basics
Operations 35% Understand the 2-3 Tree Algorithm
Post-test 25% Solve all Questions

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-test

Pretest includes questions on

  • Binary Trees
  • Binary Search Trees
Read the questions below and select the correct options from the ones given. Some questions may have multiple correct answers.

A Quiz with Multiple Choice Questions

Q1. Which of the following statements are correct about a binary tree?

(A) A node in a binary tree can have exactly two children

(B) A node in a binary tree can have atmost two children

(C) A node in a binary tree can have two or more children

(D) A node in a binary tree can have two or more children

A node in a binary tree, by definition, can have atmost two children.

Q2. Node values in a binary tree always appear in a sorted order from root to leaf, going left to right at each level.

(A) True

(B) False

There is no specific order in which keys are stored in a binary tree.

Q3. Which of the following is TRUE about the leaf nodes of a binary tree?

(A) Leaf nodes in a binary tree have no children

(B) Atleast one leaf node in a binary tree has two chidren

(C) Leaf nodes in a binary tree are allowed to have more than two children

(D) Leaf nodes in a binary tree may or may not have child nodes

Leaf nodes in a binary tree have no children, and this is the reason why they are called "leaf". Leaf nodes appear at the last level of the tree.

Q4. In a binary search tree all nodes in the left subtree are __________.

(A) SMALLER than the root

(B) GREATER than the root

(C) EQUAL to the root

All nodes in the left subtree of the root in a binary search tree are smaller than the root.

Q5. What is the worst case height possible in a binary search tree? Let N be the number of nodes in the tree.

(A) O(log N)

(B) O(N)

(C) O(1)

(D) None of the above

A BST need not be balanced and therefore, the worst case height possible is O(N), where N is the number of nodes in the tree.

Basics of 2-3 Tree

Estimated Time

15 minutes

Introduction to 2-3 Tree

Welcome to this module on tree 2-3 trees! Take a look at what you will go through in the module.

  • What is a 2-3 tree?
  • Different types of nodes in a 2-3 tree.
  • Various operations.
  • A quiz to check your understanding of concepts of 2-3 tree

Basics of 2-3 Tree

Welcome to 2-3 tree Experiment!

Video introduction to 2-3 tree experiment should be displayed here!

Definition

2–3 tree is a perfectly balanced binary search tree. It is called a 2-3 tree because each internal node has either 2 or 3 children. In 2-3 tree, every path from root to leaf has the same length and the data structure guarantees worst case O(log n) time complexity for search and insert operations.

2-3 Nodes

There are three types of nodes in a 2-3 tree

  • 2 Node: An internal node is a 2-node if it has one data element and two children.
  • 3 Node: An internal node is a 3-node if it has two data elements and three children.
  • Leaf Node: A leaf node contains only data elements and has no children.

Pictorial Representation of 2-3 tree nodes

Pictorial Representation of 2-3 tree

Properties of 2-3 tree

2-3 tree has the following properties:

  • Every internal node is a 2-node or a 3-node.
  • All leaves are at the same level.
  • All data is kept in sorted order. This means that:
    • In case of a 2 Node, data items in left subtree are smaller than root and data items in right subtree are greater than root.
    • In case of a 3 Node, data items in left subtree are smaller than root, data items in middle subtree are greater than root and data items in the right subtree are greater than the root and middle subtree.

2-3 Tree vs BST

  • The main advantage with 2-3 trees is that it is balanced in nature as opposed to a binary search tree whose height in the worst case can be O(N).
  • Due to this, the worst case time-complexity of operations such as search, insertion and deletion is O(Log(N)) as the height of a 2-3 tree is O(Log(N)).

A Quiz with Multiple Choice Questions

Q1. Which of the following is true?

(A) Data in a 2-3 tree is stored in unsorted manner

(B) Data in a 2-3 tree is stored in a sorted manner

(C) There is no ordering among data items in a 2-3 tree

(D) Only leaf nodes have sorted data items

Data items in a 2-3 tree are stored in a sorted manner. The left subtree has data items smaller than the root, the middle subtree has data item greater than root and smaller than right subtree and the right subtree has data items greater than left and middle subtree.

Q2. Which of the following is true?

(A) Leaf nodes in a 2-3 tree can be at any level

(B) Leaf nodes in a 2-3 tree can be only at odd levels

(C) All leaf nodes in a 2-3 have the same level

(D) None of the above

An important property of 2-3 is that all leaf nodes have the same level.

Q3. Which of the following best describes a 2-node?

(A) A 2-node has one data item and two children

(B) A 2-node has two data items and two children

(C) A 2-node has one data item and one child

(D) None of the above

By definition, a 2-node has one data item and two children.

Q4. Which of the following best describes a 3-node?

(A) A 3-node has one data item and two children

(B) A 3-node has two data items and three children

(C) A 3-node has one data item and one child

(D) None of the above

By definition, A 3-node has two data items and three children.

Operations

Estimated Time

30 minutes

Operations on 2-3 trees

Welcome to this module on operations on 2-3 tree! Take a look at what you will go through in this module.

  • Insertion in a 2-3 tree
  • Search in a 2-3 tree
  • Deletion in a 2-3 tree
  • A quiz to check your understanding of 2-3 tree.

Search

2-3 Search Video

2-3 Search Video should be displayed here!

Intuition

Searching for an item in a 2–3 tree is similar to searching for an item in a binary search tree. Since the data elements in each node are ordered, a search function will be directed to the correct subtree and eventually to the correct node which contains the item.

Search in a 2-Node

Search in a 2-Node

Search in a 3-Node

Search in a 3-Node

Algorithm

  • 1. Let T be a 2–3 tree and d be the data element we want to find. If T is empty, then d is not in T and we're done.
  • 2. Let r be the root of T.
  • 3. Suppose r is a leaf.
    • If d is not in r, then d is not in T and we're done.
    • Otherwise, d is in T. In particular, d can be found at a leaf node. We need no further steps and we're done.
  • 4. Suppose r is a 2-node with left child L and right child R. Let e be the data element in r. There are three cases:
    • If d = e, then we've found d in T and we're done.
    • If d < e, then set T to L, which by definition is a 2–3 tree, and go back to step 2.
    • If d > e, then set T to R and go back to step 2.
  • 5. Suppose r is a 3-node with left child L, middle child M, and right child R. Let a and b be the two data elements of r, where a < b. There are four cases:
    • If d is equal to a or b, then d is in T and we're done.
    • If d < a, then set T to L and go back to step 2.
    • If a < d < b, then set T to M and go back to step 2.
    • If d > b, then set T to R and go back to step 2.

Insertion

2-3 Insertion Video

2-3 Insertion Video should be displayed here!

Intuition

Insertion in a 2-3 tree is very different from a Binary Search Tree as in a 2-3 tree, a node can have one data item (2-Node) or two data items (3-Node). At first, we search for the correct position of the new data element to be inserted into the tree. Once, we have found the postion of the new data element, one of the two conditions arise:

  • The data element is to be inserted as a new node. In this case, we simply create a new node and insert the data element.
  • In another case, the new data element is to be inserted in an already full node. Here, full node means a node which cannot accomodate any new element. This results in splitting of the node

Insert in a node with only one data element

Insert in a node with only one data element

Insert in a node with two data elements whose parent contains only one data element.

Insert in a node with two data elements whose parent contains only one data element.

Insert in a node with two data elements whose parent also contains two data elements.

Insert in a node with two data elements whose parent also contains two data elements.

Algorithm

  • If the tree is empty, create a new node and insert the data item. Done.
  • If the tree has only one node with one data element, insert the new element in this node. Done.
  • Otherwise, search for the correct position of the new element.
  • If the new element is to be inserted in a node with only one data element. Perform insert and we're done.
  • If the new element is to be inserted in a node with two data elements and whose parent contains only one data element.
    • Insert the node in its correct position; this creates a temporary node with three data items.
    • Split the temporary node, by moving the medium element to the root. This results in creation of a 3-Node and we're done.
  • If the new element is to be inserted in a node with two data elements and whose parent also contains two data elements.
    • Insert the node in its correct position, this creates a temporary node with three data items.
    • Move the median element to the parent node and split the current node into two nodes. Now, the parent becomes a temporary node with three elements.
    • Split the parent node by moving the median element one level up, this creates a new root of the current subtree and we're done.

Deletion

2-3 Deletion Video

2-3 Deletion Video should be displayed here!

Intuition

  • Deletion in a 2-3 is again different from that of a Binary Search tree. Recall that, in a 2-3 tree there are two types of nodes viz., 2-Node and 3-Node. When we delete a data element from the node of a 2-3 tree, it might lead to the property of the tree being violated.
  • In order to maintain the property of a 2-3 tree even after deletion of a data element, we perform various operations such as merge, split and redistribution of elements in the tree.

Delete a data element from an internal node.

Delete a data element from an internal node.

Delete a data element from leaf node.

Delete a data element from leaf node.

Algorithm

  • If the data element to be deleted in the only element in the tree. Delete the node and we're done.
  • If the data element to be deleted is a present in the leaf. Then, delete the data element. However, this deletion will result in violation of the 2-3 tree property. To correct this, we perform redistribution and merging of elements in the node such that the property is preserved.
  • If the data element to be deleted is present in an internal node. Then, replace this data element with the inorder successor of the element. Now, delete the element according to step 2.

Demo for operations on 2-3 tree

Demo for operations on 2-3 tree

Practice for operations on 2-3 tree

Practice for operations on 2-3 tree

Exercise for operations on 2-3 tree

Exercise for operations on 2-3 tree

Post-Test Quiz

Estimated Time

10 minutes

Instructions for Post-Test

Post-test includes questions on

  • Insertion in 2-3 tree
  • Deletion in 2-3 tree
  • Search in a 2-3 tree
Read the questions below and select the correct options from the ones given. Some questions may have multiple correct answers.

A Quiz with Multiple Choice Questions

Q1. Which of the following statements are correct about a 2-3 tree?

(A) A 2-3 tree has either 2 keys or 3 keys in every node

(B) A 2-3 has two types of nodes, namely 2-node and 3-node

(C) A node in a 2-3 tree can have only only one child

(D) A node in a 2-3 tree can have more than one root

By definition, a 2-3 tree can have 2-node and 3-node.

Q2. Key values in the nodes of a 2-3 tree always appear sorted from top to bottom and left to right in the tree.

(A) True

(B) False

Keys in a 2-3 tree are always sorted.

Q3. Keys in a 2-3 tree are always sorted when __________.

(A) All leaves in a 2-3 tree are at the same level

(B) Atleast one leaf node in a 2-3 tree has two chidren

(C) Leaf nodes in a 2-3 tree are allowed to have more than two children

(D) Leaf nodes in a 2-3 tree may or may not have child nodes

Leaf nodes in a 2-3 tree are at the same level

Q4. Which of the following is correct about a 2-node?

(A) A two node has only one child

(B) A two node has one data element and two children

(C) A two node has one data element and two children

A two node has one data element and two children.

Q5. What is the time complexity of search in a 2-3 tree?

(A) O(log N)

(B) O(N)

(C) O(1)

(D) None of the above

A 2-3 is a balanced tree so the time complexity of search is O(log N).

Further Readings and References of the Experiment

Explore 2-3 Tree

You can explore more about tree traversal through following resources:

Theory

Practice

Quizzes