ALG ppt

Size: px

Start display at page:

Download "ALG ppt"

きよたつやぶき
4 years ago
Views:

2 2

3 2 3

5 N O(log N) 29 O(N)

6 48 32 N O(log N) O(N)

7 interface Comparable compareto() public int compareto(object o) this public class MyData implements Comparable { public MyData(int anid, Object adata) { this.id = anid; this.data = adata; public int compareto(object atarget) { int targetid = ((MyData)aTarget).getId(); if(this.id == targetid){ return 0; if(this.id > targetid){ return 1; return -1; public Object getdata() { return this.data; public int getid() { return (this.id); public String tostring() { return "(" + this.id + "'" + this.data + ")"; private Object data; // private int id; // 7

8 public class MyNode { public MyNode(MyData adata) { this.data = adata; public MyData getdata() { return this.data; public MyNode getleft() { return this.left; public MyNode getright() { return this.right; public void setleft(mynode anode) { this.left = anode; public void setright(mynode anode) { this.right = anode; public String tostring() { MyData leftdata = null; MyData rightdata = null; if(null!= this.left){ leftdata = this.left.getdata(); if(null!= this.right){ rightdata = this.right.getdata(); return ("{"+leftdata+","+this.data+","+rightdata+""); private MyData data; private MyNode left; private MyNode right; 8

9 (73)

10 public class BinarySearchTree { public BinarySearchTree() { this.root = null; private MyNode root; public void insert(mydata adata) { MyNode newnode = new MyNode(aData); if(null == this.root){ this.root = newnode; return; MyNode currentnode = this.root; while(true){ if(0 < currentnode.getdata().compareto(adata)){ if(null == currentnode.getleft()){ currentnode.setleft(newnode); return; currentnode = currentnode.getleft(); else{ if(null == currentnode.getright()){ currentnode.setright(newnode); return; currentnode = currentnode.getright(); 10

11 public MyNode search(mydata adata) { if(null == this.root){ return null; MyNode currentnode = this.root; while(true){ if(0 == currentnode.getdata().compareto(adata)){ return currentnode; if(0 < currentnode.getdata().compareto(adata)){ if(null == currentnode.getleft()){ return null; currentnode = currentnode.getleft(); else{ if(null == currentnode.getright()){ return null; currentnode = currentnode.getright(); 11

12 Tail Recursion () public MyNode searchrecursive(mydata adata) { return searchr(adata, this.root); private MyNode searchr(mydata adata, MyNode aroot) { if(null == aroot){ // () return null; int result = aroot.getdata().compareto(adata); if(0 == result){ // return aroot; return searchr(adata, (0 < result)? aroot.getleft(): aroot.getright()); 12

14 public boolean remove(mydata adata) { if(null == this.root){ return false; MyNode parentnode = this.root; MyNode currentnode = this.root; boolean inleftsubtree = false; while(0!= currentnode.getdata().compareto(adata)){ parentnode = currentnode; if(0 < currentnode.getdata().compareto(adata)){ currentnode = currentnode.getleft(); inleftsubtree = true; else{ currentnode = currentnode.getright(); inleftsubtree = false; if(null == currentnode){ return false; /* / currentnode.setleft(null); currentnode.setright(null); return true; 14

15 if((null == currentnode.getleft()) && (null == currentnode.getright())){ if(currentnode == this.root){ this.root = null; else if(inleftsubtree){ parentnode.setleft(null); else{ parentnode.setright(null); else if(null == currentnode.getright()){ if(currentnode == this.root){ this.root = currentnode.getleft(); else if(inleftsubtree){ parentnode.setleft(currentnode.getleft()); else{ parentnode.setright(currentnode.getleft()); else if(null == currentnode.getleft()){ if(currentnode == this.root){ this.root = currentnode.getright(); else if(inleftsubtree){ parentnode.setleft(currentnode.getright()); else{ parentnode.setright(currentnode.getright()); /* */ 15

17 else{ MyNode minimumnode = this.getminimumnode(currentnode.getright()); this.remove(minimumnode.getdata()); minimumnode.setleft(currentnode.getleft()); minimumnode.setright(currentnode.getright()); if(currentnode == this.root){ this.root = minimumnode; else if(inleftsubtree){ parentnode.setleft(minimumnode); else{ parentnode.setright(minimumnode); 1. () 2. private MyNode getminimumnode(mynode alocalrootnode){ if(null == alocalrootnode){ return null; MyNode currentnode = alocalrootnode; while(true){ if(null == currentnode.getleft()){ return currentnode; currentnode = currentnode.getleft(); 17

18 (pre-order) public void printtreepreorder() { System.out.println(this.traversePreOrder(this.root)); 30 private String traversepreorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; StringBuffer treerepresentation = new StringBuffer(); treerepresentation.append(alocalrootnode + System.getProperty("line.separator")); treerepresentation.append(this.traversepreorder(alocalrootnode.getleft())); treerepresentation.append(this.traversepreorder(alocalrootnode.getright())); return treerepresentation.tostring(); 18 48

19 (in-order) private String traverseinorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; StringBuffer treerepresentation 7 = new 19 StringBuffer(); treerepresentation.append(this.traverseinorder(alocalrootnode.getleft())); treerepresentation.append(alocalrootnode +System.getProperty("line.separator")); treerepresentation.append(this.traverseinorder(alocalrootnode.getright())); return treerepresentation.tostring();

20 (post-order) public void printtreepostorder() { System.out.println(this.traversePostOrder(this.root)); private String traversepostorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; StringBuffer treerepresentation = new StringBuffer(); treerepresentation.append(this.traversepostorder(alocalrootnode.getleft())); treerepresentation.append(this.traversepostorder(alocalrootnode.getright())); treerepresentation.append(alocalrootnode + System.getProperty("line.separator")); return treerepresentation.tostring(); 20 48

アルゴリズムとデータ構造１

アルゴリズムとデータ構造１ 1 200972 (sakai.keiichi@kochi sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi ://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2009/index.html 29 20 32 14 24 30 48 7 19 21 31 Object public class