# Presentation: 228661

## C++ Plus Data Structures

**Nell Dale**
**Chapter 8**
**Binary Search Trees**
***Modified from the slides by Sylvia Sorkin, Community College of Baltimore County - Essex Campus***

**C++ Plus Data Structures**

## for an element in a sorted list stored sequentially

in an array: O(Log2N)
in a linked list: ? (midpoint = ?)

**in an array: ****O(Log****2****N)**
**in a linked list: ? (midpoint = ?)**

**Binary search **

## Introduce some basic tree vocabulary

Develop algorithms

Implement operations needed to use a binary search tree

**Develop algorithms**
**Implement operations needed to use a binary search tree**

**Goals of this chapter**

## Jake’s Pizza Shop

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

##   Waitress                              Waiter                   Cook                         Helper 

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

##   Waitress                              Waiter                   Cook                         Helper 

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

## A Tree Has Levels

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

**A Tree Has Levels**

**LEVEL 0**

- Level of a node: its distance from the root

##   Waitress                              Waiter                   Cook                         Helper 

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

## Level Two

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

**Level Two**

**LEVEL 2**

## Maximum number of levels: N

Minimum number of levels: logN + 1

          e.g., N=8, 16, ..., 1000

**Minimum number of levels: ****logN + 1**
**          ****e.g., N=8, 16, ..., 1000**

**A binary tree with N nodes:**

## the maximum level in a tree

**The height of a tree:**

- -- a critical factor in determining
-    how efficiently we can search for elements

## A Subtree

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

**A Subtree**

**LEFT SUBTREE OF ROOT NODE**

## Another Subtree

**	****	****	****      ****Owner **
**	****	****	****       ****Jake**
**                   ****Manager ****	****	****                         Chef ****	****	****       Brad****	****	****	****          Carol**
**  ****Waitress                              Waiter                   Cook                         Helper**** **
**    ****Joyce                                 Chris                      Max                            Len**

**Another Subtree**

**RIGHT SUBTREE**
** ****OF ROOT NODE**

## 
A binary tree is a structure in which:

   Each node can have at most two children, and in which a unique path exists from the root to every other node.

The two children of a node are called the    left child and the right child, if they exist.

**A binary tree is a structure in which:**
**   ****Each node can have at most ****two**** children, and in which a ****unique path**** exists from the root to every other node.**
**The two children of a node are called the    ****left child**** and the ****right child, ****if they exist.**

**Binary Tree**

** **

**A Binary Tree**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

** **

**A Binary Tree ?**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

** **

**How many leaf nodes?**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

** **

**How many descendants of Q?**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

** **

**How many ancestors of K?**

** **

**Implementing a Binary Tree with Pointers and Dynamic Data**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

## Each node contains two pointers 

**template< class  ItemType >**
**struct   TreeNode  {****   **
**    ****ItemType     info;****   ****	****	****  *****// Data member***
*** *****   ****TreeNode<ItemType>*  left;****     *****// Pointer to left child***** **
**    ****TreeNode<ItemType>*  right; ****  *****// Pointer to right child***
**};**

-  **.** **left          ****.** **info            ****.** **right**

** ****NULL ****           ****‘A’****            ****6000**

## class   TreeType  {   

**template< class  ItemType >**
**class   TreeType  {****   **
**public:   **
**	**
*** *****   ****TreeType ( );   ****	****     ****	****	*****// constructor***** **
**    ****~TreeType ( );         ****	****	****	*****// destructor***
**    ****bool   IsEmpty ( ) ****const****;  **
**    ****bool   IsFull ( ) ****const****;**
**    ****int      NumberOfNodes ( ) ****const****;***** ***
**    ****void   InsertItem ( ItemType  item );****	**
**    ****void   DeleteItem (ItemType  item );****	****	****    ****	**
**    ****void   RetrieveItem ( ItemType& item,  bool& found ); **
**    ****void   PrintTree (ofstream&  outFile)  ****const****;**
**      ****.  .  .****	**
**private:**
**	**** ****	**
**    ****TreeNode<ItemType>*  root;**
**};**

