16. Insertion in a Search Tree

So, now let us see how to insert a value, inserting a value in a search tree fairly straightforward; there is only one place because remember that the tree is listed in order will give us a sorted list.

Inserting a value into a search tree is straightforward because there is a defined order. The values in a search tree are arranged in such a way that for any given node, all values in the left subtree are smaller, and all values in the right subtree are larger. This means that when we need to insert a new value, we simply need to find the correct position within this ordered structure. Once located, we can insert the new value and maintain the order.

Think of inserting a book in a library. If you are adding a book to an already organized shelf (like a search tree), you first find out where that book fits alphabetically. You wouldn't just put it anywhere; you’d find its exact spot to keep the order intact.

So, is like insertion in a sorted list, except we have to find that correct place in the tree to hang it. So, when we do this in order traversal, it would be in the correct order when we list it out.

Insertion involves traversing the tree, starting from the root. We compare the value to insert with the current node's value, moving left if the new value is smaller or right if it is larger. This process continues recursively until we find a node where there is no child in the direction we are supposed to go, which indicates the position for the new value.

Imagine you're looking for a parking spot in a parking lot that sorts cars by size. If you're driving a compact car, you check the smaller slots first. You keep moving until you find a spot that's open. Similarly, in the tree, you keep moving left or right until you spot the correct spot for insertion.

For instance, if you want to insert 21, we will walk down the tree and look for the place where we should find 21. If it is smaller than 52 we go left, smaller than 37 we go left, bigger than 16 we go right, and then find that at 28 there's no value of 21, so since it should be to the left of 28, we add it there.

When inserting a specific value like 21, you start from the root (52) and determine that 21 is less, so you move left to 37. From there, since 21 is still less, you go left again to 16, and finally, since 21 is greater than 16, you move right. You find an empty position to the left of the node containing 28, making it the perfect spot to place 21.

Consider a scenario where you're deciding where to place a new item in a categorized display case. You start at the top category and check where the item fits best based on its attributes, just like comparing values in the tree. Each step leads you closer to the right placement until you find the perfect spot to add your item.

Now, if we try to insert a value that is already there, for instance, if we try to insert 91, we look for 91 and find it, so we do nothing and do not create duplicates.

When attempting to insert a value that already exists in the tree, the algorithm searches for the value. If the value is found, it simply does not proceed with the insertion. This is important because maintaining unique values is critical in search trees to ensure the integrity of the data structure and improve search efficiency.

It’s like trying to add a name to a guest list that already has that name. You wouldn’t add it again to keep the list unique; instead, you confirm the name already exists and move on.

This is a simple recursive way to do this; if the tree is empty, we create a new node. If we cannot go left and find the place to insert, we create a new node to the left, making that node point to its parent.

The recursive insertion method simplifies the process of adding new values. If the tree is empty, a new node is created directly. If there's an appropriate spot for the new value, the algorithm constructs a new node either to the left or right depending on the comparisons made during traversal, linking the new node back to its parent for structural integrity.

Think of this process like building a family tree. If you have no children, you simply add a child. If you need to add more children under a specific parent, you link each new child to the correct parent as you go, ensuring that the family tree stays organized.

--