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

Slides:



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

アルゴリズムとデータ構造1 2005年7月8日
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造 2010年7月5日
Ex8. Search for Vacuum Problem(2)
アルゴリズムとデータ構造 2012年6月14日
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
オペレーティングシステムJ/K 2004年11月4日
アルゴリズムとデータ構造 2011年6月13日
データ構造と アルゴリズム 第八回 知能情報学部 新田直也.
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
アルゴリズムとデータ構造 2011年6月20日
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
Cプログラミング演習 中間まとめ2.
アルゴリズムとデータ構造 2011年7月4日
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
アルゴリズムとデータ構造1 2005年7月26日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2006年6月16日
アルゴリズムとデータ構造1 2005年7月15日
二分木のメソッド(続き).
二分探索木における要素削除 データ構造とプログラミング(10)
第9回 優先度つき待ち行列,ヒープ,二分探索木
アルゴリズムとデータ構造1 2005年7月1日
アルゴリズムとデータ構造1 2009年6月29日
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
離散数学 07. 木 五島.
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2009年7月9日
アルゴリズムとデータ構造1 2005年7月5日
プログラミング 4 整列アルゴリズム.
アルゴリズムとデータ構造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日
情報工学概論 (アルゴリズムとデータ構造)
アルゴリズムとデータ構造1 2009年7月2日
アルゴリズムとデータ構造 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.高度な木.
Ibaraki Univ. Dept of Electrical & Electronic Eng.
アルゴリズムとデータ構造 2012年7月9日
Presentation transcript:

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

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

2012年6月14日 二分木 データ 左 右 各ノードが持てる子の数が高々2である木 二分探索木として、順序木を使う

二分探索木 二分木を次のルールで作成 親よりも小さい値を持つ子は左 親よりも大きい値を持つ子は右 29 20 32 14 24 30 48 7 19 21 31

ノードの探索 ノード数をNとすると O(log N) の計算量で探索できる 木が偏っているときは 最悪O(N)になるが… 29 20 32 14 24 30 48 7 19 21 31

最悪の形(二分探索木) 48 32 31 ノード数をNとすると O(log N) の計算量で探索できる 30 木が偏っているときは 最悪O(N)になるが… 30 29 24 21 20 木の深さをバランスよく したものを平衡木という 平衡木については次回述べる 19 14 7

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

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

二分探索木へノードの挿入 (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 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(); 14 24 30 48 7 19 21 31

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

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