## TreeType<char> CharBST; 

**TreeType<char> CharBST;**** **

**Private data:**
**root**

**RetrieveItem**

**PrintTree**
**          ****.  **
**          ****.**
**          ****.**

** **

**A Binary Tree**

**   ****Q****   **

**   ****V****   **

**   ****T****   **

**   ****K ****  **

**   ****S****   **

**  ****A****   **

**   ****E ****  **

**   ****L****   **

- Search for ‘S’?

## A special kind of binary tree in which:

1.  Each node contains a distinct data value,

2.  The key values in the tree can be compared using “greater than” and “less than”, and

3.  The key value of each node in the tree is
	less than every key value in its right subtree, and greater than every key value in its left subtree.

**1.  Each node contains a distinct data value,**
**2.  The key values in the tree can be compared using “greater than” and “less than”, and**
**3.  The key value of each node in the tree is**
**	****less ****than every key value in its**** right subtree****, and ****greater ****than every key value in**** its left subtree.**

**A Binary ****Search**** Tree (B****S****T) is . . .**

## Depends on its key values and their order of insertion.

Insert the elements   ‘J’   ‘E’   ‘F’  ‘T’  ‘A’    in that order.

The first value to be inserted is put into the root node.

**Insert the elements   ‘J’   ‘E’   ‘F’  ‘T’  ‘A’    in that order.**
**The first value to be inserted is put into the root node.**

**Shape of a binary search tree . . .**

## 
Thereafter, each value to be inserted begins by comparing itself to the value in the root node, moving left it is less, or moving right if it is greater.  This continues at each level until it can be inserted as a new leaf. 

**Thereafter, each value to be inserted begins by comparing itself to the value in the root node, moving left it is less, or moving right if it is greater.  This continues at each level until it can be inserted as a new leaf. **

**Inserting ‘E’ into the BST**

## 
Begin by comparing ‘F’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. 

**Begin by comparing ‘F’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. **

**Inserting ‘F’ into the BST**

## 
Begin by comparing ‘T’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. 

**Begin by comparing ‘T’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. **

**Inserting ‘T’ into the BST**

## 
Begin by comparing ‘A’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. 

**Begin by comparing ‘A’ to the value in the root node, moving left it is less, or moving right if it is greater.  This continues until it can be inserted as a leaf. **

**Inserting ‘A’ into the BST**

## is obtained by inserting
 the elements   ‘A’   ‘E’   ‘F’  ‘J’  ‘T’    in that order?

** ****the elements   ‘A’   ‘E’   ‘F’  ‘J’  ‘T’    in that order?**

**What binary search tree . . .**

## obtained by inserting
 the elements   ‘A’   ‘E’   ‘F’  ‘J’  ‘T’    in that order.

** ****the elements   ‘A’   ‘E’   ‘F’  ‘J’  ‘T’    in that order.**

**Binary search tree . . .**

- A “degenerate” tree!

** **

**Another binary search tree**

**Add nodes containing these values in this order:**
**‘****D’      ‘B’      ‘L’       ‘Q’       ‘S’       ‘V’        ‘Z’**

** ‘****E’**

**‘****A’**

**‘****H’**

**‘****T’**

** ‘****M’**

**‘****K’**

**‘****P’**

** **

**Is ‘F’ in the binary search tree?**

**‘****J’**

** ‘****E’**

**‘****A’**

**‘****H’**

**‘****T’**

** ‘****M’**

**‘****V’**

**‘****P’**

## class   TreeType  {   

