Binary Trees
A binary tree is made up of a finite set
of nodes that is either empty or
consists of a node called the root
together with two binary trees,called
the left and right subtrees,which are
disjoint from each other and from the
root.
Binary Tree Example
Notation,Node,
children,edge,
parent,ancestor,
descendant,path,
depth,height,level,
leaf node,internal
node,subtree.
Full and Complete Binary Trees
Full binary tree,Each node is either a leaf or
internal node with exactly two non-empty children.
Complete binary tree,If the height of the tree is d,
then all leaves except possibly level d are
completely full,The bottom level has all nodes to
the left side.
Full Binary Tree Theorem (1)
Theorem,The number of leaves in a non-empty
full binary tree is one more than the number of
internal nodes.
Proof (by Mathematical Induction):
Base case,A full binary tree with 1 internal node must
have two leaf nodes.
Induction Hypothesis,Assume any full binary tree T
containing n-1 internal nodes has n leaves.
Full Binary Tree Theorem (2)
Induction Step,Given tree T with n internal
nodes,pick internal node I with two leaf children,
Remove I’s children,call resulting tree T’.
By induction hypothesis,T’ is a full binary tree with
n leaves.
Restore I’s two children,The number of internal
nodes has now gone up by 1 to reach n,The
number of leaves has also gone up by 1.
Full Binary Tree Corollary
Theorem,The number of null pointers in a
non-empty tree is one more than the
number of nodes in the tree.
Proof,Replace all null pointers with a
pointer to an empty leaf node,This is a
full binary tree.
Binary Tree Node Class (1)
// Binary tree node class
template <class Elem>
class BinNodePtr, public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e,BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
Binary Tree Node Class (2)
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const
{ return lc; }
void setLeft(BinNode<Elem>* b)
{ lc = (BinNodePtr*)b; }
inline BinNode<Elem>* right() const
{ return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNodePtr*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
Traversals (1)
Any process for visiting the nodes in
some order is called a traversal.
Any traversal that lists every node in
the tree exactly once is called an
enumeration of the tree’s nodes.
Traversals (2)
? Preorder traversal,Visit each node before
visiting its children.
? Postorder traversal,Visit each node after
visiting its children.
? Inorder traversal,Visit the left subtree,
then the node,then the right subtree.
Traversal Example
// Return the number of nodes in the tree
template <class Elem>
int count(BinNode<Elem>* subroot) {
if (subroot == NULL)
return 0; // Nothing to count
return 1 + count(subroot->left())
+ count(subroot->right());
}
Binary Tree Implementation (1)
Binary node class
template<class Elem>struct BinNode
{ Elem data; // The node's value
BinNode *lc; // Pointer to left child
BinNode *rc; // Pointer to right child
BinNode() { lc = rc = NULL; }
BinNode(Elem e,BinNode* l=NULL,BinNode* r=NULL)
{ data = e; lc = l; rc = r; }
~BinNode() { } // Destructor
Elem& val() { return data; }
Binary node class continue
void setVal(const Elem& e) { data = e; }
inline BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (BinNode*)b; }
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNode*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
Array Implementation (1)
Position 0 1 2 3 4 5 6 7 8 9 10 11
Parent -- 0 0 1 1 2 2 3 3 4 4 5
Left Child 1 3 5 7 9 11 -- -- -- -- -- --
Right Child 2 4 6 8 10 -- -- -- -- -- -- --
Left Sibling -- -- 1 -- 3 -- 5 -- 7 -- 9 --
Right Sibling -- 2 -- 4 -- 6 -- 8 -- 10 -- --
Array Implementation (1)
Parent (r) =
Leftchild(r) =
Rightchild(r) =
Leftsibling(r) =
Rightsibling(r) =
Binary Search Trees
BST Property,All elements stored in the left
subtree of a node with value K have values < K,
All elements stored in the right subtree of a node
with value K have values >= K.
BST ADT(1)
// BST implementation for the Dictionary ADTtemplate <class Key,class Elem,
class KEComp,class EEComp>class BST, public Dictionary<Key,Elem,
KEComp,EEComp> {private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes
void clearhelp(BinNode<Elem>*);BinNode<Elem>*
inserthelp(BinNode<Elem>*,const Elem&);BinNode<Elem>*
deletemin(BinNode<Elem>*,BinNode<Elem>*&);BinNode<Elem>* removehelp(BinNode<Elem>*,
const Key&,BinNode<Elem>*&);bool findhelp(BinNode<Elem>*,const Key&,
Elem&) const;void printhelp(BinNode<Elem>*,int) const;
BST ADT(2)
public:BST() { root = NULL; nodecount = 0; }
~BST() { clearhelp(root); } void clear() { clearhelp(root); root = NULL;
nodecount = 0; }bool insert(const Elem& e) {
root = inserthelp(root,e);nodecount++;
return true; }bool remove(const Key& K,Elem& e) {
BinNode<Elem>* t = NULL;root = removehelp(root,K,t);
if (t == NULL) return false;e = t->val();
nodecount--;delete t;
return true; }
BST ADT(3)
bool removeAny(Elem& e) { // Delete min valueif (root == NULL) return false; // Empty
BinNode<Elem>* t;root = deletemin(root,t);
e = t->val();delete t;
nodecount--;return true;
}bool find(const Key& K,Elem& e) const
{ return findhelp(root,K,e); }int size() { return nodecount; }
void print() const {if (root == NULL)
cout << "The BST is empty.\n";else printhelp(root,0);
}
BST Search
template <class Key,class Elem,
class KEComp,class EEComp>
bool BST<Key,Elem,KEComp,EEComp>::
findhelp(BinNode<Elem>* subroot,
const Key& K,Elem& e) const {
if (subroot == NULL) return false;
else if (KEComp::lt(K,subroot->val()))
return findhelp(subroot->left(),K,e);
else if (KEComp::gt(K,subroot->val()))
return findhelp(subroot->right(),K,e);
else { e = subroot->val(); return true; }
}
BST Insert (1)
BST Insert (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
inserthelp(BinNode<Elem>* subroot,
const Elem& val) {
if (subroot == NULL) // Empty,create node
return new BinNodePtr<Elem>(val,NULL,NULL);
if (EEComp::lt(val,subroot->val()))
subroot->setLeft(inserthelp(subroot->left(),
val));
else subroot->setRight(
inserthelp(subroot->right(),val));
// Return subtree with node inserted
return subroot;
}
Remove Minimum Value
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,
KEComp,EEComp>::
deletemin(BinNode<Elem>* subroot,
BinNode<Elem>*& min) {
if (subroot->left() == NULL) {
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(
deletemin(subroot->left(),min));
return subroot;
}
}
BST Remove (1)
BST Remove (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
removehelp(BinNode<Elem>* subroot,
const Key& K,BinNode<Elem>*& t) {
if (subroot == NULL) return NULL;
else if (KEComp::lt(K,subroot->val()))
subroot->setLeft(
removehelp(subroot->left(),K,t));
else if (KEComp::gt(K,subroot->val()))
subroot->setRight(
removehelp(subroot->right(),K,t));
BST Remove (2)
else { // Found it,remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL)
subroot = subroot->right();
else if (subroot->right() == NULL)
subroot = subroot->left();
else { // Both children are non-empty
subroot->setRight(
deletemin(subroot->right(),temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
} }
return subroot;
}
Cost of BST Operations
Find:
Insert:
Delete:
Heaps
Heap,Complete binary tree with the heap
property:
? Min-heap,All values less than child values.
? Max-heap,All values greater than child values.
The values are partially ordered.
Heap representation,Normally the array-
based complete binary tree representation.
Heap ADT
template<class Elem,class Comp> class maxheap{private:
Elem* Heap; // Pointer to the heap arrayint size; // Maximum size of the heap
int n; // Number of elems now in heapvoid siftdown(int); // Put element in place
public:maxheap(Elem* h,int num,int max);
int heapsize() const;bool isLeaf(int pos) const;
int leftchild(int pos) const;int rightchild(int pos) const;
int parent(int pos) const;bool insert(const Elem&);
bool removemax(Elem&);bool remove(int,Elem&);
void buildHeap();};
Building the Heap
(a) (4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (6-5) (7-5) (7-6)
(b) (5-2),(7-3),(7-1),(6-1)
Siftdown (1)
For fast heap construction:
? Work from high end of array to low end.
? Call siftdown for each item.
? Don’t need to call siftdown on leaf nodes.
template <class Elem,class Comp>void maxheap<Elem,Comp>::siftdown(int pos) {
while (!isLeaf(pos)) {int j = leftchild(pos);
int rc = rightchild(pos);if ((rc<n) && Comp::lt(Heap[j],Heap[rc]))
j = rc;if (!Comp::lt(Heap[pos],Heap[j])) return;
swap(Heap,pos,j);pos = j;
}}
Siftdown (2)
Buildheap Cost
Cost for heap construction:
log n
? (i - 1) n/2i ? n.
i=1
Remove Max Value
template <class Elem,class Comp>
bool maxheap<Elem,Comp>:,
removemax(Elem& it) {
if (n == 0) return false; // Heap is empty
swap(Heap,0,--n); // Swap max with end
if (n != 0) siftdown(0);
it = Heap[n]; // Return max value
return true;
}
Priority Queues (1)
A priority queue stores objects,and on request
releases the object with greatest value.
Example,Scheduling jobs in a multi-tasking
operating system.
The priority of a job may change,requiring some
reordering of the jobs.
Implementation,Use a heap to store the priority
queue.
Priority Queues (2)
To support priority reordering,delete and re-insert,
Need to know index for the object in question.
template <class Elem,class Comp>
bool maxheap<Elem,Comp>::remove(int pos,
Elem& it) {
if ((pos < 0) || (pos >= n)) return false;
swap(Heap,pos,--n);
while ((pos != 0) && (Comp::gt(Heap[pos],
Heap[parent(pos)])))
swap(Heap,pos,parent(pos));
siftdown(pos);
it = Heap[n];
return true;
}
Huffman Coding Trees
ASCII codes,8 bits per character.
? Fixed-length coding.
Can take advantage of relative frequency of letters
to save space.
? Variable-length coding
Build the tree with minimum external path weight.
Z K F C U D L E
2 7 24 32 37 42 42 120
Huffman Tree
Assigning Codes
Letter Freq Code Bits
C 32
D 42
E 120
F 24
K 7
L 42
U 37
Z 2
Coding and Decoding
A set of codes is said to meet the prefix
property if no code in the set is the prefix
of another.
Code for DEED:
Decode 1011001110111101:
Expected cost per letter:
A binary tree is made up of a finite set
of nodes that is either empty or
consists of a node called the root
together with two binary trees,called
the left and right subtrees,which are
disjoint from each other and from the
root.
Binary Tree Example
Notation,Node,
children,edge,
parent,ancestor,
descendant,path,
depth,height,level,
leaf node,internal
node,subtree.
Full and Complete Binary Trees
Full binary tree,Each node is either a leaf or
internal node with exactly two non-empty children.
Complete binary tree,If the height of the tree is d,
then all leaves except possibly level d are
completely full,The bottom level has all nodes to
the left side.
Full Binary Tree Theorem (1)
Theorem,The number of leaves in a non-empty
full binary tree is one more than the number of
internal nodes.
Proof (by Mathematical Induction):
Base case,A full binary tree with 1 internal node must
have two leaf nodes.
Induction Hypothesis,Assume any full binary tree T
containing n-1 internal nodes has n leaves.
Full Binary Tree Theorem (2)
Induction Step,Given tree T with n internal
nodes,pick internal node I with two leaf children,
Remove I’s children,call resulting tree T’.
By induction hypothesis,T’ is a full binary tree with
n leaves.
Restore I’s two children,The number of internal
nodes has now gone up by 1 to reach n,The
number of leaves has also gone up by 1.
Full Binary Tree Corollary
Theorem,The number of null pointers in a
non-empty tree is one more than the
number of nodes in the tree.
Proof,Replace all null pointers with a
pointer to an empty leaf node,This is a
full binary tree.
Binary Tree Node Class (1)
// Binary tree node class
template <class Elem>
class BinNodePtr, public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e,BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
Binary Tree Node Class (2)
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const
{ return lc; }
void setLeft(BinNode<Elem>* b)
{ lc = (BinNodePtr*)b; }
inline BinNode<Elem>* right() const
{ return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNodePtr*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
Traversals (1)
Any process for visiting the nodes in
some order is called a traversal.
Any traversal that lists every node in
the tree exactly once is called an
enumeration of the tree’s nodes.
Traversals (2)
? Preorder traversal,Visit each node before
visiting its children.
? Postorder traversal,Visit each node after
visiting its children.
? Inorder traversal,Visit the left subtree,
then the node,then the right subtree.
Traversal Example
// Return the number of nodes in the tree
template <class Elem>
int count(BinNode<Elem>* subroot) {
if (subroot == NULL)
return 0; // Nothing to count
return 1 + count(subroot->left())
+ count(subroot->right());
}
Binary Tree Implementation (1)
Binary node class
template<class Elem>struct BinNode
{ Elem data; // The node's value
BinNode *lc; // Pointer to left child
BinNode *rc; // Pointer to right child
BinNode() { lc = rc = NULL; }
BinNode(Elem e,BinNode* l=NULL,BinNode* r=NULL)
{ data = e; lc = l; rc = r; }
~BinNode() { } // Destructor
Elem& val() { return data; }
Binary node class continue
void setVal(const Elem& e) { data = e; }
inline BinNode<Elem>* left() const { return lc; }
void setLeft(BinNode<Elem>* b) { lc = (BinNode*)b; }
inline BinNode<Elem>* right() const { return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNode*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
Array Implementation (1)
Position 0 1 2 3 4 5 6 7 8 9 10 11
Parent -- 0 0 1 1 2 2 3 3 4 4 5
Left Child 1 3 5 7 9 11 -- -- -- -- -- --
Right Child 2 4 6 8 10 -- -- -- -- -- -- --
Left Sibling -- -- 1 -- 3 -- 5 -- 7 -- 9 --
Right Sibling -- 2 -- 4 -- 6 -- 8 -- 10 -- --
Array Implementation (1)
Parent (r) =
Leftchild(r) =
Rightchild(r) =
Leftsibling(r) =
Rightsibling(r) =
Binary Search Trees
BST Property,All elements stored in the left
subtree of a node with value K have values < K,
All elements stored in the right subtree of a node
with value K have values >= K.
BST ADT(1)
// BST implementation for the Dictionary ADTtemplate <class Key,class Elem,
class KEComp,class EEComp>class BST, public Dictionary<Key,Elem,
KEComp,EEComp> {private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes
void clearhelp(BinNode<Elem>*);BinNode<Elem>*
inserthelp(BinNode<Elem>*,const Elem&);BinNode<Elem>*
deletemin(BinNode<Elem>*,BinNode<Elem>*&);BinNode<Elem>* removehelp(BinNode<Elem>*,
const Key&,BinNode<Elem>*&);bool findhelp(BinNode<Elem>*,const Key&,
Elem&) const;void printhelp(BinNode<Elem>*,int) const;
BST ADT(2)
public:BST() { root = NULL; nodecount = 0; }
~BST() { clearhelp(root); } void clear() { clearhelp(root); root = NULL;
nodecount = 0; }bool insert(const Elem& e) {
root = inserthelp(root,e);nodecount++;
return true; }bool remove(const Key& K,Elem& e) {
BinNode<Elem>* t = NULL;root = removehelp(root,K,t);
if (t == NULL) return false;e = t->val();
nodecount--;delete t;
return true; }
BST ADT(3)
bool removeAny(Elem& e) { // Delete min valueif (root == NULL) return false; // Empty
BinNode<Elem>* t;root = deletemin(root,t);
e = t->val();delete t;
nodecount--;return true;
}bool find(const Key& K,Elem& e) const
{ return findhelp(root,K,e); }int size() { return nodecount; }
void print() const {if (root == NULL)
cout << "The BST is empty.\n";else printhelp(root,0);
}
BST Search
template <class Key,class Elem,
class KEComp,class EEComp>
bool BST<Key,Elem,KEComp,EEComp>::
findhelp(BinNode<Elem>* subroot,
const Key& K,Elem& e) const {
if (subroot == NULL) return false;
else if (KEComp::lt(K,subroot->val()))
return findhelp(subroot->left(),K,e);
else if (KEComp::gt(K,subroot->val()))
return findhelp(subroot->right(),K,e);
else { e = subroot->val(); return true; }
}
BST Insert (1)
BST Insert (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
inserthelp(BinNode<Elem>* subroot,
const Elem& val) {
if (subroot == NULL) // Empty,create node
return new BinNodePtr<Elem>(val,NULL,NULL);
if (EEComp::lt(val,subroot->val()))
subroot->setLeft(inserthelp(subroot->left(),
val));
else subroot->setRight(
inserthelp(subroot->right(),val));
// Return subtree with node inserted
return subroot;
}
Remove Minimum Value
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,
KEComp,EEComp>::
deletemin(BinNode<Elem>* subroot,
BinNode<Elem>*& min) {
if (subroot->left() == NULL) {
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(
deletemin(subroot->left(),min));
return subroot;
}
}
BST Remove (1)
BST Remove (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
removehelp(BinNode<Elem>* subroot,
const Key& K,BinNode<Elem>*& t) {
if (subroot == NULL) return NULL;
else if (KEComp::lt(K,subroot->val()))
subroot->setLeft(
removehelp(subroot->left(),K,t));
else if (KEComp::gt(K,subroot->val()))
subroot->setRight(
removehelp(subroot->right(),K,t));
BST Remove (2)
else { // Found it,remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL)
subroot = subroot->right();
else if (subroot->right() == NULL)
subroot = subroot->left();
else { // Both children are non-empty
subroot->setRight(
deletemin(subroot->right(),temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
} }
return subroot;
}
Cost of BST Operations
Find:
Insert:
Delete:
Heaps
Heap,Complete binary tree with the heap
property:
? Min-heap,All values less than child values.
? Max-heap,All values greater than child values.
The values are partially ordered.
Heap representation,Normally the array-
based complete binary tree representation.
Heap ADT
template<class Elem,class Comp> class maxheap{private:
Elem* Heap; // Pointer to the heap arrayint size; // Maximum size of the heap
int n; // Number of elems now in heapvoid siftdown(int); // Put element in place
public:maxheap(Elem* h,int num,int max);
int heapsize() const;bool isLeaf(int pos) const;
int leftchild(int pos) const;int rightchild(int pos) const;
int parent(int pos) const;bool insert(const Elem&);
bool removemax(Elem&);bool remove(int,Elem&);
void buildHeap();};
Building the Heap
(a) (4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (6-5) (7-5) (7-6)
(b) (5-2),(7-3),(7-1),(6-1)
Siftdown (1)
For fast heap construction:
? Work from high end of array to low end.
? Call siftdown for each item.
? Don’t need to call siftdown on leaf nodes.
template <class Elem,class Comp>void maxheap<Elem,Comp>::siftdown(int pos) {
while (!isLeaf(pos)) {int j = leftchild(pos);
int rc = rightchild(pos);if ((rc<n) && Comp::lt(Heap[j],Heap[rc]))
j = rc;if (!Comp::lt(Heap[pos],Heap[j])) return;
swap(Heap,pos,j);pos = j;
}}
Siftdown (2)
Buildheap Cost
Cost for heap construction:
log n
? (i - 1) n/2i ? n.
i=1
Remove Max Value
template <class Elem,class Comp>
bool maxheap<Elem,Comp>:,
removemax(Elem& it) {
if (n == 0) return false; // Heap is empty
swap(Heap,0,--n); // Swap max with end
if (n != 0) siftdown(0);
it = Heap[n]; // Return max value
return true;
}
Priority Queues (1)
A priority queue stores objects,and on request
releases the object with greatest value.
Example,Scheduling jobs in a multi-tasking
operating system.
The priority of a job may change,requiring some
reordering of the jobs.
Implementation,Use a heap to store the priority
queue.
Priority Queues (2)
To support priority reordering,delete and re-insert,
Need to know index for the object in question.
template <class Elem,class Comp>
bool maxheap<Elem,Comp>::remove(int pos,
Elem& it) {
if ((pos < 0) || (pos >= n)) return false;
swap(Heap,pos,--n);
while ((pos != 0) && (Comp::gt(Heap[pos],
Heap[parent(pos)])))
swap(Heap,pos,parent(pos));
siftdown(pos);
it = Heap[n];
return true;
}
Huffman Coding Trees
ASCII codes,8 bits per character.
? Fixed-length coding.
Can take advantage of relative frequency of letters
to save space.
? Variable-length coding
Build the tree with minimum external path weight.
Z K F C U D L E
2 7 24 32 37 42 42 120
Huffman Tree
Assigning Codes
Letter Freq Code Bits
C 32
D 42
E 120
F 24
K 7
L 42
U 37
Z 2
Coding and Decoding
A set of codes is said to meet the prefix
property if no code in the set is the prefix
of another.
Code for DEED:
Decode 1011001110111101:
Expected cost per letter:
