0
# Tree Implementations
1

2
Specialized hierarchical graph structures with parent-child relationships and tree-specific operations. These implementations provide efficient tree modeling with support for single trees, forests (collections of trees), and ordered k-ary trees with indexed child access.
3

4
## Capabilities
5

6
### DelegateTree
7

8
Single tree implementation with a designated root vertex and hierarchical parent-child relationships.
9

10
```java { .api }
11
/**
12
 * An implementation of Tree that delegates to a specified instance of DirectedGraph.
13
 * Maintains tree constraints and provides tree-specific operations.
14
 */
15
public class DelegateTree<V,E> extends GraphDecorator<V,E> implements Tree<V,E> {
16
    
17
    /**
18
     * Creates an instance with default DirectedSparseGraph backend
19
     */
20
    public DelegateTree();
21
    
22
    /**
23
     * Creates an instance with specified graph factory
24
     * @param graphFactory Supplier for creating the underlying directed graph
25
     */
26
    public DelegateTree(Supplier<DirectedGraph<V,E>> graphFactory);
27
    
28
    /**
29
     * Creates a new DelegateTree which delegates to the specified graph
30
     * @param graph The underlying directed graph to use
31
     */
32
    public DelegateTree(DirectedGraph<V,E> graph);
33
    
34
    /**
35
     * Returns a Supplier that creates instances of this tree type
36
     * @return Factory supplier for DelegateTree instances
37
     */
38
    public static <V,E> Supplier<Tree<V,E>> getFactory();
39
    
40
    // Tree-specific edge addition (maintains tree constraints)
41
    public boolean addEdge(E e, V v1, V v2, EdgeType edgeType); // v1=parent, v2=child
42
    public boolean addEdge(E e, V v1, V v2);
43
    public boolean addChild(E edge, V parent, V child, EdgeType edgeType);
44
    public boolean addChild(E edge, V parent, V child);
45
    
46
    // Vertex operations
47
    public boolean addVertex(V vertex);  // Sets root if tree is empty
48
    public boolean removeVertex(V vertex); // Removes vertex and all descendants
49
    
50
    // Tree navigation
51
    public V getRoot();
52
    public void setRoot(V root); // Only if root is previously unset
53
    public V getParent(V child);
54
    public Collection<V> getChildren(V parent);
55
    public int getChildCount(V parent);
56
    public Collection<E> getChildEdges(V vertex);
57
    public E getParentEdge(V vertex);
58
    
59
    // Tree structure queries
60
    public List<V> getPath(V vertex);  // Path from root to vertex
61
    public int getDepth(V v);          // Depth from root
62
    public int getHeight();            // Height of entire tree
63
    public boolean isRoot(V v);
64
    public boolean isLeaf(V v);
65
    public boolean isInternal(V v);    // Neither root nor leaf
66
    
67
    // Tree operations
68
    public boolean removeChild(V orphan); // Removes vertex and all descendants
69
    public Collection<Tree<V,E>> getTrees(); // Returns singleton collection
70
    
71
    // Graph interface compliance
72
    public int getIncidentCount(E edge); // Always returns 2
73
    public boolean addEdge(E edge, Collection<? extends V> vertices);
74
    public String toString();
75
}
76
```
77

78
**Usage Examples:**
79

80
```java
81
import edu.uci.ics.jung.graph.DelegateTree;
82
import edu.uci.ics.jung.graph.Tree;
83

84
// Create a tree
85
Tree<String, String> tree = new DelegateTree<>();
86

87
// Add root vertex
88
tree.addVertex("root");
89
tree.setRoot("root");
90

91
// Add children to root
92
tree.addChild("edge1", "root", "child1");
93
tree.addChild("edge2", "root", "child2");
94

95
// Add grandchildren
96
tree.addChild("edge3", "child1", "grandchild1");
97
tree.addChild("edge4", "child1", "grandchild2");
98

99
// Tree navigation
100
String root = tree.getRoot();                    // "root"
101
Collection<String> children = tree.getChildren("root"); // ["child1", "child2"]
102
String parent = tree.getParent("child1");        // "root"
103

104
// Tree structure queries
105
int depth = tree.getDepth("grandchild1");        // 2
106
int height = tree.getHeight();                   // 2
107
boolean isLeaf = tree.isLeaf("grandchild1");     // true
108
boolean isInternal = tree.isInternal("child1");  // true
109

110
// Path operations
111
List<String> path = tree.getPath("grandchild1"); // ["root", "child1", "grandchild1"]
112

113
// Tree modification
114
tree.removeChild("child1"); // Removes child1 and all its descendants
115
```
116