**template< class  ItemType >**
**class   TreeType  {****   **
**public:   **
**	**
*** *****   ****TreeType ( ) ;   ****	****     ****	****	*****// constructor***** **
**    ****~TreeType ( ) ;         ****	****	****	*****// destructor***
**    ****bool   IsEmpty ( ) ****const ****;  **
**    ****bool   IsFull ( ) ****const ****;**
**    ****int      NumberOfNodes ( ) ****const ****;***** ***
**    ****void   InsertItem ( ItemType  item ) ;****	**
**    ****void   DeleteItem (ItemType  item ) ;****	****	****    ****	**
**    ****void   RetrieveItem ( ItemType&  item ,  bool&  found ) ; **
**    ****void   PrintTree (ofstream&  outFile)  ****const ****;**
**      ****.  .  .****	**
**private:**
**	**** ****	**
**    ****TreeNode<ItemType>*********  root ;**
**};**

## //  SPECIFICATION   (continued)       

***// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -***
***// RECURSIVE PARTNERS OF MEMBER FUNCTIONS  ***
**template< class  ItemType >**
**void   PrintHelper ( TreeNode<ItemType>*********  ptr, **
**	****	****        ****ofstream&  outFile ) ;       **
**   **
**template< class  ItemType >**** **
**void   InsertHelper ( TreeNode<ItemType>*********&****  ptr, **
**	****	****         ****ItemType  item ) ;       **
**template< class  ItemType >**** **
**void  RetrieveHelper (***** *****TreeNode<ItemType>*********  ptr, **
**	****	****             ****ItemType&  item,  bool&  found ) ;  **
**template< class  ItemType >**
** ****void   DestroyHelper ( TreeNode<ItemType>*********  ptr ) ;                                    **
**	**

## // BINARY SEARCH TREE IMPLEMENTATION  

***// OF MEMBER FUNCTIONS AND THEIR HELPER FUNCTIONS***
***// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - *****template< class  ItemType >***** ***
**TreeType<ItemType> :: TreeType ( ) ****	****    ****	*****// constructor***** **
**{**
**       ****root = NULL ;**
**}**
***// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -***
**template< class  ItemType >**
**bool TreeType<ItemType> :: IsEmpty( )  const**
**{**
**       ****return ( root == NULL ) ;**
**}**

## template< class  ItemType > 

**template< class  ItemType >***** ***
**void   TreeType<ItemType> :: RetrieveItem ( ItemType&  item, **
**	****	****	****            ****	****	****           ****bool&   found )**
**{**
**      ****	****RetrieveHelper ( root, item,  found ) ;**** **
**}**
**template< class  ItemType >***** ***
**void  RetrieveHelper ( TreeNode<ItemType>********* ptr, ItemType&  item,  ****	****    ****	****	****            bool&   found)**
**{      if  ( ptr == NULL )    **
**	****found = false ;**
**       ****else if  ( item  <  ptr->info )****	****	****	****	****// GO LEFT**
**	****RetrieveHelper( ptr->left , item,  found ) ;**
**       ****else if  ( item  >  ptr->info ) ****	****	****	****// GO RIGHT**
**	****RetrieveHelper( ptr->right , item,  found ) ;**
**       ****else **
**       ****{     ****// item = ptr->info ;**
**	****found = true ;**
**       ****}**
**}**

## template< class  ItemType, class KF > 

**template< class  ItemType, ****class KF**** >***** ***
**void   TreeType<ItemType, ****KF****> :: RetrieveItem ( ItemType&  item, **
**	****	****	****     ****KF key****, bool&   found )**
**// Searches for an element with the same key as item’s key. **
**// If found, store it into item**
**{**
**      ****	****RetrieveHelper ( root,  item,  ****key,****  found ) ;**** **
**}**
**template< class  ItemType >***** ***
**void  RetrieveHelper ( TreeNode<ItemType,****KF****>********* ptr, ItemType&  item,  ****	****    ****	****	**** ****KF key****, bool&   found)**
**{      if  ( ptr == NULL )    **
**	****found = false ;**
**       ****else if  ( ****key****  <  ptr->info****.key()**** )****	****	****// GO LEFT**
**	****RetrieveHelper( ptr->left , item, ****key,**** ****found ) ;**
**       ****else if  ( ****key **** >  ptr->info****.key()**** ) ****	****	****// GO RIGHT**
**	****RetrieveHelper( ptr->right , item, ****key,**** ****found ) ;**
**       ****else **
**       ****{     item = ptr->info ; ****found = true ;**
**       ****}**
**}**

