アルゴリズムとデータ構造
1
アルゴリズムとデータ構造
アルゴリズムとデータ構造
1
1
2009
2009
年
年
7
7
月
月
2
2
日
日
酒居敬一
酒居敬一
(sakai.keiichi@kochi
(
sakai.keiichi@kochi-
-
tech.ac.jp
tech.ac.jp
)
)
http
木構造
ルートノード
末端ノード
エッジ
ノード
ルートとそれ以外の
ノードにちょうど１つだけ
の経路しか存在しない
二分探索木
29
31
21
19
7
48
30
24
14
32
20
二分木を次のルールで作成
•親よりも小さい値を持つ子は左
•親よりも大きい値を持つ子は右
プログラムの例では、数値のほかに
Objectを置けるようにする
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; // 順序付けのための数値 }
public class MyData implements Comparable {
private MyData() {
}
public MyData(int anId, Object aData) { this.id = anId; this.data = aData; }
interface Comparableには、
compareTo()というメソッドが存在する。
public int compareTo(Object o)；
thisオブジェクトを指定されたオブジェ
クトと比較し、
小さい場合は負の整数、
等しい場合はゼロ、
大きい場合は正の整数、
をそれぞれ返す。
二分探索木のノードに置くデータを表すクラス
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 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; }
二分探索木のノードを表すクラス
二分探索木へノードの挿入
(73ページ以降で詳しく)
17
29
31
21
19
7
48
30
24
14
32
20
17 を挿入したい
19
14
20
29
29
＞ 17
だから…20
＞ 17
だから…14
＜ 17
だから…19
＞ 17
だから…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); return; } currentNode = currentNode.getLeft(); }else{ if(null == currentNode.getRight()){ currentNode.setRight(newNode); return; } currentNode = currentNode.getRight(); } } }
public class BinarySearchTree {
public BinarySearchTree() {
this.root = null; }
private MyNode root; }
二分探索木を表すクラス
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()){ return null; } currentNode = currentNode.getLeft(); }else{ if(null == currentNode.getRight()){ return null; } 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
31
そのまま削除
削除したい
24
削除したい
削除
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){ return false; } } /* 削除処理本体は次以降のページで */ 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()){ if(currentNode == this.root){ this.root = currentNode.getLeft(); }else if(inLeftSubTree){ parentNode.setLeft(currentNode.getLeft()); }else{ parentNode.setRight(currentNode.getLeft()); }
}else if(null == currentNode.getLeft()){ if(currentNode == this.root){ this.root = currentNode.getRight(); }else if(inLeftSubTree){ parentNode.setLeft(currentNode.getRight()); }else{ parentNode.setRight(currentNode.getRight()); } } /* 続く… */
親
親
子
子
親
親
子
親
子
子を２つ持つノードの削除
29
31
21
19
7
48
30
24
14
32
20
20
削除したい
削除
private MyNode getMinimumNode(MyNode aLocalRootNode) {
if(null == aLocalRootNode){ return null;
}
MyNode currentNode = aLocalRootNode; while(true){ if(null == currentNode.getLeft()){ return currentNode; } currentNode = currentNode.getLeft(); } } 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); } }
親
子
子
親
子
子
1. 右部分木から最小の(最左)
のノードを取り出す
2. 削除対象と付け替え
孫
孫
行きがけ順
(pre-order)の走査
二分木を次のルールで走査
1. 自分を訪ねる
2. 自分の左部分木をたどる
3. 自分の右部分木をたどる
29
31
21
19
7
48
30
24
14
32
20
29
20
32
48
30
24
14
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(); }
二分木を次のルールで走査
1. 自分を訪ねる
2. 自分の左部分木をたどる
3. 自分の右部分木をたどる
通りがけ順
(in-order)の走査
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分を訪ねる
3. 自分の右部分木をたどる
二分探索木を走査すると
整列済みデータが得られる
29
31
21
19
7
48
30
24
14
32
20
29
20
32
48
30
24
14
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(); }
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分を訪ねる
3. 自分の右部分木をたどる
二分探索木を走査すると
整列済みデータが得られる
帰りがけ順
(post-order)の走査
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分の右部分木をたどる
3. 自分を訪ねる
29
31
21
19
7
48
30
24
14
32
20
29
20
32
48
30
24
14
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(); }
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分の右部分木をたどる
3. 自分を訪ねる
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); tree.printTree(); System.out.println("木を通りがけ順で表示"); tree.printTreeInOrder(); System.out.println("30, イチゴ を探す"); System.out.println(tree.search(data05).toString()); System.out.println(tree.searchRecursive(data05).toString()); } } 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); 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, "ブドウ");
果物の名前を追加 (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} 木を通りがけ順で表示 {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'バナナ)} (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,(30'イチゴ),null} {null,(30'イチゴ),null}
