dcsimg
October 21, 2018
Hot Topics:

Java Ordered Collections: Trees and Skip Lists

  • January 9, 2009
  • 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



Comment and Contribute

 


(Maximum characters: 1200). You have characters left.

 

 


Enterprise Development Update

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

By submitting your information, you agree that developer.com may send you developer offers via email, phone and text message, as well as email offers about other products and services that developer believes may be of interest to you. developer will process your information in accordance with the Quinstreet Privacy Policy.

Sitemap

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