## template< class  ItemType > 

**template< class  ItemType >***** ***
**void   TreeType<ItemType> :: InsertItem ( ItemType  item )**
**{**
**	****InsertHelper ( root, item ) ;**** **
**}**
**template< class  ItemType >***** ***
**void   InsertHelper ( TreeNode<ItemType>*********&  ptr,   ItemType  item )**
**{      if  ( ptr == NULL )  **
**       ****{        ****	****	****	****	****// INSERT item HERE AS LEAF**
**	****ptr = new TreeNode<ItemType> ;**
**	****ptr->right = NULL ;**
**	****ptr->left = NULL ;**
**	****ptr->info = item ;**
**       ****}**
**       ****else if  ( item  <  ptr->info )****	****	****	****	****// GO LEFT**
**	****InsertHelper( ptr->left , item ) ;**
**       ****else if  ( item  >  ptr->info ) ****	****	****	****// GO RIGHT**
**	****InsertHelper( ptr->right , item ) ;**
**}**

## Find the node in the tree
Delete the node from the tree
Three cases:
	1. Deleting a leaf
	2. Deleting a node with only one child
	3. Deleting a node with two children

Note: the tree must remain a binary tree and    the search property must remain intact

**Delete the node from the tree**
**Three cases:**
**	****1. Deleting a leaf**
**	****2. Deleting a node with only one child**
**	****3. Deleting a node with two children**
**Note:**** the tree must remain a binary tree and    the search property must remain intact**

**Delete()**

## template< class  ItemType > 

**template< class  ItemType >***** ***
**void   TreeType<ItemType> :: DeleteItem ( ItemType&  item )**
**{**
**      ****	****DeleteHelper ( root, item ) ;**** **
**}**
**template< class  ItemType >***** ***
**void  DeleteHelper ( TreeNode<ItemType>********* ptr, ItemType&  item)**
**{**
**       ****if  ( item  <  ptr->info )****	****	****	****	****// GO LEFT**
**	****DeleteHelper( ptr->left , item ) ;**
**       ****else if  ( item  >  ptr->info ) ****	****	****	****// GO RIGHT**
**	****DeleteHelper( ptr->right , item ) ;**
**       ****else **
**       ****{     **
**	****DeleteNode(ptr);****  // Node is found: call DeleteNode**
**       ****}**
**}**

## template< class  ItemType > 

**template< class  ItemType >***** ***
**void   DeleteNode ( TreeNode<ItemType>*& tree )**
**{**
**  ****ItemType data;**
**  ****TreeNode< ItemType>* tempPtr;**
**  ****tempPtr = tree;**
**  ****if ( tree->left == NULL ) {**
**      ****tree = tree->right;**
**      ****delete tempPtr;**
**  ****} else if (tree->right == NULL ) {**
**      ****tree = tree->left;**
**      ****delete tempPtr;**
**  ****} else {         ****// have two children**
**      ****GetPredecessor(tree->left, item);**
**      ****tree->info = item;**
**      ****DeleteHelper(tree->left, item);**** ****// Delete predecessor node (rec)**
**  ****}**
**}**

## template< class  ItemType > 

**template< class  ItemType >***** ***
**void GetPredecessor( TreeNode<ItemType>* tree, ItemType& data )**
**// Sets data to the info member of the rightmost node in tree**
**{**
**    ****while (tree->right != NULL)**
**        ****tree = tree->right;**
**    ****data = tree->info;**
**}**

