酒居敬一(sakai.keiichi@kochi-tech.ac.jp) アルゴリズムとデータ構造1 2005年7月8日 酒居敬一(sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html

ハノイの塔 一回に一枚の円盤しか動かしてはいけない。 移動の途中で円盤の大小を逆に積んではいけない。 常に大きい方の円盤が下になるようにする。 棒以外のところに円盤を置いてはいけない。 円盤数5のとき、手数は31 nのときは手数2n－1

分割統治法 クイックソート マージソート 分割 統合 基準値を用いて、基準より大きい値からなる部分問題と基準より小さい値からなる部分問題に分割し解く 問題を空間的に2分割し、各々の部分問題を解く 分割 部分問題がソート済みであれば、基準値とそれぞれの部分問題との大小関係は分割のときに決定していることから、結合するだけでよいことになる。 部分問題の解どおしを比較しながら順に併合することで、部分問題の解の大小関係は維持したまま元の問題の解を得ることができる 統合

b neg b b * 4 a * c * － sqrt ＋ 2 a * ÷ をRPNで書く b neg b b * 4 a * c * － sqrt ＋ 2 a * ÷ b neg b b * 4 a * c * － sqrt － 2 a * ÷ 　　あるいは b neg b b * c 4 a * * － sqrt ＋ 2 a * ÷ b neg b b * c 4 a * * － sqrt － 2 a * ÷ 　他にあるかもしれないけど、意味があってればOK

プログラムの例では、数値のほかにObjectを置けるようにする 二分探索木 二分木を次のルールで作成 親よりも小さい値を持つ子は左 親よりも大きい値を持つ子は右 29 20 32 14 24 30 48 7 19 21 31 プログラムの例では、数値のほかにObjectを置けるようにする

二分探索木のノードに置くデータを表すクラス public class MyData implements Comparable { private MyData() } 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; // 順序付けのための数値 interface Comparableには、compareTo()というメソッドが存在する。 public int compareTo(Object o)； thisオブジェクトを指定されたオブジェクトと比較し、 　小さい場合は負の整数、 　等しい場合はゼロ、 　大きい場合は正の整数、 をそれぞれ返す。

ノードに関する操作 二分探索木のノードを表すクラス public class MyNode { private 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; 二分探索木のノードを表すクラス

二分探索木へ挿入するメソッド 二分探索木を表すクラス 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); currentNode = currentNode.getLeft(); }else{ if(null == currentNode.getRight()){ currentNode.setRight(newNode); currentNode = currentNode.getRight(); 二分探索木を表すクラス

ループによる二分探索 ループの終了条件 末端に達した 一致するデータを発見 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()){ currentNode = currentNode.getLeft(); }else{ if(null == currentNode.getRight()){ currentNode = currentNode.getRight(); ループの終了条件 末端に達した 一致するデータを発見 ループによる二分探索

このような再帰呼び出しはループと相互に変換可能 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()); このような再帰呼び出しはループと相互に変換可能

削除対象を探す 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){ /* 削除処理本体は次以降のページで */ currentNode.setLeft(null); currentNode.setRight(null); return true; 削除対象を探す

親 親 親 子 子 親 親 子 子 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()){ this.root = currentNode.getLeft(); parentNode.setLeft(currentNode.getLeft()); parentNode.setRight(currentNode.getLeft()); }else if(null == currentNode.getLeft()){ this.root = currentNode.getRight(); parentNode.setLeft(currentNode.getRight()); parentNode.setRight(currentNode.getRight()); /* 続く… */ 親 親 親 子 子 親 親 子 子

右部分木から最小の(最左)のノードを取り出す 削除対象と付け替え 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); } 右部分木から最小の(最左)のノードを取り出す 削除対象と付け替え 親 親 private MyNode getMinimumNode(MyNode aLocalRootNode) { if(null == aLocalRootNode){ return null; } MyNode currentNode = aLocalRootNode; while(true){ if(null == currentNode.getLeft()){ return currentNode; currentNode = currentNode.getLeft(); 子 子 子 子 孫 孫

二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 二分探索木を走査すると 整列済みデータが得られる public void printTreeInOrder() { System.out.println(this.traverseInOrder(this.root)); } private String traverseInOrder(MyNode aLocalRootNode) if(null == aLocalRootNode){ return ""; StringBuffer treeRepresentation = new StringBuffer(); treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getLeft())); treeRepresentation.append(aLocalRootNode +System.getProperty("line.separator")); treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getRight())); return treeRepresentation.toString(); 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 二分探索木を走査すると 整列済みデータが得られる

二分木を次のルールで走査 自分の左部分木をたどる 自分の右部分木をたどる 自分を訪ねる 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(); 二分木を次のルールで走査 自分の左部分木をたどる 自分の右部分木をたどる 自分を訪ねる

二分木を次のルールで走査 自分を訪ねる 自分の左部分木をたどる 自分の右部分木をたどる public void printTreePreOrder() { System.out.println(this.traversePreOrder(this.root)); } 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(); 二分木を次のルールで走査 自分を訪ねる 自分の左部分木をたどる 自分の右部分木をたどる

