Question

The first and second picture are the definition of 2-3 tree，3rd and 4th are the pre-condition and post-condition. Please use these question to solve problem 8，the last photo.

2-3 Trees: Definition Suppose that E is an ordered type, that is, a nonempty set of values that have a total order. A 2-3-tree, for type E, is a finite rooted tree T (like a binary search tree or a red-black tree) that satisfies the following 2-3 Tree Properties: (a) Every leaf in T stores an element of E. and the elements stored at the leaves of T are distinct. Thus T represents a finite subset of E, namely, the set of values stored in the leaves of T. (b) Every internal node of T has (exactly) either two or three children-which are each either leaves or internal nodes of T (c) If an internal node x has exactly two children - a first child, which is the root of a first subtree of the subtree with root x, and a second child, which is the root of a second subtree of the subtree with root x -then each of the values stored at the leaves of the first subtree is less than each of the values stored at the leaves of the second subtree. (d) If an internal node x has exactly three children- a first child, second child and third child, which are the roots of the first subtree, second subtree and third subtree of the subtree with root x, respectively - then each of the values stored at the leaves of the first subtree is less than each of the values stored at the leaves of the second subtree, and 1

Answer 1

Insertion into 2-3 Tree:

a) T is an empty tree,so that it's root is a null node.

simplified algorithm

Suppose we are to insert 2 values (5,6) into the empty tree

1. Initially create a node which will also serve as the root node for this case

2. Insert the first value into this node

3. to insert the next value

if (this.value > prev.value)   //check if the next value to be inserted is greater than the previous value in root node

then insert to the right of the prev.value

else

then insert to the left of the prev.value

4.continue with normal insertion algorithm (if) for more elements.

STEP 1 STEP 2 5 STEP 3 6 LO LO

In this situation the only root node is also leaf node

b) T is not empty, but the set it represents has size one (so that it's root is a leaf)

simplified algorithm

Suppose the root node already contains the element 5 and now the insertion data is (6,7)

1.to insert the first value

if (this.value > prev.value)  

then insert to the right of the prev.value

else

then insert to the left of the prev.value

2.to insert the next value

   //here prev.value is the last item that has been inserted

if (this.value > prev.value)

then insert to the right of the prev.value

else

then insert to the left of the prev.value

3.if (length(node) >= 3)    //such that the node now has more than two elements

1. create a new node,push up and set it as root node

2.insert middle.value of the leaf node into the root node.   //the median value is pushed up

4.continue with normal insertion algorithm (if) for more elements.

STEP 1 7 STEP 2 5 7 6 STEP 3 5 7 5 LO LC LC

I hope my answers satisfy your requirements. I have made the algorithm simplified,case specific and not added additional functions such a checking if the value has occurred before,and if yes then to return a ElementFoundException.

If you have any questions leave them in the comments. If you are satisfied with the answer please leave a thumbs up, it really matters.

Thank You.