伸展树

[RubyLouvre]

    class Node {
      constructor(data) {
        this.size = 0
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
        this.count = 1
      }
      maintain() {
        var leftSize = this.left ? this.left.size : 0
        var rightSize = this.right ? this.right.size : 0
        this.size = leftSize + rightSize + this.count;
      }

    };

    function rotateImpl(tree, node, dir, setParent) {
      var other = dir == 'left' ? 'right' : 'left';
      if (!node[other]) {
        return;
      }
      var top = node[other];//会上浮的子节点
      node[other] = top[dir]; //过继孩子

      if (setParent) {
        if (!node.parent) {
          tree.root = top;
        } else if (node == node.parent.left) {
          node.parent.left = top;
        } else {
          node.parent.right = top;
        }
        Object(top[dir]).parent = node; //父属性修正1
        top.parent = node.parent; //父属性修正2
        node.parent = top; //父属性修正3
      }
      top[dir] = node; //旋转
      node.maintain();//先处理下面的再处理上面的
      top.maintain();
      return top;
    }
    class SplayTree {
      constructor() {
        this.root = null;
      }
      leftRotate(node) {
        return rotateImpl(this, node, 'left', true);
      }
      rightRotate(node) {
        return rotateImpl(this, node, 'right', true);
      }

      splay(node, goal) {
        goal = goal || this.root
        while (node !== goal) {
          if (node == this.root) {
            break
          }
          var parent = node.parent;
          if (parent == goal) {
            if (parent.left == node) {
              // console.log("zig")
              this.rightRotate(parent)
            } else {
              // console.log("zag")
              this.leftRotate(parent)
            }
            break
          } else {
            var grandpa = parent.parent;
            var case1 = grandpa.left === parent ? "zig-" : "zag-";
            var case2 = parent.left === node ? "zig" : "zag";
            switch (case1 + case2) {
              case "zig-zig": // 一字型，先父后子，由于我们的旋转操作都是针对于根，
                // 那么操作node，即操作parent
                this.rightRotate(grandpa);
                this.rightRotate(parent);
                continue
              case "zag-zag": // 一字型，先父后子
                this.leftRotate(grandpa);
                this.leftRotate(parent);
                continue
              case "zig-zag": // 之字型
                this.leftRotate(parent);
                this.rightRotate(grandpa);
                continue;
              case "zag-zig": // 之字型
                this.rightRotate(parent);
                this.leftRotate(grandpa);
                continue;
            }
          }
        }
        node.maintain() //更新节点的数量
      }

      getSize(node) {
        return node ? node.size : 0
      }
      find(data) {
        var node = this.root;
        while (node) {
          var diff = data - node.data
          if (diff == 0) {
            break
          } else if (diff < 0) {
            node = node.left;
          } else {
            node = node.right;
          }
        }
        if (node) {
          this.splay(node)
          return node
        }
        return null
      }
      insert(data) {
        if (!this.root) {
          this.root = new Node(data);
          getOrder(this)
          return true
        }

        var node = this.root,
          parent = null
        while (node) {
          parent = node; //保存要插入的父节点
          var diff = data - node.data
          if (diff == 0) {
            node.count++
            return false
          } else if (diff < 0) {
            node = node.left;
          } else {
            node = node.right;
          }
        }
        var node = new Node(data);
        node.parent = parent;
        if (diff < 0) {
          parent.left = node
        } else {
          parent.right = node
        }
        this.splay(node)
        getOrder(this)
        return true;
      }
      inOrder(cb) {
        function recursion(node) {
          if (node) {
            recursion(node.left)
            cb(node)
            recursion(node.right)
          }
        }
        recursion(this.root)
      }
      remove(data) {
        if (!this.root) {
          return false
        }
        var node = this.find(data); //如果找到，内部会进行伸展
        if (node) {
          if (node.count > 1) {
            node.count--;
            return true;
          }
          if (data == this.root.data) {
            if (!node.left) {
              this.root = node.right;
              this.root.parent = null;
            } else if (!node.right) {
              this.root = node.left;
              this.root.parent = null;
            } else {
              var succ = this.maxNode(node.left);
              this.splay(succ);
              succ.parent = null;
              succ.right = node.right;
              succ.right.parent = succ;
            }
          }
        }
      }
      /**
       * 与伸展树tree2合并。其中tree1的所有元素都小于tree2的所有元素。
       * 首先，找到伸展树tree1中的最大元素x，再通过Splay(x,tree1)将x调整为tree1的根。
       * 然后将tree2作为x节点的右子树。这样，就得到了新伸展树tree。
       */
      join(tree1, tree2) {
        if (!tree1) {
          return tree2
        }
        if (!tree2) {
          return tree1
        }
        var x = this.maxNode(tree1)
        this.splay(max, tree1);
        x.right = tree2
        tree2.parent = x;
        return x;
      }
      getRank(value) {
        var node = this.find(value);
        if (node) {
          console.log(node.left.size)
          return this.getSize(node.left) + 1
        } else {
          return 0
        }
      }
      getKth(k) {
        var node = this.root
        while (node) {
          if (k <= this.getSize(node.left)) {
            node = node.left
          } else if (k > this.getSize(node.left) + node.count) {
            k -= (this.getSize(node.left) + node.count)
            node = node.right
          } else {
            return node.data
          }
        }
        return null
      }
      maxNode(node) {
        var current = node || this.root;
        while (current.right) {
          current = node.right
        }
        return current;
      }
      toString(printNode) {
        if (printNode === void 0) printNode = function (n) {
          return n.data;
        };

        var out = [];
        printRow(this.root, '', true, function (v) {
          return out.push(v);
        }, printNode);
        return out.join('');
      };
    }

    // https://github.com/w8r/splay-tree/blob/master/dist/splay.js
    function printRow(root, prefix, isTail, out, printNode) {
      if (root) {
        out(("" + prefix + (isTail ? '└── ' : '├── ') + (printNode(root)) + "\n"));
        var indent = prefix + (isTail ? '    ' : '│   ');
        if (root.left) {
          printRow(root.left, indent, false, out, printNode);
        }
        if (root.right) {
          printRow(root.right, indent, true, out, printNode);
        }
      }
    }
    var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 1, 2]  //[11,7,14,3,9,18,16,15]
    var t = new SplayTree();
    array.forEach(function (el) {
      t.insert(el)
    })

    function getOrder(t) {
      var array = [], last = -Infinity, error
      t.inOrder(function (node) {
        if (last > node.data) {
          error = true
        }
        array.push(node.data)
        last = node.data
      })
      console.log(array + '')
      if (error) {
        // console.log(t.root)
        // throw t
      }
    }
    var rank = t.find(44)
    console.log('t.find(44)', rank, t)
    var a = t.getRank(44)
    console.log('t.getRank(44)', a);
    var b = t.getKth(a)
    console.log(`t.getKth(${a})`, b);

