一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 839|回复: 9
收起左侧

Berkeley CS 61B Data Structures(in Java) Lab14(Lab 14@2014 Spring)讨论贴

[复制链接] |试试Instant~ |关注本帖
enirinth 发表于 2015-6-14 22:01:51 | 显示全部楼层 |阅读模式

[其他]Berkeley CS 61B Data Structures(in Java) (2014 Spring) #14 - 2014-01-22@UC Berkeley

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
14年和06年的作业大部分是一样的,但是14年的lab9是个理论证明lab,所以之后是06的lab#+1 = 14的lab#;
但06年的lab13开始和14年的lab14不一样了; 而且14年还有个lab15是给复习期末用的,06年到lab13就没了;

14年lab14:
实现splay tree的操作;zig(); zigZag(), rotateLeft(), rotateRight() 已经帮你实现好了;另外要你实现zigZig() 和 整体的splayNode()操作。
结果如下:

111.png


只有没有error就是输出成功;
tree的结构可以看一下是不是确实更balanced了
阿童木 发表于 2016-3-8 10:05:03 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
QQ截图20160308100342.png
回复 支持 反对

使用道具 举报

pirateshadow 发表于 2016-5-7 16:30:03 | 显示全部楼层
关注一亩三分地微博:
Warald
自己画了一下,确实balance了一些,不过没想象的那么balance。。
Screen Shot 2016-05-07 at 4.15.43 PM.png
Screen Shot 2016-05-07 at 4.27.59 PM.png
回复 支持 反对

使用道具 举报

Chris1993 发表于 2016-5-7 16:38:13 | 显示全部楼层
这个Lab应该要求自己实现rotate right&left
Screen Shot 2016-05-07 at 4.35.57 PM.png
Screen Shot 2016-05-07 at 4.37.12 PM.png
回复 支持 反对

使用道具 举报

irene000000 发表于 2016-5-14 17:04:37 | 显示全部楼层
感觉最麻烦的rotate老师都写好了。。。
lab14.png
回复 支持 反对

使用道具 举报

zzdsg 发表于 2016-8-26 19:26:27 | 显示全部楼层
写完lab14啦,就差一个homework10就结课了!开心
lab14.png
回复 支持 反对

使用道具 举报

codergoose 发表于 2016-12-17 21:39:08 | 显示全部楼层
然而最麻烦的rotateleft和rotateright已经写好了 lab14.png

回复 支持 反对

使用道具 举报

蔚蔚酱 发表于 2017-3-20 10:30:07 | 显示全部楼层
rotate应该留给我们写
Lab14.PNG
回复 支持 反对

使用道具 举报

