2012614 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/2012/index.html 1
2
2 3
29 20 32 14 24 30 48 7 19 21 31 4
N O(log N) 29 O(N) 20 32 14 24 30 48 7 19 21 31 5
48 32 N O(log N) 30 31 O(N) 24 29 21 19 20 14 7 6
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
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
(73) 29 17 29 17 20 17 20 32 14 17 14 24 30 48 7 19 21 31 19 17 17 9
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
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
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
29 20 32 14 24 30 48 7 19 21 31 13
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
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
29 20 32 14 24 30 48 7 19 21 31 16
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
(pre-order) 1. 2. 3. 14 24 29 20 32 public void printtreepreorder() { System.out.println(this.traversePreOrder(this.root)); 30 private String traversepreorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; 7 19 21 31 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
(in-order) 1. 2. 3. 14 24 29 20 32 private String traverseinorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; StringBuffer treerepresentation 7 = new 19 StringBuffer(); 21 31 treerepresentation.append(this.traverseinorder(alocalrootnode.getleft())); treerepresentation.append(alocalrootnode +System.getProperty("line.separator")); treerepresentation.append(this.traverseinorder(alocalrootnode.getright())); return treerepresentation.tostring(); 19 30 48
(post-order) 1. 2. 3. 29 14 20 32 public void printtreepostorder() { System.out.println(this.traversePostOrder(this.root)); 24 30 private String traversepostorder(mynode alocalrootnode) { if(null == alocalrootnode){ return ""; 7 19 21 31 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