Drawing a 2-3 Tree & Inserting/Deleting Keys

In summary, the conversation discusses a 2-3 tree with a root containing the key 12 and nodes containing the keys 3, 6, 9, 15, 18, 21, 24, 27, 30, 33, and 36. The conversation also includes inserting the key 16 and deleting the key 6 in the tree. The resulting tree for the insert and deletion operations are shown.
  • #1
evinda
Gold Member
MHB
3,836
0
Hello! (Wave)

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,15,18,21,24, 27, 30, 33, 36$.

It is also given that the root is a 2-node that contains the number $12$.Draw the tree. PS: It is not required to make so many insertions as the above keys in an initially empty 2-3 tree. It is just required to draw only one tree that is a 2-3 tree and that contains the above keys at its nodes(which you have to decide if they should be 2-nodes or 3-nodes).

  • Insert the key 16 at the tree you drawed
  • Delete the key 6 at the tree you drawed
I tried to draw the required 2-3 as follows:View attachment 3885Could you tell me if it is right?
 

Attachments

  • two3.png
    two3.png
    4.5 KB · Views: 72
Technology news on Phys.org
  • #2
Yes, the tree you drew is correct.To insert the key 16, the tree should look like this:To delete the key 6, the tree should look like this:
 

FAQ: Drawing a 2-3 Tree & Inserting/Deleting Keys

What is a 2-3 Tree?

A 2-3 Tree is a type of data structure used in computer science for storing and organizing data in a hierarchical manner. It is a type of binary tree where each node can have either 2 or 3 child nodes.

How do you draw a 2-3 Tree?

To draw a 2-3 Tree, start by drawing a root node and then draw two or three child nodes directly below it. Each of these child nodes can then have two or three child nodes of their own, and so on. The tree should be balanced, meaning that all leaf nodes are at the same level.

How do you insert keys into a 2-3 Tree?

To insert a key into a 2-3 Tree, start by finding the appropriate location for the key within the tree. Then, if the node at that location already has two keys, split it into two nodes and promote the middle key to the parent node. Finally, insert the new key into the appropriate child node.

How do you delete keys from a 2-3 Tree?

To delete a key from a 2-3 Tree, start by finding the node that contains the key to be deleted. If the node is a leaf node, simply remove the key from the node. If the node is an internal node, replace the key with the smallest key from the right subtree and then remove that key from the right subtree.

What is the time complexity of inserting and deleting keys in a 2-3 Tree?

The time complexity of inserting and deleting keys in a 2-3 Tree is O(log n), where n is the number of keys in the tree. This is because the tree is always balanced, and the height of the tree increases by one for every additional key that is inserted or removed.

Similar threads

MHB Deleting Element from 2-3 Tree Example
Replies
1
Views
2K
MHB Drawing Binary Tree: Exploring Pre-Order & In-Order Traversal
Replies
14
Views
3K
Different Node Deletion/Insertion in a Binary Search Tree
Replies
5
Views
2K
MHB Understanding AVL Tree Rotations: Solving the Case RL
Replies
1
Views
1K
MHB Build Huffman Tree with Ternary System
Replies
1
Views
2K
MHB How Can You Check if a Binary Tree Satisfies the Properties of a 2-3 Tree?
Replies
4
Views
2K
Delete 'F', 'E', 'V' from 2-3 Tree
Replies
1
Views
1K
Binary Search Tree Homework - Setup BST & Write Functions
Replies
5
Views
2K
Printing a Binary Tree: Solving the Space Issue
Replies
8
Views
3K
Deleting Nodes w/ 2 Children from a BST
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top