Binary Search Trees: Generic Traversal and Function Objects

Chapter 19

• In a traversal algorithm, “visiting” may mean different things.

  • For example, outputting the values, updating the values, and calculating results.

• Problems:

  • Repeatedly implementing a specific traversal algorithm for each function.

  • Must have access to the internals of the tree.

• The Solution: Write a generic traversal function that accepts a function as a parameter.

• In C++, a function name without parentheses is considered a pointer to the function.

• To specify a function as a formal parameter to another function,

  1. specify the function type (e.g., void),

  2. the name as a pointer (e.g., (*visit)),

  3. the parameter types (e.g., (int, double)).

• For example,

  void funcParamFunc1(void (*visit) (int));
  
  template<typename Type>
  void funcParamFunc2(void (*visit) (Type&));

Generic Traversal Example

A recursive member function that accepts a node to tree to traverse and a function to call at each node.

template<typename Type>
void BinarySearchTree<Type>::inorder(Node *root,
      void (*visit)(Type& value)) {
  if (root != nullptr)  {
    inorder(root->left, visit);

    visit(root->info);

    inorder(root->right, visit);
  }
}

Function Objects (a.k.a. Functors)

• In short, and object that looks like a function, but that
  can maintain state.

• A function object is an object class/struct that overloads operator().

• Can be passed to a generic traversal function instead of a function pointer.

Function Object: Example Definition

template <typename Type>
struct SumValues {
  Type sum;

  // Constructor initializes sum to 0
  SumValues() : sum(0) {}

  // Overloaded operator() to accumulate sum
  void operator()(Type data) {
    sum += data;
  }
};

Function Object: How it Works

SumValues funObj;

funObj(10);
funObj(20);

std::cout << funObj.sum << '\n'; // 30

Function Object: Example Generic Traversal

template<typename Type>
template<typename Func>
void BinarySearchTree<Type>::preorderTraversal( Node* pCurr, Func& functor)
{
  if (pCurr != nullptr)
  {
    functor(pCurr->value); // visit the node
    preorderTraversal(pCurr->pLeft, functor);
    preorderTraversal(pCurr->pRight, functor);
  }
}

template<typename Type>
template<typename Func>
void BinarySearchTree<Type>::preorderTraversal( Func& functor)
{
  preorderTraversal(mpRoot, functor);
}

BinarySearchTree<int> tree{VALUES, SIZE};
SumValues<int> sumObj; // Instantiate functor

tree.preorderTraversal(sumObj);

std::cout << "Sum: " << sumObj.sum << '\n';

Self-Balancing Binary Search Trees

• The worst-case performance for searching is .

• Self-Balancing Binary Trees automatically minimize the tree’s height when performing insertion and deletion operations.

• Searching (and therefore insertion and deletion) becomes (i.e., asymptotically optimal) in the worst case (and may average for some operation depending on the implementation).

• Disadvantage: Algorithms are more complicated (especially if duplicates are allowed).

Examples:

• 2–3
• AA
• AVL
• Red Black
• Scapegoat
• Splay
• Treap
• etc.

Example of Balancing using Rotation

Example of how an unbalanced tree becomes balanced in two steps of rotations.

Example of how an unbalanced tree becomes balanced in two steps of rotations.

Lab 15: Binary Trees (Part 2)

Let’s take a look at the lab based on today’s lecture.