A Practical Guide to Data Structures and Algorithms using Java

536 A Practical Guide to Data Structures and Algorithms Using Java

}

if (node ! = root) //if not found splay last node reached

splay(node.parent, null); //(unless it’s already the root)

return false;

}

Figure 35.3 illustrates a call to contains for two elements in the collection, and then for an element

not in the collection. First contains is called for “b.” After using the standard binary search tree

search method to locate “b,” the splay method is used to bring “b” to the root. First case 3 is

applied, followed by case 2. Observe that the two occurrences of “a” maintain their same relative

positions in the iteration order. Next the contains method is called for “o” which results in applying

case 2, followed by case 1. Finally, an unsuccessful search ...