Transcript tree

Comp 245
Data Structures
Trees
Introduction to the Tree ADT




A tree is a non-linear structure.
A treenode can point to 0 to N other
nodes.
There is one access point to the tree;
it is called the root.
A tree is recursive in nature.
Terminology Using a Binary Tree
Root
Child
Parent
Leaf
Height
Level
Full, Complete, Balanced
A FULL Tree
A COMPLETE Tree
A BALANCED Tree
Traversing a Tree



PRE – order
(v)isit – (l)eft – (r)ight
VLR
POST – order
(l)eft – (r)ight – (v)isit
LRV
IN – order
(l)eft – (v)isit – (r)ight
LVR
A PRE-order Traversal
(VLR)
1
2
4
8
5
3
6
9
7
This traversal is considered “top-down”
A POST-order Traversal
(LRV)
8
4
5
2
9
6
7
3
1
This traversal is considered “bottom-up”
An IN-order Traversal
(LVR)
8
4
2
5
1
6
9
3
7
This traversal is considered “left to right”
Traversal Practice
Traversal Practice
Pre
1
2
4
5
7
8
3
6
9
Post
4
7
8
5
2
9
6
3
1
In
4
2
7
5
8
1
3
9
6
Sample Code of a Traversal
void Tree::InOrder(TreePtr P)
{
if (P != NULL)
{
InOrder(P->Left);
Process(P);
InOrder(P->Right);
}
}
Implementing a Binary Tree
Linked
struct Node;
typedef SomeDataType TreeType;
typedef Node* TreePtr;
struct Node
{
TreeType info;
TreePtr Left, Right;
};
Defining a Binary Tree
Linked
class Tree
{
public:
Tree();
~Tree();
bool Empty();
bool Insert(TreeType);
bool Delete(TreeType);
void Traverse();
private:
void InOrder(TreePtr);
TreePtr Root;
};
Binary Search Trees
BST


A special type of tree that is very
useful!
Main characteristic:
Given any node P, the left child is lesser than or
equal to P; the right child is greater than P.

The efficiency of a BST ranges from
logarithmic time to linear time.
Example of BST Efficiency
How many accesses to find R?
How many accesses to find R?
BST Efficiency


Assuming a tree is balanced, it’s efficiency
is approximately log2N where N is the
number of elements in the tree.
Example:
There are 1000 elements in a BST, it’s efficiency therefore
is approximately log21000 = 9.9 or 10. This means
that it will take in the absolute worst case, 10 accesses
to find a value in the tree. If you contrast this to an
ordered list, it will take 1000 accesses in the worst
case and 500 in the average case to find an
element!!

If a tree is not balanced, it’s efficiency
will degenerate!
BST Operation - Insertion


The Insert function can be highly
efficient.
The new value is always inserted as a
leaf node!
BST Operation – Insertion
Practice: Build a BST
Build a BST from these
values:
LARRY
FRED
JOE
STEVE
NANCY
BILL
CAROL
TERRY
Inserting a Node into a BST





Create a node (Test for success)
Store data, set right and left pointers
null (it will be a leaf)
Search tree for insertion point, keep
track of node which will become the
parent.
Attach this node to parent.
Return success or failure of operation.
Deleting a Node from a BST

There are three cases to account for:
Leaf
One Child
Two Child

The algorithm requires a Search to
find the node to delete, determining
the specific case, and then executing
the deletion.
Leaf Case

How do you know the node is a leaf?

This routine will require 1) a pointer to the node to
be deleted and 2) a pointer to the parent.
Delete Leaf Code
void Bst::DeleteLeaf (TreePtr P, TreePtr Parent)
{
//check for root
if (Parent == NULL)
Root = NULL;
else
if (Parent->Left == P)
Parent->Left = NULL;
else
Parent->Right = NULL;
delete P;
}
One Child Case

How do you know the node has one child?

This routine will require 1) a pointer to the node to be
deleted and 2) a pointer to the parent.
Delete One Child Code
void Bst::DeleteOneChild (TreePtr P, TreePtr Parent)
{
1) save pointer to subtree, must be re-attached
2) check for root case
3) re-attach subtree to parent
4) delete P
}
Two Child Case

How do you know the node has two children?

This routine will require only a pointer to the node to be
deleted.
Finding the Closest
Predecessor



From the two child node to be deleted,
take one step left and go as far right as
possible. This node is the closest
predecessor.
Place this value in the node to be
deleted.
The closest predecessor will be
deleted by calling DeleteLeaf or
DeleteOneChild.
Delete Two Children Case
void Bst::DeleteTwoChild (TreePtr P)
{
1) Find closest predecessor (cp), keep track of
parent to cp!!
2) Copy cp->info to P->info
3) Call DeleteLeaf or DeleteOneChild for cp
}
Traversal Usage
Preorder

The preorder traversal can be used to effectively
save a tree to file that can be reconstructed
identically. This type of traversal can be used to
copy a tree also.
Mike
Don
Harry
Greg
Tim
Paul
Wayne
Traversal Usage
Inorder

The inorder traversal can be used to obtain a sorted
list from a BST.
Don
Greg
Harry
Mike
Paul
Tim
Wayne
Traversal Usage
Postorder

The postorder traversal can be used to delete a
tree. A tree needs to be deleted from the bottom up
because every node at the point of deletion is a
leaf.
Order of Deletion
Greg
Harry
Don
Paul
Wayne
Tim
Mike
Binary Tree Implementation
Array Based – method 1



The first method will store information
in the tree traveling down levels going
left to right.
Given this storage technique, a node
stored at slot I in the array will have it’s
left child at 2I + 1, and the right child
will be at 2I + 2.
A parent can be found at (I – 1)/2.
Binary Tree Implementation
Array Based – method 2


The second method will have an array
of structs. Each struct will contain the
information and left and right pointer
fields. The pointer fields will simply be
index values within the array.
Each new value is added at the end of
the array as a leaf and the pointer to
it’s parent adjusted.
N-Ary Trees
First Child-Sibling Implementation