117
### DelegateForest
118

119
Forest implementation supporting multiple trees (a collection of trees) with forest-specific operations.
120

121
```java { .api }
122
/**
123
 * An implementation of Forest that delegates to a specified DirectedGraph instance.
124
 * Manages multiple trees within a single forest structure.
125
 */
126
public class DelegateForest<V,E> extends GraphDecorator<V,E> implements Forest<V,E> {
127
    
128
    /**
129
     * Creates an instance backed by a new DirectedSparseGraph
130
     */
131
    public DelegateForest();
132
    
133
    /**
134
     * Creates an instance backed by the input DirectedGraph
135
     * @param delegate The underlying directed graph to use
136
     */
137
    public DelegateForest(DirectedGraph<V,E> delegate);
138
    
139
    // Forest-specific edge addition
140
    public boolean addEdge(E e, V v1, V v2, EdgeType edgeType); // v1=parent, v2=child
141
    public boolean addVertex(V vertex); // Adds vertex as a root
142
    
143
    // Edge and vertex removal with subtree handling
144
    public boolean removeEdge(E edge); // Removes edge and subtree
145
    public boolean removeEdge(E edge, boolean remove_subtree);
146
    public boolean removeVertex(V vertex); // Removes vertex and subtree
147
    public boolean removeVertex(V vertex, boolean remove_subtrees);
148
    
149
    // Forest navigation
150
    public Collection<V> getRoots(); // Roots of all trees in forest
151
    public Collection<Tree<V,E>> getTrees(); // All trees in the forest
152
    public void addTree(Tree<V,E> tree); // Add entire tree to forest
153
    
154
    // Tree operations (work on individual trees within forest)  
155
    public V getParent(V child);
156
    public Collection<V> getChildren(V v);
157
    public int getChildCount(V vertex);
158
    public Collection<E> getChildEdges(V vertex);
159
    public E getParentEdge(V vertex);
160
    
161
    // Tree structure queries
162
    public List<V> getPath(V child); // Path from root to vertex
163
    public V getRoot(); // Returns root if forest has single tree, null otherwise
164
    public void setRoot(V root); // Adds root as a root of the forest
165
    public boolean removeChild(V orphan);
166
    public int getDepth(V v);
167
    public int getHeight();
168
    public boolean isInternal(V v);
169
    public boolean isLeaf(V v);
170
    public boolean isRoot(V v);
171
    
172
    // Graph interface compliance
173
    public int getIncidentCount(E edge); // Always returns 2
174
    public boolean addEdge(E edge, Collection<? extends V> vertices);
175
}
176
```
177

178
**Usage Examples:**
179

180
```java
181
import edu.uci.ics.jung.graph.DelegateForest;
182
import edu.uci.ics.jung.graph.Forest;
183

184
// Create a forest
185
Forest<String, String> forest = new DelegateForest<>();
186

187
// Add multiple trees
188
forest.addVertex("root1");  // First tree root
189
forest.addVertex("root2");  // Second tree root
190

191
// Build first tree
192
forest.addEdge("edge1", "root1", "child1");
193
forest.addEdge("edge2", "root1", "child2");
194

195
// Build second tree  
196
forest.addEdge("edge3", "root2", "child3");
197
forest.addEdge("edge4", "root2", "child4");
198

199
// Forest queries
200
Collection<String> roots = forest.getRoots();    // ["root1", "root2"]
201
Collection<Tree<String,String>> trees = forest.getTrees(); // 2 trees
202

203
// Individual tree operations work within forest context
204
Collection<String> children1 = forest.getChildren("root1"); // ["child1", "child2"]
205
String parent = forest.getParent("child3");      // "root2"
206

207
// Forest modification
208
forest.removeVertex("root1", true); // Removes entire first tree
209
```
210

211
### OrderedKAryTree
212

213
Specialized tree implementation where each vertex has at most k children, with indexed access to children by position.
214

215
```java { .api }
216
/**
217
 * An implementation of Tree in which each vertex has ≤ k children.
218
 * A specific child can be retrieved directly by specifying the index 
219
 * at which the child is located.
220
 */
221
public class OrderedKAryTree<V,E> extends AbstractTypedGraph<V,E> implements Tree<V,E> {
222
    
223
    /**
224
     * Creates a new instance with the specified order (maximum number of children)
225
     * @param order Maximum number of children per vertex
226
     */
227
    public OrderedKAryTree(int order);
228
    
229
    /**
230
     * Returns a Supplier that creates instances with specified order
231
     * @param order Maximum children per vertex for created instances
232
     * @return Factory supplier for OrderedKAryTree instances
233
     */
234
    public static <V,E> Supplier<DirectedGraph<V,E>> getFactory(final int order);
235
    
236
    // Indexed child operations
237
    public V getChild(V vertex, int index);  // Get child at specific index
238
    public E getChildEdge(V vertex, int index); // Get edge to child at index
239
    public boolean addEdge(E e, V parent, V child, int index); // Add at specific position
240
    public boolean addEdge(E e, V parent, V child); // Add at next available position
241
    
242
    // Tree structure
243
    public int getChildCount(V vertex);
244
    public Collection<E> getChildEdges(V vertex);
245
    public Collection<V> getChildren(V vertex); // Returns ordered list
246
    public V getParent(V vertex);
247
    public E getParentEdge(V vertex);
248
    public V getRoot();
249
    public Collection<Tree<V,E>> getTrees();
250
    
251
    // Tree measurements
252
    public int getDepth(V vertex);
253
    public int getHeight(); // Returns -1 if empty
254
    
255
    // Tree predicates
256
    public boolean isLeaf(V vertex);
257
    public boolean isRoot(V vertex);
258
    
259
    // Edge operations with tree constraints
260
    public boolean addEdge(E e, V v1, V v2, EdgeType edge_type);
261
    public boolean addEdge(E edge, Collection<? extends V> vertices, EdgeType edge_type);
262
    public boolean addEdge(E edge, Pair<? extends V> endpoints, EdgeType edgeType);
263
    
264
    // Vertex operations
265
    public boolean addVertex(V vertex); // Adds as root only if no root exists
266
    public boolean removeEdge(E edge);  // Removes edge and subtree rooted at child
267
    public boolean removeVertex(V vertex); // Removes vertex and all descendants
268
    
269
    // Directional graph interface (tree-specific implementations)
270
    public V getDest(E directed_edge);
271
    public Pair<V> getEndpoints(E edge);
272
    public Collection<E> getInEdges(V vertex);  // Parent edge or empty
273
    public V getOpposite(V vertex, E edge);
274
    public Collection<E> getOutEdges(V vertex); // Child edges
275
    public int getPredecessorCount(V vertex);   // 0 for root, 1 for others
276
    public Collection<V> getPredecessors(V vertex); // Parent or empty
277
    public V getSource(E directed_edge);
278
    public int getSuccessorCount(V vertex);     // Number of children
279
    public Collection<V> getSuccessors(V vertex); // Children
280
    
281
    // Graph queries
282
    public int inDegree(V vertex);   // 0 for root, 1 for others
283
    public boolean isDest(V vertex, E edge);
284
    public boolean isPredecessor(V v1, V v2);
285
    public boolean isSource(V vertex, E edge);
286
    public boolean isSuccessor(V v1, V v2);
287
    public int outDegree(V vertex);  // Number of children
288
    
289
    // Standard graph interface
290
    public boolean isIncident(V vertex, E edge);
291
    public boolean isNeighbor(V v1, V v2);
292
    public boolean containsEdge(E edge);
293
    public boolean containsVertex(V vertex);
294
    public E findEdge(V v1, V v2);
295
    public Collection<E> findEdgeSet(V v1, V v2);
296
    public int getEdgeCount();
297
    public Collection<E> getEdges();
298
    public int getIncidentCount(E edge); // Always returns 2
299
    public Collection<E> getIncidentEdges(V vertex);
300
    public Collection<V> getIncidentVertices(E edge);
301
    public int getNeighborCount(V vertex);
302
    public Collection<V> getNeighbors(V vertex);
303
    public int getVertexCount();
304
    public Collection<V> getVertices();
305
}
306
```
307

