001:import java.util.ArrayList;
002:
003:/**
004: * ２分探索木 Binary Search Tree
005: * @see <A HREF="http://www.geocities.jp/h2fujimura/mutter/tree/binary-search-tree.html">２分探索木</A>
006: * @auther Hikaru Fujimura
007: * @version 2005.08.25
008: */
009:public class BinaryTree<T extends Comparable> {
010:
011: T value; // データ
012: BinaryTree<T> parent; // 親のノード
013: BinaryTree<T> left; // 左部分木
014: BinaryTree<T> right; // 右部分木
015:
016:/** 部分木の生成 */
017: private BinaryTree(T v, BinaryTree<T> p, BinaryTree<T> l, BinaryTree<T> r) {
018: value = v;
019: parent = p;
020: left = l;
021: right = r;
022: }
023:
024:/**
025: * 要素 v だけをもつ２分探索木の生成します。
026: * 生成した木を部分木として、NIL とおきかえるには、
027: * setAsLeaf メソッドを使用してください。
028: * @param v 根に設定する値
029: */
030: BinaryTree(T v) {
031: if(v==null) throw new IllegalArgumentException();
032: value = v;
033: parent = null;
034: left = new BinaryTree<T>(null, this, null, null);
035: right = new BinaryTree<T>(null, this, null, null);
036: }
037:
038:/**
039: * 空木の生成します。
040: * NIL としても使われます。
041: */
042: BinaryTree() {
043: this(null, null, null, null);
044: }
045:
046:/**
047: * NIL の判定。
048: * @return value フィールドが null のとき true、そうでないとき false
049: */
050: boolean isNIL() { return value==null; }
051:
052:/**
053: * 根の判定。
054: * @return parent フィールドが null のとき true、そうでないとき false
055: */
056: boolean isRoot() { return parent==null; }
057:
058:/** 値の取得 */
059: T getValue() { return value; }
060:/** 親の取得 */
061: BinaryTree<T> getParent() { return parent; }
062:/** 左部分木の取得 */
063: BinaryTree<T> getLeft() { return left; }
064:/** 右部分木の取得 */
065: BinaryTree<T> getRight() { return right; }
066:
067:/**
068: * 値の設定。
069: * @throws IllegalArgumentException() パラメタが null の場合
070: */
071: void setValue(T v) {
072: if(v==null) throw new IllegalArgumentException("null");
073: value = v;
074: }
075:
076:/**
077: * 葉の作成。
078: * この部分木（通常 NIL）を v を値とする葉に書き換えます。
079: * parent フィールドは不変です。
080: * @throws IllegalArgumentException() パラメタが null の場合
081: */
082: BinaryTree<T> setAsLeaf(T v) {
083: if(v==null) throw new IllegalArgumentException("null");
084: value = v;
085: left = new BinaryTree<T>(null, this, null, null);
086: right = new BinaryTree<T>(null, this, null, null);
087: return this;
088: }
089:
090:/**
091: * 文字列としての値
092: */
093: public String toString() {
094: if(this.value==null) return "null";
095: return value.toString();
096: }
097:
098:/**
099: * 浅いコピー
100: */
101: public BinaryTree<T> clone() {
102: if(isNIL()) return new BinaryTree<T>();
103: else {
104: BinaryTree<T> newLeft = left.clone();
105: BinaryTree<T> newRight = right.clone();
106: BinaryTree<T> newNode = new BinaryTree<T>(value, null, newLeft, newRight);
107: newLeft.parent = newNode;
108: newRight.parent = newNode;
109: return newNode;
110: }
111: }
112:
113:/**
114: * 文字列への変換（デバッグ用）
115: */
116: String toLongString() {
117: if(isNIL()) return "NIL";
118: StringBuffer s = new StringBuffer("[");
119: if(value==null) s.append("null");
120: else s.append(value.toString());
121: s.append(",");
122: if(left==null) s.append("null");
123: else if(left.isNIL()) s.append("NIL");
124: else s.append(left.toLongString());
125: s.append(",");
126: if(right==null) s.append("null");
127: else if(right.isNIL()) s.append("NIL");
128: else s.append(right.toLongString());
129: s.append("]");
130: return s.toString();
131: }
132:
133:/**
134: * この木を ArrayList へ変換します。
135: * @return ノードの値を昇順に含む ArrayList
136: */
137: ArrayList<T> toArrayList() {
138: ArrayList<T> a = new ArrayList<T>();
139: if(isNIL()) return a;
140: a.addAll(left.toArrayList());
141: a.add(value);
142: a.addAll(right.toArrayList());
143: return a;
144: }
145:
146:/**
147: * この２分探索木をさがし、 値v を含む部分木を返します。
148: *
149: * @param v 探す値
150: * @return 根の値が v である部分木、または NIL （見つからない場合）
151: */
152: BinaryTree<T> search(T v) {
153: if(isNIL()) return this;
154: if(v.compareTo(value)<0) return left.search(v);
155: else if(v.compareTo(value)>0) return right.search(v);
156: else return this;
157: }
158:
159:/**
160: * この２分探索木に 値v を挿入します。
161: *
162: * @param v 挿入する値
163: * @return 元の２分探索木、空木に挿入した場合は新しい木
164: */
165: BinaryTree<T> insert(T v) {
166: if(isNIL()) return new BinaryTree<T>(v); // empty tree
167: BinaryTree<T> x = search(v); // search v
168: while(!x.isNIL()) { // found?
169: x = (x.right).search(v); // yes, check right subtree
170: }
171: x.setAsLeaf(v);
172: return this;
173: }
174:
175:/**
176: * この２分探索木から 値v を削除します。
177: *
178: * @param v 削除する値
179: * @return 元の２分探索木（削除後）
180: */
181: BinaryTree<T> delete(T v) {
182: if(isNIL()) return this; // empty tree
183: BinaryTree<T> t = search(v); // search
184: if(t.isNIL()) return this; // not found
185: if(t.left.isNIL() && t.right.isNIL()) { // no child
186: t.value = null; // change to NIL
187: t.left = null; //
188: t.right = null; //
189: return this; // only parent chain
190: }
191: if(t.left.isNIL()) { // no left subtree
192: t = t.replace(t.right); // replace here by right subtree
193: if(t.isRoot()) return t;
194: else return this;
195: }
196: if(t.right.isNIL()) { // no right subtree
197: t = t.replace(t.left); // replace here by left subtree
198: if(t.isRoot()) return t;
199: else return this;
200: } // now, t has 2 subtree
201: BinaryTree<T> x = t.left; // get smaller subtree
202: while(!x.right.isNIL()) { // as far as right subtree exist
203: x = x.right; // get greater value
204: } //
205: T prev = x.value; // maximun value that less than v
206: x.replace(x.left); // replace here by left
207: t.value = prev; // replace v
208: return this; // and return
209: }
210:
211:/**
212: * この部分木をパラメタに指定された部分木で置換します。
213: *
214: * @param t 部分木
215: * @return 元の２分探索木、または t （元の部分木が根の場合）
216: */
217: private BinaryTree<T> replace(BinaryTree<T> t) {
218: t.parent = parent;
219: if(this.isRoot()) return t;
220: if(parent.left==this) parent.left = t;
221: else parent.right = t;
222: return this;
223: }
224:
225:/**
226: * この木の指定された個所を右回転します。
227: * @param here 回転する中心のノード（部分木）
228: * @return 元の２分探索木（回転後）
229: */
230: BinaryTree<T> rotateRight(BinaryTree<T> here) {
231: if(isNIL()) return this;
232: if(here.left.isNIL()) return this;
233: boolean atRoot = false;
234: if(here.isRoot()) atRoot = true;
235: BinaryTree<T> father = here.parent;
236: BinaryTree<T> newTop = here.left;
237: here.parent = newTop;
238: here.left = here.left.right;
239: newTop.parent = father;
240: newTop.right = here;
241: if(atRoot) return newTop;
242: else {
243: if(father.left==here) father.left = newTop;
244: else father.right = newTop;
245: return this;
246: }
247: }
248:
249:/**
250: * この木の指定された個所を左回転します。
251: * @param here 回転する中心のノード（部分木）
252: * @return 元の２分探索木（回転後）
253: */
254: BinaryTree<T> rotateLeft(BinaryTree<T> here) {
255: if(isNIL()) return this;
256: if(here.right.isNIL()) return this;
257: boolean atRoot = false;
258: if(here.isRoot()) atRoot = true;
259: BinaryTree<T> father = here.parent;
260: BinaryTree<T> newTop = here.right;
261: here.parent = newTop;
262: here.right = here.right.left;
263: newTop.parent = father;
264: newTop.left = here;
265: if(atRoot) return newTop;
266: else {
267: if(father.left==here) father.left = newTop;
268: else father.right = newTop;
269: return this;
270: }
271: }
272:
273:/**
274: * 兄弟を取得します。
275: * @return 親の子で、自分でない方の部分木。 この木が根の場合は null を返します。
276: */
277: BinaryTree<T> getBrother() {
278: if(isRoot()) return null;
279: if(parent.left==this) return parent.right;
280: else return parent.left;
281: }
282:
283:/**
284: * 叔父を取得します。
285: * @return 親の親の子の内で、自分の親でない方の部分木、叔父までたどれない場合は null
286: */
287: BinaryTree<T> getUncle() {
288: if(isRoot()) return null;
289: if(parent.isRoot()) return null;
290: BinaryTree<T> grandPa = parent.parent;
291: if(grandPa.left.isNIL()) return null;
292: if(grandPa.left==parent) return grandPa.right;
293: else return grandPa.left;
294: }
295:}