https://github.com/w8r/splay-tree/blob/master/dist/splay.js

[RubyLouvre]

https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91

[RubyLouvre]

能解决移除BUG的版本

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.size = 1;
    this.count = 1;
  }
  maintain() {
    this.size = this.count;
    if (this.left) {
      this.size += this.left.size;
    }
    if (this.right) {
      this.size += this.right.size;
    }
  }
}

function rotateImpl(tree, node, dir, setParent) {
  var other = dir == "left" ? "right" : "left";
  if (!node[other]) {
    return;
  }
  var top = node[other]; //会上浮的子节点
  node[other] = top[dir]; //过继孩子

  if (setParent) {
    if (!node.parent) {
      tree.root = top;
    } else if (node == node.parent.left) {
      node.parent.left = top;
    } else {
      node.parent.right = top;
    }
    Object(top[dir]).parent = node; //父属性修正1
    top.parent = node.parent; //父属性修正2
    node.parent = top; //父属性修正3
  }
  top[dir] = node; //旋转
  node.maintain(); //先处理下面的再处理上面的
  top.maintain();
  return top;
}
class SplayTree {
  //参考 https://github.com/sisobus/SplayTree/blob/master/index.js
  constructor() {
    this.root = null;
  }
  leftRotate(node) {
    return rotateImpl(this, node, "left", true);
  }
  rightRotate(node) {
    return rotateImpl(this, node, "right", true);
  }
  rotate(x) {//rotate具有决定左旋或右旋的功能
    let p = x.parent;
    if (x === p.left) {
      return this.rightRotate(p);
    } else {
      return this.leftRotate(p);
    }
  }
  splay(node, goal) {
    if (node == goal) return;
    while (node.parent != goal) {
      var p = node.parent;
      if (p.parent == goal) {//如果祖先不存在
        this.rotate(node);//等价于rotate(tree,tree->fa->son[1]==tree^1)
        break;
      }
      var grandpa = p.parent;
      this.rotate(
        (node === p.left) === (p === grandpa.left) ? p : node
      );
      this.rotate(node);
    }
  }
  remove2(data) {
    var node = this.find(data)
    if (!node) {
      return false
    }
    if (node.count > 1) {
      node.count--
      return true;
    }
    this.splay(node)
    var left = node.left, right = node.right;
    if (left != null) {
      left.parent = null;
    }
    if (right != null) {
      right.parent = null;
    }
    if (left == null) {
      return right;
    }
    if (right == null) {
      return left;
    }
    this.root = null;
    return this.root = this.merge(left, right)
  }
  getSize(node) {
    return node ? node.size : 0;
  }