308
**Usage Examples:**
309

310
```java
311
import edu.uci.ics.jung.graph.OrderedKAryTree;
312
import edu.uci.ics.jung.graph.Tree;
313

314
// Create a binary tree (k=2)
315
OrderedKAryTree<String, String> binaryTree = new OrderedKAryTree<>(2);
316

317
// Add root
318
binaryTree.addVertex("root");
319

320
// Add children at specific positions
321
binaryTree.addEdge("leftEdge", "root", "leftChild", 0);   // Index 0 (left)
322
binaryTree.addEdge("rightEdge", "root", "rightChild", 1); // Index 1 (right)
323

324
// Add children at next available position
325
binaryTree.addEdge("edge1", "leftChild", "grandchild1"); // Next available: index 0
326

327
// Indexed access
328
String leftChild = binaryTree.getChild("root", 0);       // "leftChild"
329
String rightChild = binaryTree.getChild("root", 1);      // "rightChild"
330
String noChild = binaryTree.getChild("root", 2);         // null (no child at index 2)
331

332
// Tree structure
333
int childCount = binaryTree.getChildCount("root");       // 2
334
Collection<String> children = binaryTree.getChildren("root"); // Ordered: ["leftChild", "rightChild"]
335

336
// Tree constraints enforced
337
// binaryTree.addEdge("edge3", "root", "thirdChild", 2); // Would fail: exceeds k=2 limit
338
```
339

340
## Tree Constraints and Validation
341

342
### Single Root Constraint
343

344
All tree implementations enforce single root constraints:
345
- DelegateTree: Only one root vertex allowed
346
- DelegateForest: Multiple roots allowed (one per tree)
347
- OrderedKAryTree: Single root, additional vertices must be children
348

349
### Acyclic Structure
350

351
Trees prevent cycle formation:
352
- Adding edges that would create cycles is rejected
353
- Parent-child relationships are strictly hierarchical
354
- No vertex can be an ancestor of itself
355

356
### Edge Type Constraints
357

358
Tree implementations use directed edges to represent parent-child relationships:
359
- All edges are implicitly directed (parent → child)
360
- EdgeType.DIRECTED is enforced for tree edges
361

362
## Performance Characteristics
363

364
### DelegateTree
365
- **Space Complexity**: O(V + E) = O(V) since E = V-1 in trees
366
- **Tree Operations**: O(1) for parent/child queries with cached depth information
367
- **Path Operations**: O(depth) for getPath operations
368

369
### DelegateForest
370
- **Multiple Trees**: Efficient management of forest structure
371
- **Tree Isolation**: Operations on one tree don't affect others
372

373
### OrderedKAryTree
374
- **Indexed Access**: O(1) child access by index
375
- **Order Constraint**: Enforces k-ary constraint at insertion time
376
- **Memory Overhead**: Additional storage for maintaining child order
377

378
## Common Use Cases
379

380
### DelegateTree
381
- Organizational hierarchies, file system structures, decision trees
382
- Taxonomy classifications, parse trees, expression trees
383

384
### DelegateForest
385
- Multiple classification systems, disconnected hierarchies
386
- Spanning forests, collections of organizational structures
387

388
### OrderedKAryTree
389
- Binary trees, heaps, B-trees, game trees
390
- Ordered taxonomies, indexed hierarchical data
391
- Any scenario requiring positional child access