System.out.println("木を行きがけ順で表示"); tree.printTreePreOrder(); public class BinarySearchTreeTest { public static void main(String[] anyArguments) BinarySearchTree tree = new BinarySearchTree(); MyData data01 = new MyData(29, "リンゴ"); MyData data02 = new MyData(20, "ミカン"); MyData data03 = new MyData(14, "サクランボ"); MyData data04 = new MyData(32, "バナナ"); MyData data05 = new MyData(30, "イチゴ"); MyData data06 = new MyData(24, "ブルーベリー"); MyData data07 = new MyData( 7, "グレープフルーツ"); MyData data08 = new MyData(21, "レモン"); MyData data09 = new MyData(48, "メロン"); MyData data10 = new MyData(31, "スイカ"); MyData data11 = new MyData(19, "ナシ"); MyData data12 = new MyData(17, "モモ"); MyData data13 = new MyData(23, "マンゴー"); MyData data14 = new MyData(28, "ブドウ"); 　　　　　　　System.out.println("果物の名前を追加"); tree.insert(data01); tree.insert(data02); tree.insert(data03); tree.insert(data04); tree.insert(data05); tree.insert(data06); tree.insert(data07); tree.insert(data08); tree.insert(data09); tree.insert(data10); tree.insert(data11); tree.insert(data12); tree.insert(data13); tree.insert(data14); tree.printTree(); System.out.println("木を行きがけ順で表示"); tree.printTreePreOrder(); System.out.println("木を通りがけ順で表示"); tree.printTreeInOrder(); System.out.println("木を帰りがけ順で表示"); tree.printTreePostOrder(); tree.remove(data10); tree.remove(data11); tree.remove(data02); System.out.println("30, イチゴ を探す"); System.out.println(tree.search(data05).toString()); System.out.println(tree.searchRecursive(data05).toString()); }

ミカン・スイカ・ナシを削除 果物の名前を追加 (7'グレープフルーツ) (14'サクランボ) (17'モモ) (19'ナシ) (20'ミカン) (21'レモン) (23'マンゴー) (24'ブルーベリー) (28'ブドウ) (29'リンゴ) (30'イチゴ) (31'スイカ) (32'バナナ) (48'メロン) 木を行きがけ順で表示 {(20'ミカン),(29'リンゴ),(32'バナナ)} {(14'サクランボ),(20'ミカン),(24'ブルーベリー)} {(7'グレープフルーツ),(14'サクランボ),(19'ナシ)} {null,(7'グレープフルーツ),null} {(17'モモ),(19'ナシ),null} {null,(17'モモ),null} {(21'レモン),(24'ブルーベリー),(28'ブドウ)} {null,(21'レモン),(23'マンゴー)} {null,(23'マンゴー),null} {null,(28'ブドウ),null} {(30'イチゴ),(32'バナナ),(48'メロン)} {null,(30'イチゴ),(31'スイカ)} {null,(31'スイカ),null} {null,(48'メロン),null} (7'グレープフルーツ) (14'サクランボ) (17'モモ) (21'レモン) (23'マンゴー) (24'ブルーベリー) (28'ブドウ) (29'リンゴ) (30'イチゴ) (32'バナナ) (48'メロン) 木を通りがけ順で表示 {null,(7'グレープフルーツ),null} {(7'グレープフルーツ),(14'サクランボ),(17'モモ)} {null,(17'モモ),null} {(14'サクランボ),(21'レモン),(24'ブルーベリー)} {null,(23'マンゴー),null} {(23'マンゴー),(24'ブルーベリー),(28'ブドウ)} {null,(28'ブドウ),null} {(21'レモン),(29'リンゴ),(32'バナナ)} {null,(30'イチゴ),null} {(30'イチゴ),(32'バナナ),(48'メロン)} {null,(48'メロン),null} 30, イチゴ を探す ミカン・スイカ・ナシを削除 木を通りがけ順で表示 {null,(7'グレープフルーツ),null} {(7'グレープフルーツ),(14'サクランボ),(19'ナシ)} {null,(17'モモ),null} {(17'モモ),(19'ナシ),null} {(14'サクランボ),(20'ミカン),(24'ブルーベリー)} {null,(21'レモン),(23'マンゴー)} {null,(23'マンゴー),null} {(21'レモン),(24'ブルーベリー),(28'ブドウ)} {null,(28'ブドウ),null} {(20'ミカン),(29'リンゴ),(32'バナナ)} {null,(30'イチゴ),(31'スイカ)} {null,(31'スイカ),null} {(30'イチゴ),(32'バナナ),(48'メロン)} {null,(48'メロン),null} 木を通りがけ順で表示 {null,(7'グレープフルーツ),null} {(7'グレープフルーツ),(14'サクランボ),(19'ナシ)} {null,(17'モモ),null} {(17'モモ),(19'ナシ),null} {(14'サクランボ),(20'ミカン),(24'ブルーベリー)} {null,(21'レモン),(23'マンゴー)} {null,(23'マンゴー),null} {(21'レモン),(24'ブルーベリー),(28'ブドウ)} {null,(28'ブドウ),null} {(20'ミカン),(29'リンゴ),(32'バナナ)} {null,(30'イチゴ),(31'スイカ)} {null,(31'スイカ),null} {(30'イチゴ),(32'バナナ),(48'メロン)} {null,(48'メロン),null} 木を帰りがけ順で表示 {null,(7'グレープフルーツ),null} {null,(17'モモ),null} {(17'モモ),(19'ナシ),null} {(7'グレープフルーツ),(14'サクランボ),(19'ナシ)} {null,(23'マンゴー),null} {null,(21'レモン),(23'マンゴー)} {null,(28'ブドウ),null} {(21'レモン),(24'ブルーベリー),(28'ブドウ)} {(14'サクランボ),(20'ミカン),(24'ブルーベリー)} {null,(31'スイカ),null} {null,(30'イチゴ),(31'スイカ)} {null,(48'メロン),null} {(30'イチゴ),(32'バナナ),(48'メロン)} {(20'ミカン),(29'リンゴ),(32'バナナ)}