Rekursive Datenstruktur

Implementierung

Baum wird in der Node selbst traversiert

public class TreeNode {
private int value;
private TreeNode left, right;
public TreeNode (int v) { value = v; }
public void add(int v) {
if (v < value) {
if (left != null) {
left.add(v);
} else {
left = new TreeNode(v);
}
} else if (v > value ) {
if (right != null) {
right.add(v);
} else {
right = new TreeNode(v);
}
}
}public boolean contains (int v) {
return v == value ||
(v < value ? left != null && left.contains(v) : right != null && right.contains(v));
}
}

public class STree {
private TreeNode root;
// add v if not already in the tree
public void add(int v) {
if (root == null) {
root = new TreeNode(v);
} else {
root.add(v);
}
}
// is v in the tree?
public boolean contains(int v) {
return root != null && root.contains(v);
}
}

Assoziative Datenstruktur: Map

x.compareTo(y) verwendet

Node:

public class TANode {
private String key, value;
private TANode left, right ;
public TANode(String k, String v) {
key = k;
value = v;
}
private int compare ( String k) {
if (k == null) { return key == null ? 0 : -1; }
if (key == null) { return 1; }
return k.compareTo(key);
}
public String put(String k, String v) {
int cmp = compare(k);
if (cmp < 0) {
if (left != null) { return left.put(k,v); }
left = new TANode (k,v);
} else if (cmp > 0) {
if ( right != null) { return right.put(k,v); }
right = new TANode (k,v);
} else {
String result = value;
value = v;
return result ;
}
return null;
}public TANode find(String k) {
int cmp = compare (k);
if (cmp == 0) { return this; }
TANode node = cmp < 0 ? left : right;
if ( node == null) { return null; }
return node.find(k);
}public boolean hasValue (String v) {
return (v == null ? value == v : v.equals(value)) ||
(left != null && left.hasValue (v)) ||
(right != null && right.hasValue (v));
}public String value() { return value; }
}

Map:

public class TreeAssoc {
private TANode root;
public String put(String k, String v) {
if (root != null) { return root.put(k,v); }
root = new TANode(k,v);
return null;
}
public String get(String k) {
if (root == null) { return null; }
TANode node = root.find(k);
return node == null ? null : node.value();
}
public boolean containsKey(String k) {
return root != null && root.find(k) != null;
}
public boolean containsValue(String v) {
return root != null && root.hasValue(v);
}}

Sortierter Baum

public interface Ordered extends Collection { }

import java.util.Arrays;public class OrderedTree implements Ordered {
private OTNode root;
private int [] cnt = new int[1];
public OrderedTree() {}
public OrderedTree(String [] elems) {
for ( String e : elems) { add(e); }
}
public OrderedTree( Iterable elems) {
for ( String e : elems) { add(e); }
}
public void add( String e) {
cnt [0]++;
if ( root != null) { root.add (e); }
else { root = new OTNode (e); }
}
public int contains ( String e) {
if ( root == null) { return 0; }
return root. contains (e);
}
public int removeAll ( String e) {
int oldcnt = cnt [0];
if ( root != null) { root = root.rmv(e, cnt ); }
return oldcnt - cnt [0];
}
public void clear () { root = null; cnt [0] = 0; }
public int size () { return cnt [0]; }
public String [] toArray () {
String [] array = new String [size ()];
toArray ( array );
return array ;
}
public int toArray ( String [] array) {
return root == null ? 0 : root.fill(array , 0);
}
public Iterator iterator () {
OTIter iter = new OTIter ();
if ( root != null) { root.iter(iter , false ); }
return iter;
}
public String toString () {
String res = "";
for ( String s : this)
res += (res. isEmpty () ? "" : ", ") + s;
return "{" + res + "}";
}
public boolean equals ( Object o) {
if ( this == o) { return true; }
if (o == null || o. getClass () != getClass ())
return false ;
OrderedTree t = ( OrderedTree)o;
return Arrays . equals (t. toArray (), toArray ());
}
public int hashCode () {
return 57 - Arrays . hashCode ( toArray ());
}
}

