Last modified 27 June 2003 by jdavis@math.wisc.edu
Inherits from SMKBinaryTree : NSObject
Conforms to NSCoding, NSCopying
SMKSplayTree implements a splay tree, which is a balanced binary search tree similar to an AVL or red-black tree. In a binary search tree, each node has a unique numeric key, and the keys conform to this search condition: at each node, the key is greater than all of the keys in the left subtree and less than all of the keys in the right subtree. In order to maintain efficiency, the splay tree uses balancing operations. In particular, whenever a node is accessed, it is lifted to the root of the tree. This balancing lets a splay tree with n nodes perform any initial sequence of m operations in time O(m log n). That is, its amortized time complexity is O(log n).
In practice, such balancing can be very time-consuming. For this reason, SMKSplayTree also implements standard binary search tree operations (named with the prefix "quickly"), which you can mix with the splay tree operations as you desire. For example, you might want to use the "quickly" variants for most accesses, and then use occasional splay tree accesses to restore some balance to the tree. (But note well: If you use only the "quickly" variants, then the tree can eventually become so unbalanced that the "quickly" variants operate more slowly than the splaying variants. That's the point of splaying.)
Each node in the splay tree stores a key and a pointer to a "resource object". The only peculiarity here is that the node does not retain the resource object; it just stores a copy of its address. That is, the splay tree implements a mapping from integers to pointers.
- (id)setKey:(int)key resource:(id)resource;Sets the node's key and resource pointer, without retaining the resource.
Returns the node's key.
Returns the node's resource pointer.
The splay tree interface comprises the following three methods, which insert, find, and remove nodes. All three methods splay through the tree, lifting the desired node up to the root. Since the root of the tree changes, you must update your reference to the tree to point to the new root. To do this, you will typically want to autorelease the tree, perform a splaying operation, and then retain the result. For example, to find key 37 in the tree myTree, you do
myTree = [[[myTree autorelease] findKey:37] retain];
or, if you prefer to avoid autoreleasing,
id oldTree = myTree;
myTree = [[myTree findKey:37] retain];
[oldTree release];
Here are the three splaying methods.
- (id)insertNode:(SMKSplayTree *)node;If the node's key is not already in the tree, inserts the node at the root and returns the reconfigured tree. (If the node's key is already in the tree, then the new node is not inserted; the old one with that key is lifted to the root.) In fact, the new node can be the root of a multi-node tree, and the entire tree will be inserted; however, this must be done carefully, so that the search condition is not violated. Typically only single nodes are inserted.
Lifts the node with the key (if it exists) to the root and returns the reconfigured tree.
Removes the node with the key (if it exists) and returns a reconfigured tree.
It is recommended that you use the splaying methods by default. However, for those times when you want fast tree access without complicated reconfigurations, the following standard binary search tree operations are also available.
- (id)quicklyInsertNode:(SMKSplayTree *)node;If the node's key is not already in the tree, inserts the node and returns the receiver. (If the node's key is already in the tree, then the new node is not inserted, and the receiver is returned.) In fact, the new node can be the root of a multi-node tree, and the entire tree will be inserted; however, this must be done carefully, so that the search condition is not violated. Typically only single nodes are inserted.
- (id)quicklyFindKey:(int)key;
Returns the node with the key, or nil if it does not exist.
- (id)quicklyFindParentOfKey:(int)key;
Returns the parent of the node with the key; if the key is not in the tree, or if it is at the root node, then nil is returned. This method is useful in altering the tree structure around the key node.
- (id)quicklyRemoveKey:(int)key;
Removes the node with the key (if it exists) and returns the reconfigured tree (which is the receiver, unless the key was at the receiver's root node). You should autorelease the tree before invoking this method, and then retain the result.