俘虏你的心 发表于 2017-3-21 16:10:55 | 显示全部楼层
自己完成了min(), max(), remove(),有了Lab11的基础,比较容易写出来。
首先附上Test code
  1.    String shouldBe = null;

  2.     System.out.println("------------------------------------------");
  3.     System.out.println("PART I:  Testing insert()\n");   

  4.     System.out.println("Inserting 1G, 3O, 2O, 5J, 4D, 7B, 6O.");
  5.     SplayTree tree = new SplayTree();
  6.     tree.insert(new Integer(1), "G");
  7.     tree.insert(new Integer(3), "O");
  8.     tree.insert(new Integer(2), "O");
  9.     tree.insert(new Integer(5), "J");
  10.     tree.insert(new Integer(4), "D");
  11.     tree.insert(new Integer(7), "B");
  12.     tree.insert(new Integer(6), "O");
  13.     System.out.println("Tree is:  " + tree);
  14.     if (tree.toString().equals("(((((1G)2O)3O)4D)5J)6O(7B)")) {
  15.       System.out.println("insert() works correctly.");
  16.     }

  17.     System.out.println("------------------------------------------");
  18.     System.out.println("PART II:  Testing find()\n");

  19.     System.out.println("Inserting 10A, 9B, 8C, 7D, 6E, 5F, 4G, 3H, 2I, 1J");
  20.     SplayTree splayTest = new SplayTree();
  21.     makeUnbalancedTree(splayTest);
  22.     System.out.println("tree is:  " + splayTest);
  23.     splayTest.testFind(10, "A");
  24.     System.out.println("The tree should be better balanced now: " + splayTest);
  25.     shouldBe = "(1J((2I)3H((4G)5F((6E)7D((8C)9B)))))10A";
  26.     if (!splayTest.toString().equals(shouldBe)) {
  27.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  28.     }

  29.     System.out.println("Inserting 3A, 7B, 4C, 2D, 9E, 1F");
  30.     SplayTree tree2 = new SplayTree();
  31.     tree2.insert(new Integer(3), "A");
  32.     tree2.insert(new Integer(7), "B");
  33.     tree2.insert(new Integer(4), "C");
  34.     tree2.insert(new Integer(2), "D");
  35.     tree2.insert(new Integer(9), "E");
  36.     tree2.insert(new Integer(1), "F");
  37.     System.out.println("Tree 2 is:  " + tree2);
  38.     shouldBe = "1F((2D(3A((4C)7B)))9E)";
  39.     if (!tree2.toString().equals(shouldBe)) {
  40.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  41.     }
  42.     tree2.testFind(7, "B");
  43.     System.out.println("Tree 2 is:  " + tree2);
  44.     shouldBe = "(1F((2D)3A(4C)))7B(9E)";
  45.     if (!tree2.toString().equals(shouldBe)) {
  46.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  47.     }
  48.     tree2.testFind(4, "C");
  49.     System.out.println("Tree 2 is:  " + tree2);
  50.     shouldBe = "((1F(2D))3A)4C(7B(9E))";
  51.     if (!tree2.toString().equals(shouldBe)) {
  52.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  53.     }

  54.     System.out.println("------------------------------------------");
  55.     System.out.println("PART III:  Testing min() and max()\n");

  56.     System.out.println("Inserting 9A, 3B, 5C, 7D, 4E, 2F, 10G");
  57.     SplayTree tree3 = new SplayTree();
  58.     tree3.insert(new Integer(9), "A");
  59.     tree3.insert(new Integer(3), "B");
  60.     tree3.insert(new Integer(5), "C");
  61.     tree3.insert(new Integer(7), "D");
  62.     tree3.insert(new Integer(2), "E");
  63.     tree3.insert(new Integer(8), "F");
  64.     tree3.insert(new Integer(6), "G");
  65.     shouldBe = "(2E((3B)5C))6G((7D)8F(9A))";
  66.     if (!tree3.toString().equals(shouldBe)) {
  67.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  68.     }   

  69.     Entry min = tree3.min();
  70.     System.out.println("min should be 2E, which is: " +
  71.       ((Integer) min.key()).toString() + ((String) min.value()).toString());
  72.     shouldBe = "2E(((3B)5C)6G((7D)8F(9A)))";
  73.     if (!tree3.toString().equals(shouldBe)) {
  74.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  75.     }

  76.     Entry max = tree3.max();
  77.     System.out.println("max should be 9A, which is: " +
  78.       ((Integer) max.key()).toString() + ((String) max.value()).toString());
  79.     shouldBe = "(2E((((3B)5C)6G(7D))8F))9A";
  80.     if (!tree3.toString().equals(shouldBe)) {
  81.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  82.     }

  83.     System.out.println("------------------------------------------");
  84.     System.out.println("PART IV:  Testing remove()\n");

  85.     System.out.println("Inserting 3A, 7B, 4C, 2D, 9E, 1F");
  86.     SplayTree tree4 = new SplayTree();
  87.     tree4.insert(new Integer(3), "A");
  88.     tree4.insert(new Integer(7), "B");
  89.     tree4.insert(new Integer(4), "C");
  90.     tree4.insert(new Integer(2), "D");
  91.     tree4.insert(new Integer(9), "E");
  92.     tree4.insert(new Integer(1), "F");
  93.     System.out.println("Tree 4 is:  " + tree2);
  94.     shouldBe = "1F((2D(3A((4C)7B)))9E)";
  95.     if (!tree4.toString().equals(shouldBe)) {
  96.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  97.     }

  98.     tree4.testRemove(2, "(1F(3A((4C)7B)))9E", 5);
  99.     tree4.testRemove(4, "((1F)3A)7B(9E)", 4);
  100.     tree4.testFind(1, "F");
  101.     tree4.testFind(9, "E");
  102.     shouldBe = "(1F((3A)7B))9E";
  103.     if (!tree4.toString().equals(shouldBe)) {
  104.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  105.     }
  106.     tree4.testRemove(7, "1F((3A)9E)", 3);
  107.     tree4.testRemove(1, "(3A)9E", 2);
  108.     tree4.testRemove(9, "3A", 1);
  109.     tree4.testRemove(3, "", 0);

  110.     System.out.println("------------------------------------------");
  111.     System.out.println("PART V:  Testing remove() for nonexisting keys\n");

  112.     System.out.println("Inserting 3A, 7B, 4C, 2D, 9E, 1F");
  113.     SplayTree tree5 = new SplayTree();
  114.     tree5.insert(new Integer(3), "A");
  115.     tree5.insert(new Integer(7), "B");
  116.     tree5.insert(new Integer(4), "C");
  117.     tree5.insert(new Integer(2), "D");
  118.     tree5.insert(new Integer(9), "E");
  119.     tree5.insert(new Integer(1), "F");
  120.     System.out.println("Tree 5 is:  " + tree2);
  121.     shouldBe = "1F((2D(3A((4C)7B)))9E)";
  122.     if (!tree5.toString().equals(shouldBe)) {
  123.       System.err.println("  ERROR:  SHOULD BE " + shouldBe);
  124.     }

  125.     tree5.testRemove(5, "(1F(2D(3A)))4C((7B)9E)", 6);
  126.     tree5.testRemove(10, "((1F(2D(3A)))4C(7B))9E", 6);
  127.     tree5.testRemove(0, "1F((2D(3A))4C((7B)9E))", 6);