  split(value) {
    var trees = []
    var data = this.approximate(this.root, value);
    var tree1 = new SplayTree();
    var tree2 = new SplayTree();
    if (data == null) {
      return trees
    }
    console.log(data)
    var node = this.find(data);
    this.splay(node);
    var root = this.root
    tree1.root = root;
    tree2.root = root.right;
    if (root.right != null) {
      root.right.parent = null;
    }
    root.right = null;
    trees.push(tree1, tree2)

    return trees;
  }
  insert(data) {
    if (!this.root) {
      this.root = new Node(data);
      console.log(this.keys() + "");
      return true;
    }

    var node = this.root,
      parent = null;
    while (node) {
      parent = node; //保存要插入的父节点
      var diff = data - node.data;
      if (diff == 0) {
        node.count++;
        return false;
      } else if (diff < 0) {
        node = node.left;
      } else {
        node = node.right;
      }
    }
    var node = new Node(data);
    node.parent = parent;
    if (diff < 0) {
      parent.left = node;
    } else {
      parent.right = node;
    }
    this.splay(node);
    console.log(this.keys() + "");
    return true;
  }

  getMin() {
    var node = this.root
    if (node) {
      while (node.left)
        node = node.left

      return this.splay(node);
    }
    return null;
  }
  maxNode(node) {
    var cur = node || this.root;
    while (cur.right) {
      cur = cur.right
    }
    return cur;
  }
  minNode(node) {
    var cur = node || this.root;
    while (cur.left) {
      cur = cur.left
    }
    return cur;
  }
  getMax() {
    var node = this.maxNode()
    return node ? node.data : null
  }
  getMin() {
    var node = this.minNode()
    return node ? node.data : null
  }
  getPrev(value) {
    var node = this.find(value)
  }

