wem (32) [Avatar] Offline
#1
Insertion into a tree is described as:
1. Compare the element to be inserted with the root. If they’re equal, you’re done.
There’s nothing to insert because you can only insert an element lower or higher
than the root. Note, however, that the reality will sometimes be different. If the
objects inserted into the tree may be equal from the tree-ordering point of view but
different based on other criteria, you’ll probably want to replace the root with the
element you’re inserting. This will be the most frequent case, as you’ll see.
2. If the element to be inserted is lower than the root, insert it recursively into the left
branch.
3. If the element to be inserted is higher than the root, insert it recursively into the
right branch.
But case 2 will only result in a recursive call if the current node has a left branch (and similarly for case 3).
Pierre-Yves Saumont (182) [Avatar] Offline
#2
Not sure what you mean. If the branch is an empty tree, the inserted value will be inserted into that empty tree. Do you mean that this insertion is not recursive since the tree is empty? No recursion will be involved in this specific case, but it is still a recursive process. Or do you mean that I did not represent the right and left empty branches and failed to make it clear that they are actual empty trees? A tree with a single value has a right and left branches that are (empty) trees. If this is what you mean, I would maybe rather add explicit insertion into an empty tree, such as:


  • - If the tree is empty, just create a new tree with the element as the root and two empty trees as the left an right branches.

    - Compare the element to be inserted with the root. If they’re equal, you’re done...

    - If the element to be inserted is lower than the root, insert it recursively into the left branch.

    - If the element to be inserted is higher than the root, insert it recursively into the right branch.


  • Does this answer your question?
    wem (32) [Avatar] Offline
    #3
    When I saw the diagram in figure 10.3 (and 10.4) I saw that some of the nodes were labelled as leaf nodes. I assumed that leaf nodes by definition have no children i.e. no left or right branches. But, if I understand you correctly, these 'leaf' nodes actually have empty trees as their left and right branches. Is that right?
    Pierre-Yves Saumont (182) [Avatar] Offline
    #4
    Figure 10.3 represents a different kind of tree ("leafy tree") where the leaves (the values) are terminal. Note that in this kind of tree, nodes do not contain values.

    In the "regular" kind of tree, there are no leaves, only trees. A tree is composed of a value and two branches, which are also trees (subtrees). The terminal elements are empty trees. By convention, they are not represented on the diagrams, so that the nodes having only empty subtrees appear as if they were leaves, but in fact, they are trees with empty branches.