アルゴリズムとデータ構造1

アルゴリズムとデータ構造
2011年6月14日
酒居敬一([email protected])
http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2011/index.html
1
木構造
ルートとそれ以外の
ノードにちょうど１つだけ
の経路しか存在しない
ルートノード
エッジ
ノード
末端ノード
2
２０１１年６月１４日
二分木
•各ノードが持てる子の数が高々２である木
•二分探索木として、順序木を使う
データ
左
右
データ
左
データ
左
右
データ
右
左
データ
左
右
データ
左
右
右
データ
左
右
3
二分探索木
二分木を次のルールで作成
•親よりも小さい値を持つ子は左
•親よりも大きい値を持つ子は右
29
20
14
7
32
24
19
21
30
48
31
4
ノードの探索
ノード数をNとすると
O(log N)
の計算量で探索できる
29
木が偏っているときは
最悪O(N)になるが…
20
14
7
24
19
21
32
30
48
31
5
最悪の形（二分探索木）
48
32
31
ノード数をNとすると
O(log N)
の計算量で探索できる
30
29
木が偏っているときは
最悪O(N)になるが…
24
21
20
19
14
7
木の深さをバランスよく
したものを平衡木という
平衡木については次回述べる
6
public class MyData implements Comparable {
public MyData(int anId, Object aData) {
二分探索木のノードに置くデータを
this.id = anId;
表すクラス
this.data = aData;
}
public int compareTo(Object aTarget) {
interface Comparableには、
int targetId = ((MyData)aTarget).getId();
if(this.id == targetId){
compareTo()というメソッドが存在する。
return 0;
}
public int compareTo(Object o)；
if(this.id > targetId){
return 1;
thisオブジェクトを指定されたオブジェ
}
クトと比較し、
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;
// 順序付けのための数値
7
}
二分探索木のノードを表すクラス
ノードに関する操作
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;
8
二分探索木へノードの挿入
(73ページ以降で詳しく)
17 を挿入したい
29 ＞ 17
29
だから…
20 ＞ 17
20
だから…
14 ＜ 17
14
24
32
30
48
だから…
19
7
19 ＞ 17
だから…
17
21
31
9
public class BinarySearchTree {
public BinarySearchTree() {
this.root = null;
二分探索木へ挿入するメソッド
}
public void insert(MyData aData) {
private MyNode root;
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();
}
}
10
}
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();
}
}
}
ループによる二分探索
11
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());
}
このような再帰呼び出しはループと相互に変換可能
12
子をもたない、または
１つだけ持つノードの削除
29
20
削除したい
削除
24
14
7
19
21
32
30
48
31
そのまま削除
削除したい
13
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;
削除対象を探す
14
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());
}
}
/* 続く… */
親
親
親
子
子
親
親
子
子
15
子を２つ持つノードの削除
29
削除したい
削除
20
14
7
24
19
21
32
30
48
31
16
}
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);
1. 右部分木から最小の(最左)
}else{
のノードを取り出す
parentNode.setRight(minimumNode);
2. 削除対象と付け替え
}
親
子
子
孫
親
子
子
孫
private MyNode getMinimumNode(MyNode aLocalRootNode){
if(null == aLocalRootNode){
return null;
}
MyNode currentNode = aLocalRootNode;
while(true){
if(null == currentNode.getLeft()){
return currentNode;
}
currentNode = currentNode.getLeft();
}
17
}
行きがけ順(pre-order)の走査
二分木を次のルールで走査
1. 自分を訪ねる
2. 自分の左部分木をたどる
3. 自分の右部分木をたどる
29
20
32
public void printTreePreOrder() {
System.out.println(this.traversePreOrder(this.root));
}
14
24
30
48
private String traversePreOrder(MyNode aLocalRootNode) {
if(null == aLocalRootNode){
return "";
}
7
19
21
31
StringBuffer treeRepresentation = new StringBuffer();
treeRepresentation.append(aLocalRootNode + System.getProperty("line.separator"));
treeRepresentation.append(this.traversePreOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(this.traversePreOrder(aLocalRootNode.getRight()));
18
return treeRepresentation.toString();
}
通りがけ順(in-order)の走査
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分を訪ねる
3. 自分の右部分木をたどる
29
二分探索木を走査すると
整列済みデータが得られる
20
32
20
32
public void printTreeInOrder() {
System.out.println(this.traverseInOrder(this.root));
}
private String traverseInOrder(MyNode 14
aLocalRootNode)
24 { 30
48
if(null == aLocalRootNode){
return "";
}
7 = new 19
21
31
21
StringBuffer treeRepresentation
StringBuffer();
treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(aLocalRootNode +System.getProperty("line.separator"));
treeRepresentation.append(this.traverseInOrder(aLocalRootNode.getRight()));
19
return treeRepresentation.toString();
}
帰りがけ順(post-order)の走査
二分木を次のルールで走査
1. 自分の左部分木をたどる
2. 自分の右部分木をたどる
3. 自分を訪ねる
29
20
32
public void printTreePostOrder() {
System.out.println(this.traversePostOrder(this.root));
}
14 aLocalRootNode)
24
30{
48
private String traversePostOrder(MyNode
if(null == aLocalRootNode){
return "";
}
7
19StringBuffer();
21
31
StringBuffer treeRepresentation
= new
treeRepresentation.append(this.traversePostOrder(aLocalRootNode.getLeft()));
treeRepresentation.append(this.traversePostOrder(aLocalRootNode.getRight()));
treeRepresentation.append(aLocalRootNode + System.getProperty("line.separator"));
20
return treeRepresentation.toString();
}

Download Report