• Searches for an element in the splay tree and splays it to the root

    This is the main search operation for splay trees. It combines traditional binary search tree lookup with the splay operation that moves the accessed node (or the last accessed node if target not found) to the root.

    The key insight is that in splay trees, every access operation (including search) triggers a splay, which provides the self-adjusting behavior that gives splay trees their excellent amortized performance for sequences with locality of reference.

    Parameters

    • target: any

      the value to search for

    • tree: SplayTree<any>

      the tree to search in

    Returns {
        found: boolean;
        tree: SplayTree<any>;
    }

    result containing:

    • found: true if target was found, false otherwise
    • tree: the tree after splaying (target at root if found, or closest node if not found)