复制代码


然后是remove()
  1.   public Entry remove(Object key) {
  2.     if (root == null) {
  3.       System.err.println("The Splay tree is empty.");
  4.       return null;
  5.     }

  6.     BinaryTreeNode node = root;
  7.     Entry e = null;
  8.     while (node != null) {
  9.       if (((Comparable) key).compareTo(node.entry.key()) < 0) {
  10.         if (node.leftChild == null) {
  11.           splayNode(node);  // Splay the last node visited to the root.
  12.           return null;
  13.         }
  14.         node = node.leftChild;
  15.       } else if (((Comparable) key).compareTo(node.entry.key()) > 0) {
  16.         if (node.rightChild == null) {
  17.           splayNode(node);  // Splay the last node visited to the root.
  18.           return null;
  19.         }
  20.         node = node.rightChild;
  21.       } else {    // Find the Entry to be removed.
  22.         e = node.entry;

  23.         BinaryTreeNode toBeRemoved = null;
  24.         if (node.leftChild != null && node.rightChild != null) { // Two children
  25.           // Find the parent of the node with minimum key from this node's right
  26.           // subtree.
  27.           toBeRemoved = minNodeNoSplay(node.rightChild);
  28.           node.entry = toBeRemoved.entry;
  29.         } else {    // One child or no children.
  30.           toBeRemoved = node;
  31.         }
  32.         removeAndSplay(toBeRemoved);
  33.         break;
  34.       }
  35.     }

  36.     return e;
  37.   }


  38.   // Remove a node and Splay its parent to the root. The Splay tree size will
  39.   // be decreased by 1.
  40.   private void removeAndSplay(BinaryTreeNode node) {
  41.     // Do nothing for node with two children.
  42.     if (node.leftChild != null && node.rightChild != null) {
  43.       System.err.println("Error! This node has two children");
  44.       System.exit(1);
  45.     }

  46.     BinaryTreeNode nodeParent = node.parent;
  47.     if (node.leftChild == null && node.rightChild == null) {  // No children.
  48.       if (nodeParent == null) { makeEmpty(); return; }
  49.       // Detach node from parent.
  50.       if (nodeParent.leftChild == node) { nodeParent.leftChild = null; }
  51.       else { nodeParent.rightChild = null; }
  52.       splayNode(nodeParent);
  53.     } else {    // One child.
  54.       if (nodeParent == null) {
  55.         if (node.leftChild != null) { root = node.leftChild;}        
  56.         else { root = node.rightChild; }
  57.         root.parent = null;     // This is critical!
  58.       } else {
  59.         BinaryTreeNode child = null;
  60.         if (node.leftChild != null) { child = node.leftChild; }
  61.         else { child = node.rightChild; }

  62.         // Attach child to parent and parent to child.
  63.         child.parent = nodeParent;
  64.         if (nodeParent.leftChild == node) { nodeParent.leftChild = child; }
  65.         else { nodeParent.rightChild = child; }
  66.         splayNode(nodeParent);
  67.       }
  68.     }
  69.     garbageCollect(node);
  70.     size--;
  71.   }

  72.   // Set all references of node to null to facilitate garbage collection.
  73.   private void garbageCollect(BinaryTreeNode node) {
  74.     node.parent = null;
  75.     node.leftChild = null;
  76.     node.rightChild = null;
  77.   }

  78.   // Find the node with minimum key in the Splay tree rooted in "node"
  79.   // and no splayNode().
  80.   private BinaryTreeNode minNodeNoSplay(BinaryTreeNode node) {
  81.     if (node == null) {
  82.       System.err.println("The Splay tree is empty.");
  83.       return null;
  84.     }

  85.     BinaryTreeNode n = node;
  86.     while (n.leftChild != null) {
  87.       n = n.leftChild;
  88.     }
  89.     // Now n is the parent of the leftmost node in the Splay tree.
  90.     return n;
  91.   }
复制代码
回复 支持 反对

使用道具 举报

DetectiveConan 发表于 2017-3-23 12:20:47 | 显示全部楼层
这次作业不难。自己写了下remove( ).

Screenshot from 2017-03-23 12-18-01.png
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-4-29 09:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表