Java Ordered Collections: Trees and Skip Lists, Page 2
Using this first rule, the tree shown in Figure 1 could have been created by adding values to an empty TreeSet in this order: 5, 8, 6, 2, 4, 1, 9, 3, 7. Figure 2 shows the organization of the binary tree after each value is added.
Figure 2: Tree Structure After Adding Each of 5, 8, 6, 2, 4, 1, 9, 3, 7
Using just the one rule worked well when the values are added (or removed from) the tree in an arbitrary order. To find something in this tree requires at most four comparisons. For example, to find 3 in this tree, the TreeSet would look at the four nodes shown in red in Figure 3.
Figure 3: Nodes looked At When Searching for 3
The tree produced using just the one rule is not as fast to search when values are added to the tree in sorted order. For example, adding the same values to the TreeSet in the order 1, 2, 3, 4, 5, 6, 7, 8, 9 produces a binary tree that is internally organized, as shown in Figure 4.
Figure 4: Adding Values in Ascending Order