Method splay_

deps/v8/tools/splaytree.mjs:203–252

* Perform the splay operation for the given key. Moves the node with * the given key to the top of the tree. If no node has the given * key, the last node on the search path is moved to the top of the * tree. This is the simplified top-down splaying algorithm from: * "Self-adjusting Bin

(key)

   * @private
   */
  splay_(key) {
    if (this.isEmpty()) return;
    // Create a dummy node.  The use of the dummy node is a bit
    // counter-intuitive: The right child of the dummy node will hold
    // the L tree of the algorithm.  The left child of the dummy node
    // will hold the R tree of the algorithm.  Using a dummy node, left
    // and right will always be nodes and we avoid special cases.
    let dummy, left, right;
    dummy = left = right = new SplayTreeNode(null, null);
    let current = this.root_;
    while (true) {
      if (key < current.key) {
        if (current.left === null) break;
        if (key < current.left.key) {
          // Rotate right.
          const tmp = current.left;
          current.left = tmp.right;
          tmp.right = current;
          current = tmp;
          if (current.left === null) break;
        }
        // Link right.
        right.left = current;
        right = current;
        current = current.left;
      } else if (key > current.key) {
        if (current.right === null) break;
        if (key > current.right.key) {
          // Rotate left.
          const tmp = current.right;
          current.right = tmp.left;
          tmp.left = current;
          current = tmp;
          if (current.right === null) break;
        }
        // Link left.
        left.right = current;
        left = current;
        current = current.right;
      } else {
        break;
      }
    }
    // Assemble.
    left.right = current.left;
    right.left = current.right;
    current.left = dummy.right;
    current.right = dummy.left;
    this.root_ = current;
  }

  /**
   * Performs a preorder traversal of the tree.