Question

Q1: How many levels your binary search tree has (including level 0)? Is the binary search tree you created height balanced?

2.1 Click the animations “Binary Search Tree”. Click “Insert” button to insert
the following elements in the sequence, “50, 20, 30, 70, 90, 80, 40, 10, 5, 60,
85, 95”.

http://algoanim.ide.sk/index.php?page=showanim&id=44

Q2: What is the insertion process of the binary search tree? The new identical element is inserted as left or right child of the existing same value?

2.3 Fill another identical 65 in the blank of Insert, and click Insert to insert this
element.

Q3: What is the find process of the binary tree? If we have the multiple appearance of an element, such as 52, can both be found?

2.4 Fill 60 in the blank on the left of Find button, and click Find to search this
element, we have Figure 4 after it is found. Try again using some element is
not in the tree, such as 52 in my case.

Q4: What is traverse process and what is the visiting result? What order it is, prefix (Middle->Left->Right), postfix (Left->Right->Middle), or infix (Left->Middle->Right)?

2.5 Click print button to observe the traverse process.

Q5: What is delete process? Which element is selected to replace in the position of 70?

2.6 Click Del to delete 70, we will have Figure 5

      Q6: List all the major changes (such as color change, rotations) happening during the insertion process for each value?

3.1 Click the animations “Red/Black Tree”. Click “Insert” button to insert the
following elements in the sequence, “10, 20, 30, 40, 50, 60, 70, 80, 90”. The
created figure is Figure 6.

http://algoanim.ide.sk/index.php?page=showanim&id=63

Q7 : What is the find process of the red/black tree?

3.2 Fill 60 in the blank on the left of Find button, and click Find to search this
element

Answer 1

Q1.

This is the tree obtained on inserting the given elements:

0050 0070 0020 0080 0090 0010 0030 0040 0005 0080 0095 0085

The number of levels in the above binary search tree is 5.

No, the above tree is not height-balanced. Its current height is 4, which can be reduced to 3.

Q2.

When inserting a new value 60 in the above tree, the resultant tree is:

0050 0020 0070 0090 0010 0060 0030 0080 0095 0005 0040 0060 0085

Hence, we can see that the new 60 is inserted to the right of the old 60.

Thus, the new identical element is inserted as the right child of the existing same value.

Q3.

When finding the element 60, only its first occurrence is being found. The further occurrences of the same element are ignored.

0050 0020 0070 0010 0030 0060 0090 0060 0080 0095 0005 0040 0085

Thus, if we have multiple appearances of an element, only the first occurrence can be found.

Q4.

The traverse order is infix (Left->Middle->Right) as can be seen by the following order:

0060 0080 0005 0010 0020 0030 0040 0050 0060 0070 0085 0090 0095

Q5.

On deleting the element 70, the tree looks like;

0050 0020 0060 0010 0030 0080 0090 0005 0040 0080 0095 0085

The element 60 is selected to replace in the position of 70. This means that the rightmost element (i.e., the largest element) in the left subtree of the element to be deleted is selected to replace the element. This is the delete process.

Q6.

Below are the screenshots of the tree every time a new element is inserted.

0010

0010 0020

0020 0010 0030

0020 0010 0030 0040

0020 0010 0040 0030 0050

0020 0010 0040 0030 0050 0080

0020 0010 0040 0060 0030 0050 0070

0020 0010 0040 0030 0060 0050 0070 0080

0040 0020 0060 0010 0030 0050 0080 0070 0090

This shows all the major changes (such as color change, rotations) happening during the insertion process for each value.

Q7.

The following picture shows the element 60 being searched in the red-black tree.

0040 0020 0080 0010 0030 0050 0080 0070 0090

The find process is the same as the traditional Binary Search tree. Firstly, the root element is matched with the element to be searched for. If the root element is bigger than the searching element, then the search continues for the left subtree of the current node. If it is smaller than or equal to the searching element, the search continues for the right subtree. If it is equal, we have found the element.

For example, in this case, firstly, 60 is compared with 40. Since 40<=60, the search continues for the right subtree. Now, the root element of the right subtree is 60. It is compared with the element to be searched for, which is also 60. Since both the elements are the same, this is our result.

Hope it helped. If you have any doubts or queries, please feel free to ask in the comments section. If it helped in any way, please consider giving positive ratings.