Overview of the Tree ADT
Published , Updated
The following post is derived from notes taken while reading through this textbook .
The running-time of all of these methods assumes that the tree is using a linked structure.
Common Methods for Trees:
- root() - Return the tree's root-node. This is an O(1) operation.
- size() - Return the number of nodes in the tree. This is an O(1) operation.
- isEmpty() - Return whether-or-not the tree is empty. This is an O(1) operation.
- iterator() - Return an iterator of all the elements stored at nodes of the tree. This is an O(n) operation.
- positions() - Return an iterable collection of all the nodes of the tree. This is an O(n) operation.
- replace(Node n, Node m) - Save node n, replace node n with node m, and then return the saved node. This is an O(1) operation.
Common Methods for Tree Nodes:
- element() - Return the object stored in this node. This is an O(1) operation.
- parent(Node n) - Return the parent of the specified node. This is an O(1) operation.
- children(Node n) - Return an iterable collection containing the children of node n. This is an O(numberOfChildrenOfNodeN) operation.
- isInternal(Node n) - Return whether-or-not the specified node is internal. This is an O(1) operation.
- isExternal(Node n) - Return whether-or-not the specified node is external. This is an O(1) operation.
- isRoot(Node n) - Return whether-or-not the specified node is the root-node of the tree. This is an O(1) operation.
- Root - The root-node is the red node. This is because every other node branches from it.
- Edge - The blue line is an edge. An edge is a connection between two nodes.
- Path - A path is a sequence of nodes and edges that connect one node to another. The red node has a path to the orange node by going along the blue edge, then through the purple node, then along another edge before reaching the orange node.
- Leaf/External Node - The orange, yellow, and green nodes are all leaf nodes because they have no children.
- Parent - A parent is a node who has at-least one child. The red and purple nodes are parents because they have children.
- Child - A child is a node who has a parent. The orange and yellow nodes are children of their parent, the purple node. The purple and green nodes are children of their parent, the red node.
- Siblings - Children who share the same parent are siblings. The orange and yellow nodes are siblings because they share the purple node as a parent. The purple and green nodes are siblings because they share the red node as a parent.
The example image provided is not the only configuration for a tree. The nodes of a tree can contain as many children as you want, but there can only be one parent for each child.
Additional Information:
- For an implementation of a Tree in Java, you can use this and this together. These two classes do not include all of the methods mentioned in this post, but they are good for a general-purpose tree.
- Notable pages from the textbook:
- Page 281 - The formal definition of a Tree is at the bottom of the page.
- Page 286 - Some notes on using a linked structure with a tree.