public class OTNode {
private String elem;
private OTNode left , right;
public OTNode ( String e) { elem = e; }
public int fill( String [] array , int i) {
if (left != null) { i = left. fill(array , i); }
if (i < array. length ) {
array[i++] = elem;
if (right != null)
i = right.fill(array ,i);
}
return i;
}
private int compare(String e) {
if (e == null) { return elem == e ? 0 : -1; }
return elem == null ? 1 : e.compareTo(elem);
}
public void add(String e) {
int cmp;
OTNode p, n = this;
do {
cmp = (p = n).compare(e);
n = cmp > 0 ? p.right : p.left;
} while (n != null);
if (cmp > 0) {
p.right = new OTNode (e);
} else {
p.left = new OTNode (e);
}
}public int contains(String e) {
int count = 0;
OTNode n = this;
do {
int cmp = n. compare (e);
if (cmp > 0) {
n = n.right;
} else {
n = n. left;
if (cmp == 0) { count ++; }
}
} while (n != null);
return count;
}public OTNode rmv( String e, int [] cnt) {
int cmp = compare (e);
if (cmp > 0) {
if ( right != null)
right = right.rmv(e, cnt );
} else {
if ( left != null) left = left.rmv(e, cnt );
if (cmp == 0) {
cnt [0] - -;
if ( left == null) { return right; }
OTNode p = left;
while (p.right != null) { p = p. right; }
p. right = right;
return left;
}
}
return this;
}public String iter(OTIter iter , boolean next) {
OTNode n = next ? right : this;
while (n != null) {
new OTIter (n, iter);
n = n. left;
}
return elem;
}
}

Sortierender Baum - Iterator

Zu kompliziert um nützlich zu sein. → Leichtere Implementierung möglich mit Linked List der man alle Werte hinzufügt beim traversieren.

Baum

	public Iterator iterator () {
OTIter iter = new OTIter();
if (root != null) { root.iter(iter , false); } //false - root gets chosen
return iter;
}

Node

public class OTNode {
private String elem;
private OTNode left, right;
public OTNode(String e) {
elem = e;
}
//...
public String iter(OTIter iter , boolean next) {
OTNode n = next ? right : this;
while (n != null) {
new OTIter(n, iter);
n = n.left;
}
return elem;
}
}

Iterator

public class OTIter implements Iterator {
private OTNode node; //node
private OTIter parent; //iteratorpublic OTIter() {}public OTIter(OTNode n, OTIter p) {
this.node = p.node;
p.node = n;
this.parent = p.parent;
p.parent = this;
}
public boolean hasNext() { return this.node != null; }
public String next() {
if (node == null) { return null; }
//this gets parents node, and parent gets removed
OTNode todo = this.node;
this.node = parent.node;
parent = parent.parent;
return todo.iter(this, true); //calls Node.iter
}
}

OTIter ist eigentlich eine singly linked list

Beispiel

OTIter pVal = new OTNode(...); //future val of childsParent
OTIter child = new OTITer(pVal, ...);
OTNode cVal = new OTNode(...); //future val of child
OTIter childsParent = new OTIter(val, child); 

After calling the constructor of OTITer:
/*
....
🠕	parent
┎---------------┒
| p.parent      |
|  ○ p.parent.node
┕---------------┚
🠕	parent
┎---------------┒
| this          |
|  ○ p.node     |
┕---------------┚
🠕	parent
┎---------------┒
| p             |
|  ○ n          |
┕---------------┚p{n} --parent--> this{p.node} --parent--> p.parent{p.parent.node} ...
*/

AVL-Tree Node

public class OTNode {
private String elem;
private OTNode left, right;
private int balance = 0;public OTNode add(String e) {
if (compare(e) > 0) {
if (right == null) {
right = new OTNode(e);
++balance;
} else {
OTNode n = right.add(e);
if (n != null) {
right = n;
return this;
}
if (++balance > 1) {
if (right.balance > 0) {
n = right;
balance = 0;
} else {
n = right.left;
balance = right.balance = 0;
if (n.balance > 0) {
balance = -1;
} else if (n.balance < 0) {
right.balance = 1;
}
right.left = n.right;
n.right = right;
}
n.balance = 0;
right = n.left;
n.left = this;
return n;
}
}
} else { // Symmetrischer Zweig für linken Teilbaum
}
return balance != 0 ? null : this;
}
}

public class OrderedTree implements Ordered {
...
public void add(String e) {
cnt[0]++;
if (root != null) {
OTNode n = root.add(e);
if (n != null) {
root = n;
}
} else {
root = new OTNode(e);
}
}public int removeAll (String e) { ... };
}