酒居敬一(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.

Slides:



Advertisements
Similar presentations
アルゴリズムとデータ構造 2012年6月27日
Advertisements

アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造 2010年7月5日
Ex8. Search for Vacuum Problem(2)
アルゴリズムとデータ構造 補足資料13-4 「2分探索木の追加・削除(ダイジェスト)」
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
二分探索木によるサーチ.
Cプログラミング演習 中間まとめ2.
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
オブジェクト指向 プログラミング 第十一回 知能情報学部 新田直也.
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
二分木のメソッド(続き).
アルゴリズムとデータ構造勉強会 第6回 スレッド木
二分探索木における要素削除 データ構造とプログラミング(10)
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
離散数学 07. 木 五島.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
Ex7. Search for Vacuum Problem
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとデータ構造 2011年6月23日
15.cons と種々のデータ構造.
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
AVL木.
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造 2012年7月2日
アルゴリズムとデータ構造 2012年6月11日
アルゴリズムとデータ構造1 2008年7月24日
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
オペレーティングシステムJ/K (管理のためのデータ構造)
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造 2013年7月2日
アルゴリズムとデータ構造 2013年7月8日
アルゴリズムとデータ構造1 2009年6月15日
アルゴリズムとデータ構造 2012年6月25日
アルゴリズムとデータ構造 2013年6月20日
アルゴリズムとデータ構造 2012年6月21日
アルゴリズムとデータ構造 2010年6月17日
アルゴリズムとデータ構造1 2005年7月12日
アルゴリズムとデータ構造1 2007年7月6日
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

酒居敬一(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

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

プログラムの例では、数値のほかに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()); このような再帰呼び出しはループと相互に変換可能

子をもたない、または 1つだけ持つノードの削除 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()); /* 続く… */ 親 親 親 子 子 親 親 子 子

子を2つ持つノードの削除 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'バナナ)}