121 Week 17 - Trees Flashcards
Tree
A nonlinear abstract data type which stores elements hierarchically.
It is made up of nodes connected by edges.
It does not have any cycles or loops.
Applications for trees
Management structure of organisation, directory structure, computer document formats (e.g., XML/ HTML), compilation (compiler turning source code into an abstract syntax tree), physic simulations, image processing and game design.
Tree structure
First, uppermost node is called the root node.
Nodes coming off from a node are called children.
A node with children coming off from it is called a parent node
Nodes without any children are called leaf nodes.
Ancestors and descendants
Descendants of a node are all nodes that have come off from that node, including children, until you reach leaf nodes. All nodes are descendants of the root.
A node is an ancestor node if it is a parent at some point up the tree of the node. The root is the ancestor to all nodes.
Distances in trees
Height of a node: number of nodes on longest path from v to some leaf.
Depth of a node: number of nodes from v to root.
Level i: contains all nodes at depth i.
Height of a tree: the height of the root/ the depth of the deepest node.
Diameter/width of a tree: number of nodes on longest path between any two leaves.
Number of edges of a tree
Trees have a fixed number of edges - for a tree with n nodes, the number of edges will always be n-1.
Subtrees
A subtree is a smaller part of an original tree that contains a node and and all of its descendants.
For any tree and node v, you can take a subtree rooted at v by taking v and all its descendants.
V will be the root of the subtree.
K-aray tree
A k-array means that each node can have a maximum of k children.
E.g., a 3-ary tree cannot have more than 3 children per node.
Binary tree
A tree where each node can only have 2 children.
Balanced tree
A tree where for any node, the heights of its child subtrees differ by ≤1
Tree ADT operations
void add(Object n, Object m)
Tree find(Object n)
Tree remove(Object n)
void move(Object n, Object m)
For adding and removing, the new parent node is always the second argument.
Node finding
Cannot just sequentially iterate through the tree.
Instead check if root node is the node we are looking for.
If it isn’t, call recursively on the children until node is found or all nodes have been searched but the node has not been found.
Node adding
Check if the parent node exists.
If it does, create a new node and add this as a child to the parent node.
Then add the parent node as a parent of the new node.
Node removal
Find the node to remove.
If it is the root, replace the root with its first child node. The children of the first child of the old root become children of the new root.
If it is not the root and has no children, just remove the node.
If it is not the root and has children, rewire so the children of the removed node become children of the parent of the removed node.
Node moving
Find node to move
Remove the node.
Find the new parent using the second parameter.
If the parent exists, add the node to move to the parent node.
Traversals
Tree traversals traverse through the tree and output the nodes.
Preoder, postorder, inorder, level order traversals can enumerate all elements, or decide in which way we look through the tree to find elements.
Pre-order tree tree traversal
It is a DFS traversal (depth-first search)
Method:
1. Look at the roots value.
2. Do a pre-order traversal the leftmost subtree from the root.
3. Do a pre-order traversal on the next leftmost subtree from the root. Continue to the next leftmost subtree until all subtrees have been traversed.
In-order tree tree traversal
It is a DFS traversal (depth-first search)
Method:
1. Do an in-order traversal the leftmost subtree from the root.
2. Look at the roots value.
2. Do an in-order traversal on the next leftmost subtree from the root. Continue to the next leftmost subtree until all subtrees have been traversed.
Post-order tree tree traversal
It is a DFS traversal (depth-first search)
Method:
1. Do a post-order traversal the leftmost subtree from the root.
2. Do a post-order traversal on the next leftmost subtree from the root. Continue to the next leftmost subtree until all subtrees have been traversed.
3. After all subtrees have been traversed, look at the roots value.
Breadth-first search tree traversal
Reads all nodes in a tree left to right at each level starting at the root.
Method:
1. Look at the roots value.
2. Look at the value of the leftmost child of the root then add all children of the node to a queue.
3. Continue step 2 for the next leftmost child of the root until all the roots children have been visited.
4. Go through each node in the queue, reading its value and adding its children to the queue.
5. Repeat step 4 until the queue is empty.
