EvbCFfp1XB

problem and my answer.

July 2012

import java.util.LinkedList;

/**
* Chapter 15. Balanced Tree - Problem1 - Robert Sedgewick Algorithms in C++<br>
* 空の木に、キーEASYQUESTIONをこの順に挿入した結果えられる2-3-4木を描け。
*/
public class Chapter15BalancedTreeProblem1 {
public static void main(String[] args) {
long start = System.nanoTime();
TwoTreeFourTree ttft = new TwoTreeFourTree();
String s = "EASYQUESTION";
for (int i = 0; i < s.length(); i++) {
System.out.format("---\n");
ttft.insert(s.substring(i, i + 1));
ttft.print();
}
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

public static class TwoTreeFourTree {
Node root = new Node();

public void insert(String key) {
insert(root, key);
}

private void insert(Node n, String key) {
if (n.key.size() == 3) {
String centerkey = n.key.get(1);
Node p = n.parent;
if (p == null) {
p = new Node();
n.parent = p;
p.child.add(n);
root = p;
}
Node l = new Node();
l.key.add(n.key.get(0));
if (n.child.size() >= 1) {
l.child.add(n.child.get(0));
}
if (n.child.size() >= 2) {
l.child.add(n.child.get(1));
}
l.parent = p;

Node r = new Node();
r.key.add(n.key.get(2));
if (n.child.size() >= 3) {
r.child.add(n.child.get(2));
}
if (n.child.size() >= 4) {
r.child.add(n.child.get(3));
}
r.parent = p;

int indexn = p.child.indexOf(n);
p.child.remove(n);
p.child.add(indexn < 0 ? 0 : indexn, r);
p.child.add(indexn < 0 ? 0 : indexn, l);

boolean add = false;
for (int i = 0; i < p.key.size(); i++) {
if (centerkey.compareTo(p.key.get(i)) < 0) {
p.key.add(i, centerkey);
add = true;
break;
}
}
if (!add) {
p.key.addLast(centerkey);
}
resetParent(p);
insert(p, key);
return;
}

for (int i = 0; i < n.key.size(); i++) {
if (key.compareTo(n.key.get(i)) < 0) {
if (n.child.size() <= i) {
n.key.add(i, key);
return;
} else {
insert(n.child.get(i), key);
return;
}
}
}
if (n.child.size() <= n.key.size()) {
n.key.add(n.key.size(), key);
return;
} else {
insert(n.child.get(n.key.size()), key);
return;
}
}

private void resetParent(Node n) {
for (int i = 0; i < n.child.size(); i++) {
n.child.get(i).parent = n;
resetParent(n.child.get(i));
}
}

public void print() {
traverseInorder(root, 0);
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
for (int l = 0; !queue.isEmpty();) {
Node p = queue.poll();
if (p == null) {
continue;
}
if (p.level != l) {
l = p.level;
System.out.format("\n");
}
System.out.format("%s", p.keys());
for (int i = 0; i < p.child.size(); i++) {
queue.add(p.child.get(i));
}
}
System.out.format("\n");
}

private void traverseInorder(Node n, int level) {
if (n != null) {
n.level = level;
for (int i = 0; i < n.child.size(); i++) {
traverseInorder(n.child.get(i), level + 1);
}
}
}
}

public static class Node {
public Node parent;
public LinkedList<Node> child = new LinkedList<Node>();
public LinkedList<String> key = new LinkedList<String>();
public int level;

public String keys() {
StringBuilder sb = new StringBuilder();
sb.append("(");
for (int i = 0; i < key.size(); i++) {
sb.append(key.get(i));
}
sb.append(")");
return sb.toString();
}
}
}

import java.util.LinkedList;

/**
* Chapter 14. Elementary Searching - Problem10 - Robert Sedgewick Algorithms in
* C++<br>
* 空な木に、キーEASYQUESTIONを挿入し、Qを削除したときの2分探索木を示せ。
*/
public class Chapter14ElementarySearchingProblem10 {
public static void main(String[] args) {
long start = System.nanoTime();
String s = "EASYQUESTION";
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < s.length(); i++) {
bst.insert(s.substring(i, i + 1));
}
bst.print();
int r = (int) (s.length() * Math.random());
System.out.format("delete %s\n", s.substring(r, r + 1));
bst.delete(s.substring(r, r + 1));
bst.print();
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

public static class BinarySearchTree {
Node root = new Node();

public void insert(String key) {
insert(root, key);
}

private void insert(Node n, String key) {
if (n.key == null) {
n.key = key;
return;
}
if (key.compareTo(n.key) < 0) {
if (n.l == null) {
n.l = new Node();
}
insert(n.l, key);
} else {
if (n.r == null) {
n.r = new Node();
}
insert(n.r, key);
}
}

public void delete(String key) {
Node p = new Node();
p.key = "";
p.r = root;
Node x = root;
for (; x.key.compareTo(key) != 0;) {
p = x;
x = x.key.compareTo(key) > 0 ? x.l : x.r;
}
Node t = x;
if (t.r == null) {
x = x.l;
} else if (t.r.l == null) {
x = x.r;
x.l = t.l;
} else {
Node c = x.r;
while (c.l.l != null) {
c = c.l;
}
x = c.l;
c.l = x.r;
x.l = t.l;
x.r = t.r;
}
if (key.compareTo(p.key) < 0) {
p.l = x;
} else {
p.r = x;
}
}

public void print() {
traverseInorder(root, 0, 0);
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
for (int l = 0, o = 0; !queue.isEmpty();) {
Node p = queue.poll();
if (p == null) {
continue;
}
if (p.level != l) {
l = p.level;
o = 0;
System.out.format("\n");
}
System.out.format("%" + (p.key.length() + p.order - o) + "s",
p.key);
o = p.key.length() + p.order;
queue.add(p.l);
queue.add(p.r);
}
System.out.format("\n");
}

private int traverseInorder(Node e, int level, int order) {
if (e != null) {
order = traverseInorder(e.l, level + 1, order);
e.level = level;
e.order = order++;
order = traverseInorder(e.r, level + 1, order);
}
return order;
}
}

public static class Node {
public String key;
public Node l;
public Node r;
public int level;
public int order;
}
}

import java.util.LinkedList;

/**
* Chapter 14. Elementary Searching - Problem9 - Robert Sedgewick Algorithms in
* C++<br>
* 2分探索木中のキーを、キーの順に書き出す再帰的でないプログラムを書け。
*/
public class Chapter14ElementarySearchingProblem9 {
public static void main(String[] args) {
long start = System.nanoTime();
BinarySearchTree bst = new BinarySearchTree();
for (int i = 0; i < 100; i++) {
bst.insert("" + (char) ('a' + (('z' - ('a' - 1)) * Math.random())));
}
bst.print();
bst.printKeys();
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

public static class BinarySearchTree {
Node root = new Node();

public void insert(String key) {
insert(root, key);
}

private void insert(Node n, String key) {
if (n.key == null) {
n.key = key;
return;
}
if (key.compareTo(n.key) < 0) {
if (n.l == null) {
n.l = new Node();
}
insert(n.l, key);
} else if (key.compareTo(n.key) > 0) {
if (n.r == null) {
n.r = new Node();
}
insert(n.r, key);
} else {
Node node = new Node();
node.key = key;
node.r = n.r;
n.r = node;
}
}

public void print() {
traverseInorder(root, 0, 0);
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
for (int l = 0, o = 0; !queue.isEmpty();) {
Node p = queue.poll();
if (p == null) {
continue;
}
if (p.level != l) {
l = p.level;
o = 0;
System.out.format("\n");
}
System.out.format("%" + (p.key.length() + p.order - o) + "s",
p.key);
o = p.key.length() + p.order;
queue.add(p.l);
queue.add(p.r);
}
System.out.format("\n");
}

private int traverseInorder(Node e, int level, int order) {
if (e != null) {
order = traverseInorder(e.l, level + 1, order);
e.level = level;
e.order = order++;
order = traverseInorder(e.r, level + 1, order);
}
return order;
}

public void printKeys() {
LinkedList<Node> stack = new LinkedList<Node>();
Node e = root;
while (e != null) {
stack.addLast(e);
e = e.l;
}
while (!stack.isEmpty()) {
e = stack.pollLast();
System.out.format("%s", e.key);
e = e.r;
while (e != null) {
stack.addLast(e);
e = e.l;
}
}
System.out.println();
}
}

public static class Node {
public String key;
public Node l;
public Node r;
public int level;
public int order;
}
}

import java.util.LinkedList;

/**
* Chapter 14. Elementary Searching - Problem8 - Robert Sedgewick Algorithms in
* C++<br>
* 等しいキーが一緒になる(与えられた節点のキーと同じキーをもつ他の節点は、その親かあるいは子のうちの1つがそのキーと等しいキーもつ)
* ように2分探索木を修正せよ。
*/
public class Chapter14ElementarySearchingProblem8 {
public static void main(String[] args) {
long start = System.nanoTime();
BinarySearchTree bst = new BinarySearchTree();
for (int j = 0; j < 100; j++) {
bst.insert("" + (char) ('a' + (('z' - ('a' - 1)) * Math.random())));
}
bst.print();
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

public static class BinarySearchTree {
Node root = new Node();

public void insert(String key) {
insert(root, key);
}

private void insert(Node n, String key) {
if (n.key == null) {
n.key = key;
return;
}
if (key.compareTo(n.key) < 0) {
if (n.l == null) {
n.l = new Node();
}
insert(n.l, key);
} else if (key.compareTo(n.key) > 0) {
if (n.r == null) {
n.r = new Node();
}
insert(n.r, key);
} else {
Node node = new Node();
node.key = key;
node.r = n.r;
n.r = node;
}
}

public void print() {
traverseInorder(root, 0, 0);
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
for (int l = 0, o = 0; !queue.isEmpty();) {
Node p = queue.poll();
if (p == null) {
continue;
}
if (p.level != l) {
l = p.level;
o = 0;
System.out.format("\n");
}
System.out.format("%" + (p.key.length() + p.order - o) + "s",
p.key);
o = p.key.length() + p.order;
queue.add(p.l);
queue.add(p.r);
}
System.out.format("\n");
}

private int traverseInorder(Node e, int level, int order) {
if (e != null) {
order = traverseInorder(e.l, level + 1, order);
e.level = level;
e.order = order++;
order = traverseInorder(e.r, level + 1, order);
}
return order;
}
}

public static class Node {
public String key;
public Node l;
public Node r;
public int level;
public int order;
}
}

import java.util.LinkedList;

/**
* Chapter 14. Elementary Searching - Problem7 - Robert Sedgewick Algorithms in
* C++<br>
* 各キーの参照頻度の推定値が前もって与えられているとする。キーを推定頻度の高い方から挿入する方がよいか、低い方がよいか。その理由も示せ。
*/
public class Chapter14ElementarySearchingProblem7 {
public static void main(String[] args) {
long start = System.nanoTime();
int[] a = new int['z' - ('a' - 1)];
for (int i = 0; i < a.length; i++) {
a[i] = 'a' + i;
}
for (int ai = a.length - 1; ai >= 0; ai--) {
int i = (int) ((ai + 1) * Math.random());
int s = a[ai];
a[ai] = a[i];
a[i] = s;
}
BinarySearchTree bst = new BinarySearchTree();
for (int i = a.length - 1; i >= 0; i--) {
bst.insert("" + (char) a[i]);
}
bst.print();
System.out.format("height : %d\n", bst.height());
System.out.format("高い方\n");
bst.count = 0;
for (int i = a.length - 1, loop = 'z' - ('a' - 1); i >= 0; i--, loop--) {
for (int j = 0; j < loop; j++) {
bst.search("" + (char) a[i]);
}
}
System.out.format("search : %d\n", bst.count);
System.out.format("低い方\n");
bst.count = 0;
for (int i = a.length - 1, loop = 1; i >= 0; i--, loop++) {
for (int j = 0; j < loop; j++) {
bst.search("" + (char) a[i]);
}
}
System.out.format("search : %d\n", bst.count);
System.out.format("%f\n", (System.nanoTime() - start) / 1e9);
}

public static class BinarySearchTree {
Node root = new Node();

public void insert(String key) {
insert(root, key);
}

public int height() {
return height(root, 0);
}

private int height(Node e, int height) {
if (e != null) {
height = Math.max(height(e.l, height + 1),
height(e.r, height + 1));
}
return height;
}

private void insert(Node n, String key) {
if (n.key == null) {
n.key = key;
return;
}
if (key.compareTo(n.key) < 0) {
if (n.l == null) {
n.l = new Node();
}
insert(n.l, key);
} else {
if (n.r == null) {
n.r = new Node();
}
insert(n.r, key);
}
}

public void search(String key) {
search(root, key);
}

int count = 0;

private void search(Node n, String key) {
count++;
if (key.compareTo(n.key) == 0) {
return;
}
if (key.compareTo(n.key) < 0) {
search(n.l, key);
} else {
search(n.r, key);
}
}

public void print() {
traverseInorder(root, 0, 0);
LinkedList<Node> queue = new LinkedList<Node>();
queue.add(root);
for (int l = 0, o = 0; !queue.isEmpty();) {
Node p = queue.poll();
if (p == null) {
continue;
}
if (p.level != l) {
l = p.level;
o = 0;
System.out.format("\n");
}
System.out.format("%" + (p.key.length() + p.order - o) + "s",
p.key);
o = p.key.length() + p.order;
queue.add(p.l);
queue.add(p.r);
}
System.out.format("\n");
}

private int traverseInorder(Node e, int level, int order) {
if (e != null) {
order = traverseInorder(e.l, level + 1, order);
e.level = level;
e.order = order++;
order = traverseInorder(e.r, level + 1, order);
}
return order;
}
}

public static class Node {
public String key;
public Node l;
public Node r;
public int level;
public int order;
}
}

このページのトップヘ