## Traverse a list:
	-- forward 
	-- backward

Traverse a tree:
	-- there are many ways!

**	****-- forward **
**	****-- backward**
**Traverse a ****tree****:**
**	****-- there are many ways!**

**PrintTree()**

** **

**Inorder Traversal:  ****A E H J M T Y**** **

** ‘****E’**

**‘****A’**

**‘****H’**

**‘****T’**

** ‘****M’**

**‘****Y’**

**tree**

**Print left subtree first**

**Print right subtree last**

**Print second**

## 					// INORDER TRAVERSAL

***	******	******	******	******	******// INORDER TRAVERSAL***
**template< class  ItemType >**
**void   TreeType<ItemType> :: PrintTree ( ofstream&  outFile ) const**
**{**
**	****PrintHelper ( root,  outFile ) ;**** **
**}**
**template< class  ItemType >***** ***
**void   PrintHelper ( TreeNode<ItemType>********* ptr,  ofstream&  outFile )**
**{      if  ( ptr != NULL )    **
**       ****{**
**	****PrintHelper( ptr->left , outFile ) ;****	****// Print left subtree**
**       ****	****outFile  <<  ptr->info ;****	****	****	**
**	****PrintHelper( ptr->right, outFile ) ;****	****// Print right subtree**
**        ****}**
**}**

** **

**Preorder Traversal: ****  J E A H T M Y**

** ‘****E’**

**‘****A’**

**‘****H’**

**‘****T’**

** ‘****M’**

**‘****Y’**

**tree**

**Print left subtree second**

**Print right subtree last**

**Print first**

** **

** ‘****E’**

**‘****A’**

**‘****H’**

**‘****T’**

** ‘****M’**

**‘****Y’**

**tree**

**Print left subtree first**

**Print right subtree second**

**Print last**

**Postorder Traversal:  ****A H E M Y T J**** **

## template< class  ItemType > 

**template< class  ItemType >***** ***
**TreeType<ItemType> :: ~TreeType (  )****	****	****// DESTRUCTOR**
**{**
**       ****DestroyHelper ( root ) ;**** **
**}**
**template< class  ItemType >***** ***
**void   DestroyHelper ( TreeNode<ItemType>********* ptr )**
***// Post:  All nodes of the tree pointed to by ptr are deallocated.***
**{      if  ( ptr != NULL )    **
**       ****{     **
**	****DestroyHelper ( ptr->left ) ;**
**	****DestroyHelper ( ptr->right ) ;**
**	****delete  ptr ;**
**       ****}**
**}**

## Read Text ...

**Iterative Insertion and Deletion**

## 
Is the depth of recursion relatively shallow?
	Yes.
Is the recursive solution shorter or clearer than the nonrecursive version?
	Yes.
Is the recursive version much less efficient than the nonrecursive version?
	No.

**Is the depth of recursion relatively shallow?**
**	****Yes.**
**Is the recursive solution shorter or clearer than the nonrecursive version?**
**	****Yes.**
**Is the recursive version much less efficient than the nonrecursive version?**
**	****No.**

**Recursion or Iteration?**

- Assume: the tree is well balanced.

## Use a recursive solution when (Chpt. 7):

**The depth of recursive calls is relatively “shallow” compared to the size of the problem.**
**The recursive version does about the same amount of work as the nonrecursive version.**
**The recursive version is shorter and simpler than the nonrecursive solution. **

** ****SHALLOW DEPTH           EFFICIENCY                   CLARITY**

## BST:

Quick random-access with the flexibility of a linked structure
Can be implemented elegantly and concisely using recursion
Takes up more memory space than a singly linked list
Algorithms are more complicated

**Quick random-access with the flexibility of a linked structure**
**Can be implemented elegantly and concisely using recursion**
**Takes up more memory space than a singly linked list**
**Algorithms are more complicated**

**Binary Search Trees (BSTs) **** vs. Linear Lists**

**End**