Java Treap Example

说明

java treap示例是从最受好评的开源项目中提取的实现代码,你可以参考下面示例的使用方式。

编程语言: Java

类/类型: Treap

示例#1
文件: Treap.java项目: rabodaber/papers

 protected void toString(StringBuilder sb) {
   sb.append("[" + x.toString() + "]; ");
   if (left != null) {
     left.toString(sb);
   }
   if (right != null) {
     right.toString(sb);
   }
 }

示例#2
文件: TreapDelete.java项目: katarinka/alg-vis

 public TreapDelete(Treap T, int x) {
   super(T);
   this.T = T;
   T.setV(v = new TreapNode(T, K = x));
   v.setColor(NodeColor.DELETE);
   setHeader("deletion");
 }

示例#3
文件: Treap.java项目: rabodaber/papers

  public Treaps splitY(Int2DIndividual x) {
    Treaps res = new Treaps();
    Treaps t = null;

    if (this.x.compareX2(x) >= 0) {
      if (right == null) {
        res.r = null;
      } else {
        t = right.splitY(x);
        res.r = t.r;
      }
      res.l = new Treap(this.x, y, left, t == null ? null : t.l);
    } else {
      if (left == null) {
        res.l = null;
      } else {
        t = left.splitY(x);
        res.l = t.l;
      }
      res.r = new Treap(this.x, y, t == null ? null : t.r, right);
    }
    return res;
  }

示例#4
文件: TreapDelete.java项目: katarinka/alg-vis

  @Override
  public void run() {
    if (T.getRoot() == null) {
      v.goToRoot();
      addStep("empty");
      mysuspend();
      v.goDown();
      v.setColor(NodeColor.NOTFOUND);
      addStep("notfound");
      return;
    } else {
      TreapNode d = (TreapNode) T.getRoot();
      v.goTo(d);
      addStep("bstdeletestart");
      mysuspend();

      while (true) {
        if (d.key == K) { // found
          v.setColor(NodeColor.FOUND);
          break;
        } else if (d.key < K) { // right
          addStep("bstfindright", K, d.key);
          d = d.getRight();
          if (d != null) {
            v.goTo(d);
          } else {
            v.goRight();
            break;
          }
        } else { // left
          addStep("bstfindleft", K, d.key);
          d = d.getLeft();
          if (d != null) {
            v.goTo(d);
          } else {
            v.goLeft();
            break;
          }
        }
        mysuspend();
      }

      if (d == null) { // notfound
        addStep("notfound");
        return;
      }

      d.setColor(NodeColor.FOUND);
      T.setV(null);
      addStep("treapbubbledown");
      // prebubleme k listu
      while (!d.isLeaf()) {
        if (d.getLeft() == null) {
          T.rotate(d.getRight());
        } else if (d.getRight() == null) {
          T.rotate(d.getLeft());
        } else if (d.getRight().p > d.getLeft().p) {
          T.rotate(d.getRight());
        } else {
          T.rotate(d.getLeft());
        }
        mysuspend();
      }
      T.setV(d);
      addStep("treapdeletecase1");
      mysuspend();
      if (d.isRoot()) {
        T.setRoot(null);
      } else if (d.isLeft()) {
        d.getParent().setLeft(null);
      } else {
        d.getParent().setRight(null);
      }
      d.goDown();

      T.reposition();
      addStep("done");
    }
  }

展开阅读全文