advanced data structures and implementation in this we discuss six data structures with an emphasis on practicality we begin by examining alternatives to the avl tree discussed in these include an optimized version of the splay treethe red-black treeand the treap we also examine the suffix treewhich allows searching for pattern in large text we then examine data structure that can be used for multidimensional data in this caseeach item may have several keys the - tree allows searching relative to any key finallywe examine the pairing heapwhich seems to be the most practical alternative to the fibonacci heap recurring themes include nonrecursivetop-down (instead of bottom-upsearch tree implementations when appropriate implementations that make use ofamong other thingssentinel nodes top-down splay trees in we discussed the basic splay tree operation when an itemxis inserted as leafa series of tree rotationsknown as splaymakes the new root of the tree splay is also performed during searchesand if an item is not founda splay is performed on the last node on the access path in we showed that the amortized cost of splay tree operation is (log na direct implementation of this strategy requires traversal from the root down the treeand then bottom-up traversal to implement the splaying step this can be done either by maintaining parent linksor by storing the access path on stack unfortunatelyboth methods require substantial amount of overheadand both must handle many special cases in this sectionwe show how to perform rotations on the initial access path the result is procedure that is faster in practiceuses only ( extra spacebut retains the (log namortized time bound figure shows the rotations for the zigzig-zigand zig-zag cases (as is customarythree symmetric rotations are omitted at any point in the accesswe have current node