Transcript Binary Trees

Binary Trees
Chapter 6
Linked Lists Suck




By now you realize that the title to this slide is
true…
When we are talking about searching or
representing data structures that need a
hierarchical structures.
We need a better structure…
So we get binary trees
Tree definition

1.
2.
3.
Here is a (recursive, of course) definition for
a tree:
An empty structure is an empty tree
If t1,…,tk are disjointed trees, then the
structure whose root has as its children the
roots of t1,…,tk is also a tree
Only structures generate by rules 1 and 2 are
trees.
More terminology




Each node has to be reachable from the roots
through a unique sequence of arcs called a
path.
The number of arcs in a path is called the
length of the path.
The level of a node is the length of the path
from the root to the node plus 1.
The height of a non-empty tree is the
maximum level of a node in the tree.
Special Trees


An empty tree has a height of zero.
A single node tree is a tree of height 1.

This is the only case where a node is both a root
and a leaf.
Binary Trees




According to the definition of trees, a node can
have any number of children.
A binary tree is restricted to only having 0, 1,
or 2 children.
A complete binary tree is one where all the
levels are full with exception to the last level
and it is filled from left to right.
A full binary tree is one where if a node has a
child, then it has two children.
Full Binary Tree Theorem

For all the nonempty binary trees whose
nonterminal node have exactly two nonempty
children, the number of leaves m is greater
than the number of nonterminal node k and m
= k + 1.
Binary Search Trees


A binary search tree (BST) is a binary tree that
has the following property: For each node n of
the tree, all values stored in its left subtree are
less than value v stored in n, and all values
stored in the right subtree are greater than v.
This definition excludes the case of duplicates.
They can be include and would be put in the
right subtree.
Binary Tree Traversals




A traversal is where each node in a tree is
visited and visited once
For a tree of n nodes there are n! traversals
Of course most of those are hard to program
There are two very common traversals


Breadth First
Depth First
Breadth First



In a breadth first traversal all of the nodes on a
given level are visited and then all of the nodes
on the next level are visited.
Usually in a left to right fashion
This is implemented with a queue
Depth First


In a depth first traversal all the nodes on a
branch are visited before any others are visited
There are three common depth first traversals




Inorder
Preorder
Postorder
Each type has its use and specific application
Insertion





In order to build a tree you must be able to
insert into the tree
In order to do this you need to know where the
nodes goes
Typically the tree is searched looking for a null
pointer to hang the new element from
There are two common ways to do this
Use a look ahead or check for null as the first
line in the code
More insertion



I prefer to check for null as the first thing I do
in my code
It simplifies some of the tests
And makes for a really easy to check for base
case
Code
InsertionHelper( Node *n, T data )
{
if ( node == 0 )
return new Node( data );
if ( n->getData() < data )
setLeft( InsertionHelper( n->getLeft(), data);
else
setRight( InsertionHelper( n->getRight(), data);
}
Deletion




Deletion poses a bigger problem
When we delete we normally have two choices
Deletion by merging
Deletion by copying
Deletion by Merging






Deletion by merging takes two subtrees and
merges them together into one tree
The idea is you have a node n to delete
N can have two children
So you find the smallest element in n’s left
subtree
You then take n’s right subtree and merge it to
the bottom of the left subtree
The root of the left subtree replaces n
Deletion by copying


This will simply swap values and reduce a
difficult case to an easier one
If the node n to be deleted has no children,


If it has one child


easy blow it away
Easy simply pass n’s child pointer up, make n’s
parent point to n’s child and blow n away
If n has two child,

Now we have deletion by copying
Details



We find the smallest value in n’s right subtree
We will take the value from that node and put
it in place of the value in n
We will then blow away the node that had the
smallest value in it