  find(value) {
    var node = this.root;
    while (node) {
      var diff = value - node.data;
      if (diff == 0) {
        break;
      } else if (diff < 0) {
        node = node.left;
      } else {
        node = node.right;
      }
    }
    if (node) {
      this.splay(node);
      return node;
    }
    return null;
  }
  getRank(value) {
    var node = this.find(value);
    if (node) {
      return this.getSize(node.left) + 1;
    } else {
      return 0;
    }
  }
  getKth(k) {
    var node = this.root;
    while (node) {
      if (k <= this.getSize(node.left)) {
        node = node.left;
      } else if (k > this.getSize(node.left) + node.count) {
        k -= this.getSize(node.left) + node.count;
        node = node.right;
      } else {
        return node.data;
      }
    }
    return null;
  }
  getPrev(value) {//找x的前驱{
    var node = this.find(value)
    if (node) {
      this.splay(node);
      var right = node.right;
      while (right.left) {
        right = right.left
      }
      return right
    }
  }
  getSuss(value) {//找x的后继
    var node = this.find(value)
    if (node) {
      this.splay(node);
      var left = node.left;
      while (left.right) {
        left = left.right
      }
      return left
    }
  }
  merge(first, second) {
    if (!first) {
      return second
    }
    if (!second) {
      return first
    }
    if (first.data > second.data) {
      var a = first;
      first = second;
      second = first;
    }
    var max = this.maxNode(first)
    this.splay(max);
    max.right = second
    second.parent = max;
    return max;
  }
  approximate(node, value) { //小于或等于value
    if (!node) {
      return null
    }
    while (node.data != value) {
      if (value < node.data) {
        if (!node.left) break;
        node = node.left;
      }
      else {
        if (!node.right) break;
        node = node.right;
      }
    }
    return node.data
  }
  remove(value) {
    let p = this.find(value);
    if (!p) {
      return false;
    } else {
      if (p.count > 1) {
        p.count--;
        return true;
      }
    }
    if (p.left) {
      //新根有左右孩子
      if (p.right) {
        this.root = p.left;
        this.root.parent = null;
        let x = this.root;
        while (x.right) x = x.right;//取得它的后继节点
        x.right = p.right;
        p.right.parent = x;
        return true;
      }
      //新根只有左孩子
      this.root = p.left;
      this.root.parent = null;
      return true;
    }
    if (p.right) {
      //新根只有右孩子
      this.root = p.right;
      this.root.parent = null;
      return true;
    }
    this.root = null; //新根节点没有孩子
    return true;
  }
  removeRange(start, end) {
    if (start >= end) {
      throw 'start必须小于end'
    }
    var a = this.getKth(start - 1);
    var b = this.getKth(end + 1);
    a = this.find(a)
    b = this.find(b)
    if (!a && !b) {
      return
    }
    if (!a) {
      this.splay(b);
      b.left = null;
      b.maintain()
      return
    }
    if (!b) {
      this.splay(a);
      a.right = null;
      a.maintain()
      return
    }
    this.splay(a)
    this.splay(b, a)
    b.left = null
    b.maintain()
  }
  inOrder(cb) {
    function recursion(node) {
      if (node) {
        recursion(node.left);
        cb(node);
        recursion(node.right);
      }
    }
    recursion(this.root);
  }
  keys() {
    var ret = [];
    this.inOrder(function (p) {
      ret.push(p.data);
    });
    return ret;
  }
}
var array = [7, 11, 13, 8, 44, 78, 15, 9, 77, 89, 1, 2]  //[11,7,14,3,9,18,16,15]
var t = new SplayTree();
array.forEach(function (el) {
  t.insert(el)
})

function getOrder(t) {
  var array = [], last = -Infinity, error
  t.inOrder(function (node) {
    if (last > node.data) {
      error = true
    }
    array.push(node.data)
    last = node.data
  })
  console.log(array + '')
  if (error) {
    // console.log(t.root)
    // throw t
  }
}
var rank = t.find(44)
console.log('t.find(44)', rank, t)
var a = t.getRank(44)
console.log('t.getRank(44)', a);
var b = t.getKth(a)
console.log(`t.getKth(${a})`, b);

t.remove(11);
t.remove(44);
t.remove(77);
console.log("移除11,44,77后");
console.log(t.keys(1) + "");
t.insert(11)
t.insert(43)
t.insert(76)
t.insert(77)

t.removeRange(4, 8)
console.log(t.keys(1) + "");
console.log(t.split(44));

[RubyLouvre]

伸展操作的简化过程

https://blog.csdn.net/u012061345/article/details/25277363