February 25, 2021
Hot Topics:

Java Ordered Collections: Trees and Skip Lists

  • By Mark Grand
  • Send Email »
  • More Articles »

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

Page 2 of 4

This article was originally published on January 9, 2009

Enterprise Development Update

Don't miss an article. Subscribe to our newsletter below.

Thanks for your registration, follow us on our social networks to keep up-to-date