Consider the following 2-3 tree containing data items whose keys are the names of the items:...

 

Transcribed Image Text:

Consider the following 2-3 tree containing data items whose keys are the names of the items: Potion of Healing +1 Mace 2000 Blue loun Stone Blue loun Stone 20000 Leather Armor Plate Armor Leather Armor 10 Plate Armor 350 Potion of Healing 100 Vampiric Blade Vampiric Blade 12000 Draw the result of inserting the items (Potion of Growth, 300) and (Mantle of Protection, 4200), in that order. Draw the new tree after each insertion. Your answer should consist of two trees (you can show additional intermediate results if you like, but at a minimum you must show the two trees after each completed insertion). Hint Recall that once items are deleted from a 2-3 tree it is possible to have keys in the internal nodes that have no corresponding keyed item at the leaf level. This tree reflects that, for example, "Entropic Armor" is an internal node key, but there is no item with the key "Entropic Armor" at the leaf level. This normal and does not alter the deletion algorithm in any way. Just work with the keys that are there. I Consider the following 2-3 tree containing data items whose keys are the names of the items: Amulet of Health 2700 Armageddon Belt of Giant Donut Strength Armageddon Donut 12000 Dust of Deliciousness 300 Earthbound Boots Gauntlets of Arrow Catching Entropic Armor Earthbound Boots 1700 Flame Arrow 650 loun Stone Hideous Halberd 15 Kneepads of Allure loun Stone 4500 Kneepads of Allure 1400 Psionic Blader Rusty Sword Psionic Blade 9200 Rusty Sword 2 Scroll of Conjure Milk Unnatural Axe Star Razor Scroll of Conjure Milk 5 Sunblade 5000 Unnatural Axe 4200 Vorpal Blade Waffles of Shame Vorpal Blade 25000 Waffles of Shame 1 Draw the result of deleting the items (Hideous Halberd, 15), (Armageddon Donut, 12000), (Dust of Deliciousness, 300), and (Earthbound Boots, 1700) in that order. Draw the new tree after each deletion. Your answer should consist of four trees (you can show additional intermediate results if you like, but at a minimum you must show the four trees after each completed deletion). Hint Recall that once items are deleted from a 2-3 tree it is possible to have keys in the internal nodes that have no corresponding keyed item at the leaf level. This tree reflects that, for example, "Entropic Armor" is an internal node key, but there is no item with the key "Entropic Armor" at the leaf level. This normal and does not alter the deletion algorithm in any way. Just work with the keys that are there. Consider the following 2-3 tree containing data items whose keys are the names of the items: Potion of Healing +1 Mace 2000 Blue loun Stone Blue loun Stone 20000 Leather Armor Plate Armor Leather Armor 10 Plate Armor 350 Potion of Healing 100 Vampiric Blade Vampiric Blade 12000 Draw the result of inserting the items (Potion of Growth, 300) and (Mantle of Protection, 4200), in that order. Draw the new tree after each insertion. Your answer should consist of two trees (you can show additional intermediate results if you like, but at a minimum you must show the two trees after each completed insertion). Hint Recall that once items are deleted from a 2-3 tree it is possible to have keys in the internal nodes that have no corresponding keyed item at the leaf level. This tree reflects that, for example, "Entropic Armor" is an internal node key, but there is no item with the key "Entropic Armor" at the leaf level. This normal and does not alter the deletion algorithm in any way. Just work with the keys that are there. I Consider the following 2-3 tree containing data items whose keys are the names of the items: Amulet of Health 2700 Armageddon Belt of Giant Donut Strength Armageddon Donut 12000 Dust of Deliciousness 300 Earthbound Boots Gauntlets of Arrow Catching Entropic Armor Earthbound Boots 1700 Flame Arrow 650 loun Stone Hideous Halberd 15 Kneepads of Allure loun Stone 4500 Kneepads of Allure 1400 Psionic Blader Rusty Sword Psionic Blade 9200 Rusty Sword 2 Scroll of Conjure Milk Unnatural Axe Star Razor Scroll of Conjure Milk 5 Sunblade 5000 Unnatural Axe 4200 Vorpal Blade Waffles of Shame Vorpal Blade 25000 Waffles of Shame 1 Draw the result of deleting the items (Hideous Halberd, 15), (Armageddon Donut, 12000), (Dust of Deliciousness, 300), and (Earthbound Boots, 1700) in that order. Draw the new tree after each deletion. Your answer should consist of four trees (you can show additional intermediate results if you like, but at a minimum you must show the four trees after each completed deletion). Hint Recall that once items are deleted from a 2-3 tree it is possible to have keys in the internal nodes that have no corresponding keyed item at the leaf level. This tree reflects that, for example, "Entropic Armor" is an internal node key, but there is no item with the key "Entropic Armor" at the leaf level. This normal and does not alter the deletion algorithm in any way. Just work with the keys that are there.

Answer rating: 100% (QA)

Inserting Potion of Growth 300 We start by searching for the insertion point which is the leaf node that contains the largest key less than 300 In this case that node is Blue loun Stone 250 We then co... View the full answer