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

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

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

子をもたない、または １つだけ持つノードの削除 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 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