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

木構造 ルートとそれ以外の ノードにちょうど１つだけ の経路しか存在しない ルートノード 末端ノード エッジ ノード

プログラムの例では、数値のほかに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; 二分探索木のノードを表すクラス

二分探索木へノードの挿入 (73ページ以降で詳しく) 17 を挿入したい 29 ＞ 17 だから… 29 31 21 19 7 48 30 24 14 32 20 29 20 ＞ 17 だから… 20 14 ＜ 17 だから… 14 19 19 ＞ 17 だから… 17

二分探索木へ挿入するメソッド 二分探索木を表すクラス 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()); このような再帰呼び出しはループと相互に変換可能

子をもたない、または １つだけ持つノードの削除 29 31 21 19 7 48 30 24 14 32 20 24 削除したい 削除 そのまま削除 31 削除したい

削除対象を探す 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()); /* 続く… */ 親 親 親 子 子 親 親 子 子

子を２つ持つノードの削除 29 31 21 19 7 48 30 24 14 32 20 削除 20 削除したい

右部分木から最小の(最左)のノードを取り出す 削除対象と付け替え 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(); 子 子 子 子 孫 孫

行きがけ順(pre-order)の走査 二分木を次のルールで走査 自分を訪ねる 自分の左部分木をたどる 自分の右部分木をたどる 29 31 21 19 7 48 30 24 14 32 20 29 20 32 14 24 30 48 7 19 21 31

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

通りがけ順(in-order)の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 二分探索木を走査すると 整列済みデータが得られる 29 31 21 19 7 48 30 24 14 32 20 29 20 32 14 24 30 48 7 19 21 31

二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 二分探索木を走査すると 整列済みデータが得られる 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(); 二分木を次のルールで走査 自分の左部分木をたどる 自分を訪ねる 自分の右部分木をたどる 二分探索木を走査すると 整列済みデータが得られる

帰りがけ順(post-order)の走査 二分木を次のルールで走査 自分の左部分木をたどる 自分の右部分木をたどる 自分を訪ねる 29 31 21 19 7 48 30 24 14 32 20 29 20 32 14 24 30 48 7 19 21 31

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

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'バナナ)}