Transcript Fourteenth Lecture

CS 240: Data Structures
Thursday, August 2nd
Trees – Traversals, Representations,
Recursion and Helpers
Submissions

If you need a Project 1 grade, you need to
schedule an appointment with me after
class.
Traversals


Traversals are how we extract data from the tree
– or any data structure.
Queue and Stack look at the data before moving
to the next data.





NLR
-
However, there is no R in this case.
The three major orders:
Preorder:
NLR
Inorder:
LNR
Postorder:
LRN
Tree Traversals







Preorder:
NLR
Inorder:
LNR
Postorder:
LRN
N means Node. More specifically, look at the
node.
L means Left and R means Right.
This is the order we examine data.
You may find it helpful to cross out each thing
you do during a traversal.
___
Tree Traversals
Lets look at some examples.
 This means we have to create some trees.

Representations



Nodes:
Data is allocated on
each insert and
deallocated on each
removal
Traversals are done
using left/right



Arrays/Vectors
Data allocation only
occurs if the insertion
is out of range.
Deallocation only
occurs if sufficient
space can be
recovered.
Traversals are done
using index arithmetic
Representations





Nodes have a left and right pointer.
Vector has to solve for left and right.
Starting at location 0:

Left is location*2 + 1

Right is (location+1)*2
With vectors it is easier to find the parent node,
just reverse the operation.
Drawing time!
Tree ADT

Any node in a Tree is also a Tree.





This is why recursive code works on either of
these.
Tree x;
x.insert(15); //calls insert(15,root);
15
x.insert(30); //calls insert(30,root);


This also applies to list, any node in a list is also a list.
Since root is full, we compare 30 to 15. It is larger, so
insert on the right subtree:
insert(30,root->right);
30
Private vs Public
Many of our methods are public so that the
user can use them.
 There are some methods that we don’t
want to give the user access to.


insert(T value);
vs insert(T value, Node<T> * insertat);

This allows us to create methods for our
own use that the user won’t have access
to.
Tree Terms


So far, we really only talked about “root” which is
equivalent to “first” from our linked lists.
Root also refers to the top-most node in the tree
we are looking at.


A leaf node is a node who has no children.




All nodes are root relative to themselves.
Left = Right = NULL;
If a node is not a leaf node, it is a parent node.
A child is a node with a parent.
Level refers to the depth of the node relative to
the root we are looking at.
Trees and Graphs
Trees are a subset of Graph.
 We can apply searching methods from
Graph to Tree:

Breadth-first search: Provides a level-by-level
output of the Tree
 Depth-first search: If we take the left sub-tree
first: we get preorder or inorder traversal.
 If we take the right sub-tree first: we get
postorder or inorder traversal.

How do we?


Insert: Traverse until you find NULL – going left if we are
small, going right if we are larger. At NULL, create a new
node, return location to caller – who must now point to
the new node.
Remove: Traverse until you find the value you want to
remove.




If it is a leaf node, remove it, parent points to NULL.
If it has 1 child, parent points to the child.
If it has 2 children, find smallest value on right sub-tree. Copy
that value into the current node. Then, remove(current>data,current->right);
Empty: Starting at root, if NULL return. Otherwise,
empty(target->left);, empty(target->right);, delete target;
Problems
First, let us compare a Binary Search Tree
with a Binary Tree – we have only really
talked about Binary Search Trees so far.
 We use Binary Search Trees because of
the improved search performance.
 However, it can degenerate!

Balancing

Therefore, we need to balance our trees.

Search time is slow when the BST is
“skinny”. Therefore, we like our BSTs to be
“beefy”.
Self-Balancing Trees
AVL: A self-balancing tree that uses a
“balance” factor to determine if an
adjustment is needed.
 Each node is created with the balance
factor set to 0.
 Balance is equal to the difference between
the height/depth of a node’s sub-trees.
 Rebalance occurs whenever one of the 4
cases exists.

AVL Cases

Left-Left: Parent = -2, Left Child – 1


Left-Right: Parent = -2, Left Child = +1


Rotate left around child, right around Parent
Right-Right: Parent = +2, Right Child = +1


Rotate Right around Parent
Rotate Left around Parent
Right-Left: Parent = +2, Right Child = -1

Rotate right around child, left around Parent.
AVL
This works out rather well.
 However, almost half of insertions and
removal require rotation.

More trees
Huffman Trees
 This is an algorithm for generating codes
such as morse code.
 For any given set of data and values.
 Pair up the two smallest (replace them
with a tree containing)

Root = sum of the two values
 Left child = one of the data
 Right child = the other

Various Tidbits
Activation Stack
 Recursion and evaluation
 Array vs pointer indexing
 Use of “this”
 Proving algorithms
 Shallow vs Deep copy
