UIUC CS400

C++ Intro

1. C++ is a strongly-typed programming language where every variable has a type, name, value and location in memory.
2. The type of a variable defines the contents of the variable. Every type is either:
   1. Primitive
   2. User-defined
3. Primitive types:
   1. int
   2. char
   3. bool
   4. float
   5. double
   6. void
4. User-Defined types:
   1. std::string
   2. std::vector
   3. many more
5. C++ Programs
   • by c++ standard, it starts with a function int main() return value 0 indicate the program was successful.

     C++ Classes

6. C++ classes encapsulate data and associated functionality into an object

   class Cube {
     public:
    double getVolume();
     private:
    double length_;
   };
   

7. data and functionality are separated into two separate protections: public and private
   • public members can be accessed by client code
   • private members can be accessed within the class itself
8. the interface/header (.h file) to the class is defined separately from the implementation (.cpp file)
9. C++ Header File (.h) defines the interface to the class, which include:
   • declaration of all member variables
   • declaration of all member functions

     class Cube {
       public:
      double getVolume();
      double getSurfaceArea();
      void setLength(double length);
       private:
      double length_;
     };
     

10. C++ Implementation File (.cpp) contains the code to implement the class

    #include "Cube.h"
    double Cube::getVolume() {
      return length_ * length_ * length_;
    }
    double Cube::getSurfaceArea() {
      return 6 * length_ * length_;
    }
    void Cube::setLength(length) {
      length_ = length;
    }
    

    Example client program ```cpp #include “Cube.h”

int main() { Cube c;

c.setLength(3.48); double volume = c.getVolume(); std::cout « “Volume: “ « volume « std::endl; return 0 }

## C++ Standard Library (std)
Standard Library Organization
+ eg: iostream - includes operations for reading and writing to files and console, eg `std::cout`
```cpp
#include <iostream>

int main() {
  std::cout << "Hello World!" << std::endl;
  return 0;
};

• functionalites from the standard library will be part of the std namespace.
• namespaces are used to avoid name conflicts for commonly used names.
• we can import functions into the global space with using ```cpp #include

using std::cout; using std::endl; int main() { cout « “Hello World!” « endl; return 0; };

+ put our `Cube` class into an unique namespace
The header fiile `Cube.h`
```cpp
namespace uiuc {
  class Cube {
    public:
      double getVolume();
      double getSurfaceArea();
      void setLength(double length);
    private:
      double length_;
  };
}

The implementation file Cube.cpp

#include "Cube.h"
namespace uiuc {
  double Cube::getVolume() {
    return length_ * length_ * length_;
  }
  double Cube::getSurfaceArea() {
    return 6 * length_ * length_;
  }
  void Cube::setLength(length) {
    length_ = length;
  }
}

Stack Memory and Pointers

In C++, the programmer has control over the memory and lifecycle of every variable.

1. Stack memory
   • By default, variables live in stack memory.
   • & operator returns the memory address of a variable. ```cpp #include

int main() { int num = 7; std::cout « “Value: “ « num « std::endl; std::cout « “Address: “ « &num « std::endl; return 0; };

```console
Value: 7
Address: 0x7ffc79466564

• Stack memory is associated with the current function and the memory’s lifecycle is tied to the function.
  • When the function returns or ends, the stack memory of that function is released.
  • Stack memory always starts from high addresses and grows down. ```cpp #include

int main() { int num_1 = 7; std::cout « “Value: “ « num_1 « std::endl; std::cout « “Address: “ « &num_1 « std::endl; int num_2 = 1; std::cout « “Value: “ « num_2 « std::endl; std::cout « “Address: “ « &num_2 « std::endl; return 0; };

```console
Value: 7
Address: 0x7ffd9b4eb780
Value: 1
Address: 0x7ffd9b4eb784

1. Pointer
   • A pointer is a variable that stores the memory address of the data
   • simply put: pointers are a level of indirection from the data + In C++, a pointer is defined by adding an * to the type of the variable
   • Integer pointer: int * p = # here int * denotes the variable p is of interger pointer type and the value is the memeory address of num.
2. Dereference Operator
   • Given a pointer, a level of indirection can be ren the dereference operator * ```cpp #include

int main() { int num = 7; int * p = # int q = *p;

std::cout « “value of num is “ « num « std::endl; std::cout « “q is “ « q « std::endl; std::cout « “p is “ « p « ” the address of num.” « std::endl; std::cout « “&p is “ « &p « ” the address of p.” « std::endl; std::cout « “*p is “ « *p « ” gives the value of num.” « std::endl;

p = 42; std::cout « “value of num is “ « num « std::endl; std::cout « “q is “ « q « std::endl; std::cout « “p is “ « p « ” the address of num.” « std::endl; std::cout « “&p is “ « &p « ” the address of p.” « std::endl; std::cout « “p is “ « *p « ” gives the value of num.” « std::endl;

return 0; };

puzzle - `g++ code.cpp` will throw errors and not build. Even with the class makefire it builds, executing the binary will cause seg fault.
```cpp
#include <iostream>
#include "Cube.h"
using uiuc::Cube;

Cube *CreateUnitCube() {
  Cube cube;  // cube is stack allocated instance of class Cube.
  cube.setLength(15);
  return &cube;  // return address of this stack allocated object
}  // once the function ends, the stack memory is released, meaning code executed after the function call may reuse the memory address for cube and write values to it. 

int main() {
  Cube *c = CreateUnitCube();  // pointer c points to an address that maybe overwritten anytime
  someOtherFunction();
  double a = c->getSurfaceArea();
  std::cout << "Surface Area: " << a << std::endl;  // if it even gets excuted, will unlikly output the area
  double v = c->getVolume();
  std::cout << "Volume: " << v << std::endl;
  return 0;
}

// Some other function that does something that uses some stack memory.
// In this code, we calculate the total volume of cubes of length from 0..99.
double someOtherFunction() {
  Cube cubes[100];
  double totalVolume = 0;

  for (int i = 0; i < 100; i++) {
    cubes[i].setLength(i);
    totalVolume += cubes[i].getVolume();
  }

  return totalVolume;

Heap Memory

1. Heap memory
   • Heap memory allows us to create memory independent of the lifecycle of a function.
   • The only way to create heap memory in C++ is with the new operator.
2. new operator
   • The new operator returns a pointer to the memory storing the data - not an instance of the data itself.
   • The new operator will always do three things:
   1. allocate memory on the heap for the data structure
   2. initialize the data structure
   3. return a pointer to the start of the data structure + The memory is only ever reclaimed by the system when the pointer is passed to the delete operator ```cpp int * numPtr = new int;
      /*
3. allocate integer pointer numPtr on the stack
4. allocate integer on the heap */ ```
5. nullptr
   • C++ nullptr is a pointer that points to the memory address 0x0
   • Address 0x0 is reserved and never used by the system
   • Address 0x0 will always generate an ‘segmentation fault’ when accessed
6. -> Arror Operator
   • c->getVolume() is identical to (*c).getVolume()
   • (*c) is dereferencing the pointer to get the instance, then call the member function via .
   • -> is syntatical sugar

     Class Constructors

     When an instance of a class is created, the class constructor sets up the initial state of the instance.

7. Automatic Default Constructor
   • If we do not provide any custom constructors, the C++ compiler provides an automatic default constructor for our class for free.
   • The automatic default constructor will only initialize all member variables to their default values.
   • But if we define any custom constructor, the automatic default constructor will not be provided by complier.
8. Custom Default Constructor:
   • A member function with the same name of the class
   • The function takes zero parameters
   • The function does not have a return type ```cpp class Cube { public: Cube(); // custom default constructor

private: double length_; }

```cpp
#include "Cube.h"

// custom default constructor
Cube::Cube() {
  length_ = 1;
} 

1. Custom Constructors
   • non-default custom constructors require client code to supply arguments:

     Cube::Cube(double length) {
       length_ = length;
     }
     

     Copy Constructors

     In C++, a copy constructor is a special constructor that exists to make a copy of an existing object.

2. Automatic Copy Constructor
   • If we do not provide a custom copy constructor, the C++ compiler provides an automatic copy constructor for our class for free.
   • This free automatic copy constructor will copy the contents of all member variables.
3. Custom Copy Constructor
   • Is a class constructor
   • Has exactly one argument that is const reference of the same type

     Cube::Cube(const Cube & obj) {
       length_ = obj.length_;
     }
     

4. Copy Constructor Invocation Often copy constructors are invoked automatically:
   • Passing an object as a parameter (by value)
   • Returning an object from a function (by value)
   • Initializing a new object ```cpp #include “Cube.h” using Cube;

void foo(Cube cube) {}

int main() { Cube c; // trigger default constructor foo(c); // trigger copy constructor return 0; }

## Copy Assignment Operator
In C++, a copy assignment operator defines the behavior when an object is copied copied using the assignment operator =.
1. Copy Constructor vs. Assignment
  + A copy constructor creates a new object (constructor).
  + An assignment operator assigns a value to an existing object.
  + An assignment operator is always called on an object that has already been constructed.
2. Automatc Assignment operator
  + If we do not provide an assignment operator, the C++ compiler will provides an automatic assignment operator.
  + The automatic assignment operator will copy the contents of all member variables.
3. Custom Assignment Operator
  + A custom assignment operator:
    1. Is a public member function of the class.
    2. Has the function name operator=.
    3. Has a return value of a reference of the class' type.
    4. Has exactly one argument which ust be const reference of the class' type.
  + Eg. `Cube & Cube::operator=(const Cube & obj)`
```cpp
namespace uiuc {
  // default constructor
  Cube::Cube() {
    length_ = 1
  }
  // copy constructor
  Cube::Cube(const Cube & obj) {
    length_ = obj.length_;
  }
  // assignment operator
  Cube & Cube::operator=(const Cube & obj) {
    length_ = obj.length_;
    return *this;
  }
}

#include "Cube.h"
using uiuc::Cube;

int main() {
  Cube c;       // trigger default constructor
  Cube myCube;  // trigger default constructor
  myCube = c;   // trigger assignment operator
  return 0;
}

Variable Storage

In C++, an instance of a variable can be stored directly in memory, accessed by pointer, or accessed by reference.

Cube c;
Cube & r = c;
Cube * ptr = &c;

1. Direct Storage
   • By default, variables are stored directly in memory.
   • The type of a variable has no modifiers.
   • The object takes up exactly its size in memory.
2. Storage by Pointer
   • The type of a variable is modified with an asterisk (*).
   • A pointer takes a “memory address width” of memory, eg. 64 bits on a 64 bit system.
   • The pointer “points” to the allocated space of the object.
3. Storage by Reference
   • A reference is an alias to existing memory and is denoted in the type with an ampersand (&).
   • A reference does not store memory itself, it is only an alias to another variable.
   • The alias must be assigned when the variable is initialized. ```cpp Cube c; int i;

Cube b; int j;

Cube &c; // illegal Cube &d = c; int &k = i;

4. Pass by / Return by
  + by value (default)
  + by pointer (modified with *)
  + by reference (modified with &, acts as an alias)
+ Never return a reference to a stack variable created on the stack of your current function.
## Class Destructor
+ When an instance of a class is cleaned up, the class destructor is the last call in a class's lifecycle.
1. Automatic Default Destructor
  + An automatic default destructor is added to your class if no other destructor is defined.
  + The only action of the automatic default destructor is to call the default destructor of all member objects.
  + An destructor should never be called directly. Instead, it is automatically called when the object's memory is being reclaimed by the system:
    + If the object is on the stack, when the function returns.
    + If the object is on the heap, when delete is used.
2. Custom Destructor
  + To add custom behaviro to the end-of-life of the function, a custom destructor can be defined as:
    + A custom destructor is a member function.
    + The function's destructor is the name of the class preceded by a tilde ~.
    + All destructors have zero arguments and no return type.
```cpp
Cube::~Cube() {}

Template Types

• A template type is a special type that can take on different types when the type is initialized.
• Eg. std::vector uses a template type:

  std::vector<char>
  std::vector<int>
  std::vector<Cube>
  

• std::vector standard library class that provides the functionality of a dynamically growing array with a “templated” type.
  • Defined in: #include <vector>
  • Initialization: std::vector<T> v;
  • Add to (back) oof array: ::push_back(T);
  • Access specific element: ::operator[](unsigned pos);
  • Number of elements: ::size()
• When initializing a “templated” type, the template type goes inside of <> at the end of the type name

  Templated Functions

• A template variable is defined by declaring it before the beginning of a class or function:

  template <typename T>
  class List {
    // ...
    private:
      T data_;
  };
  

template <typename T>
T max(T a, T b) {
  if (a > b) { return a; }
  return b;
}

• Templated variables are checked at compile time, which allows for errors to be caught before running the program.

  Inheritance

• Inheritance allows for a class to inherit all member functions and data from a base class into a derived class.
• Generic to Specialized: A base class is a generic form of a specialized, derived class. ```cpp class Shape { public: Shape(); Shape(double width); double getVolume() const; private: double width_; };

class Cube : public Shape { public: Cube(double width, HSLAPixel color); double getVolume() const; private: HSLAPixel color_; };

1. Initialization
  + When a derived class is instantiated, the derived class must construct the base class:
    + `Cube` must construct `Shape`
    + By default, uses default constructor
    + Custom constructor can be used with an `initialization list`
```cpp
Cube::Cube(double width, HSLAPixel color) : Shape(width) {
  color_ = color;
}

double Cube::getVolume() const {
  return getWidth() * getWidth() * getWidth();
}

1. Access Control
   • When a base class is inherited, the derived class:
   • Can access all public members of the base class
   • Can not access private members of the base class
2. Initializer List
   • The syntax to initialize the base class is called the initializer list and can be used for several purposes:
   • Initialize a base class
   • Initialize the current class using another Constructor
   • Initialize the default values of member variables

     Arrays

     An array stores data in blocks of sequential memory.

     int values[10] = {2,3,5,7,11,13,15,17,21,23};
     

3. Array Limitations:
4. All data in an array must be of the same type + we can calculate the address of the nth element by adding index offset * sizeof type to the address of the first element.
5. Arrays have a fixed capacity + array must be expanded(make a new larger array and copy over all the data) when reached capacity.

   int main() {
     int values[10] = { 2, 3, 5, 7, 11, 13, 15, 17, 21, 23 };
     std::cout << sizeof(int) << std::endl;
     int offset = (long)&(values[2]) - (long)&(values[0]);
     std::cout << offset << " should be twice of the number above" << std::endl;
     return 0;
   }
   

6. std::vector
   • Which implements an array that dynamically grows in size automatically. ```cpp int main() { std::vector cubes{ Cube(11), Cube(42), Cube(400) };

// Examine capacity:
std::cout « “Initial Capacity: “ « cubes.capacity() « std::endl; cubes.push_back( Cube(800) ); std::cout « “Size after adding: “ « cubes.size() « std::endl; std::cout « “Capacity after adding: “ « cubes.capacity() « std::endl;

// Using pointer arithmetic, ask the computer to calculate // the offset from the beginning of the array to [2]: int offset = (long)&(cubes[2]) - (long)&(cubes[0]); std::cout « “Memory separation: “ « offset « std::endl;

// Find a specific target cube in the array: Cube target = Cube(400); for (unsigned i = 0; i < cubes.size(); i++) { if (target == cubes[i]) { std::cout « “Found target at [” « i « ”]” « std::endl; } } return 0; }

## Linked Memory
Linked memory stores data together with a "link" to the location (in memory) of the next list node.
1. List Nodes: refers to pair of both the data and the link.
```cpp
template <typename T>
class ListNode {
  public:
    T & data;
    ListNode *next;
    ListNode(T & data) : data(data), next(nullptr) {}
};

1. Linked List: zero or more ListNode elements linked together form a Linked List.
   • A pointer called the “head pointer” stores the link to the begining of the list.
   • A pointer to NULL marks the end of the list. ```cpp template class List { public: const T & operator[](unsigned index); void insertAtFront(const T & data);

private: class ListNode { public: const T & data; ListNode *next; ListNode(const T & data) : data(data), next(nullptr) {} } ListNode *head_; }

3. Linked List:
  1. get: return element at index k
  2. insert: add an element to the list.
```cpp
template <typename T>
const T & List<T>::operator[](unsigned index) {
  ListNode *node = head_;
  while (index > 0 && node->next != nullptr) {
    node = node->next;
    index--;
  }
  return node->data;
}

template <typename T>
void List<T>::insertAtFront(const T & data) {
  ListNode *node = new Listnode(data);
  node->next = head_;
  head_ = node;
}

Run-Time Analysis

1. Array Resize: double each time
   • total work: O(N)
   • average work per element: O(1)
2. Access nth element
   • Array: O(1) direct access via offset formula
   • LinkedList: O(N) traverse elements to reach the index
3. Insert at front
   • Array: O(1) amortized constant when array size is doubled when copied
   • LinkedList: O(1) fixed constant by adding a new node
4. Find data
   • Array: O(N)
   • LinkedList: O(N)
5. Find data in sorted collection
   • Array: O(logN) using binary search
   • LinkedList: O(N)
6. Insert after the given element
   • Array: O(N) require copying up to half of the array to make space for the new element
   • O(1): fixed constant by adding a new node
7. Delete after the given element
   • Arrary: O(N) require copying up to half of the array to remove the blank space
   • LinkedList: O(1) fixed constant by set link to nullptr

     Queue

     A queue is a first-in-first-out data structure.

8. Abstract Data Type
   • A structure(like array, list)’s Abstract Data Type(ADT) is how data interacts with the structure
   • It is not an implementation, it is a description
9. Queue ADT
   • create: create an empty queue
   • push: adds data to the back of the queue
   • pop: remove data from the front of the queue
   • empty: check if queue is empty Queue can be implemented with array or doubly linked list and get O(1) run time for all 4 operations

     Stack

     A stack is a last-in-frist-out data structure

10. Queue ADT
    • create: create an empty stack
    • push: adds data to the top of the stack
    • pop: remove data from the top of the queue
    • empty: check if stack is empty Stack can be implemented with array or singly linked list and get O(1) run time for all 4 operations

      Tree Terminology

      A tree is a linked structure with a sense of ancestry (parent, children, siblings, and more)

    • Each element in the tree is a node
    • Each connection between two nodes is an edge
    • Trees must always contain a root node that has no incoming edges
    • Nodes that contain no outgoing edges are called leaf nodes
    • In a tree, the nodes will store data and maybe labeled
    • Edges do not have names, but are referred to by the nodes they connect
    • Every node, except the root node, has exactly one parent node
    • A node’s children are the nodes with that node as it’s parent
    • Most ancestry terms apply as expected: sibling, ancestor, grandchildren, grandparent etc
    • To be a tree, three conditions must be true:
11. Must have a root
12. Must have directed edges
13. Must not have a cycle
    • We say a tree is a “rooted, directed acyclic” structure

      Binary Tree

      A binary tree is a tree where every node has at most two children We will label every child as either left child or right child ```cpp // BinaryTree.h template class BinaryTree { public:

private: class TreeNode { public: T & data; TreeNode *left, *right; TreeNode(T & data) : data(data), left(nullptr), right(nullptr) {} }; TreeNode *root_; };

+ Binary Tree Property:
  1. height: number of edges in the longest path from root to leaf.
  2. full: a binary tree is full if and only if every node has either zero children or two children.
  3. perfect: a binary tree is perfect if and only if all interior nodes have two children and leaves are at the same level.
  4. complete: a binary tree is complete if and only if the tree is perfect up until the last level and all leaf nodes on the last level are pushed to the left.
## Binary Search Tree
A binary search tree (BST) is an ordered binary tree capable of being used as a search structure 
+ A binary tree is a BST if for every node in the tree:
  + Nodes in the left subtree are less than itself
  + Nodes in the right subtree are greater than itself
+ Dictionary ADT: a dictionary associates a key with data
  + find: finds the data associated with a key in the dictionary
  + insert: adds a key/data pair to the dictionary
  + remove: removes a key from the dictionary
  + empty: returns true if the dictionary is empty
+ BST-based Dictionary:
  + Use BST to implement a dictionary will store both a key and data at every node
+ BST::remove
  + Zero children: simple, delete the node
  + One child: simple works like a linked list
  + Two children:
    1. Find the in-order-predecessor (IOP) of the node to be removed. - the largest node < node
    2. Swap with the IOP
    3. Remove the node in it's new position
```cpp
template <typename K, typename D>
class Dictionary {
  public:
    Dictionary();
    const D & find(const K & key);
    void insert(const K & key, const D & data);
    const D & remove(const K & key);

  private:
    class TreeNode {
      public:
        const K & key;
        const D & data;
        TreeNode *left, *right;
        TreeNode(const K & key, const D & data)
          : key(key), data(data), left(nullptr), right(nullptr) {}
    };

  TreeNode *head_;
}

template <typename K, typename D>
typename Dictionary<K, D>::TreeNode *& Dictionary<K, D>::_find(
  const K & key, TreeNode *& cur) const {
    if (cur == nullptr) { return cur; }
    else if (cur->key == key) { return cur; }
    else if (cur->key > key) { return _find(key, cur->left); }
    else { return _find(key, cur->right); }
}

template <typename K, typename D>
const D & Dictionary<K, D>::find(const K & key) {
  TreeNode *& node = _find(key, head_); // *& is a reference / alias to the pointer
  if (node == nullptr) { throw std::runtime_error("key not found"); }
  return node->data;
}

template <typename K, typename D>
void Dictionary<K, D>::insert(const K & key, const D & data) {
  TreeNode *& node = _find(key, head_);
  node = new TreeNode(key, data);
}

template <typename K, typename D>
const D & Dictionary<K, D>::remove(const K & key) {
  TreeNode *& node = _find(key, head_);
  return _remove(node);
}

template <typename K, typename D>
const D & Dictionary<K, D>::_remove(TreeNode *& node) {
  if (node->left == nullptr && node->right == nullptr) {
    const D & data = node->data;
    delete(node);
    node = nullptr;
    return data;
  } 
  if (node->left != nullptr && node->right == nullptr) {
    const D & data = node->data;
    TreeNode *temp = node;
    node = node->left;
    delete(temp);
    return data;
  }
  if (node->left == nullptr && node->right != nullptr) {
    const D & data = node->data;
    TreeNode *temp = node;
    node = node->right;
    delete(temp);
    return data;
  }
  TreeNode *& iop = _iop( node->left );
  _swap( node, iop );
  return _remove( node );
}

BST analysis

1. There are n! different ways to create BSTs with the same data
   • The worst-case BST will have a height proportional to the number of nodes
   • An average BST will have a height proportional to the logarithm of the number of nodes
2. Using a height balance factor, we can formalize if a given BST is balanced
   • height balance factor of a node is the difference in height between its two subtrees
   • A balanced BST is a BST where every node’s balance factor has a magnitude of 0 or 1

     Balanced BST

     Balanced BSTs are height-balanced trees that ensures nearly half of the data is located in each subtree

   • BST Rotation Summary | rotation | balance factor of the lowest point of imbalance | balance factor of the node in the direction of imbalance | |———————|————————————————-|———————————————————-| | left rotation | 2 | 1 | | right rotation | -2 | -1 | | right-left rotation | 2 | -1 | | left-right rotation | -2 | 1 |
   • BST rotations restore the balance property to a tree after an insert causes a BST to be out of balance
     • rotations are local operations
     • rotations do not impact the broader tree
     • rotations run in O(1) time
   • These trees are called “AVL Trees”

     AVL (Adelson-Velsky and Landis) Analysis

     AVL Trees is an implementation of a balanced BST

     • It starts with a BST implementation and adds two key ideas:
   1. Maintains the height at each node
   2. Maintains the balance factor after insert and remove
      • Everything about finding, inserting, and removing from a BST remains true.
      • In an AVL tree, we add steps to ensure we maintain balance
        • Extra work on insert/remove
        • To quickly compute the balance factor, AVL trees store the height of every node as part of the node itself
      • Insert
3. Insert at proper place
4. check for imbalance
5. Rotate, if necessary
6. Update height ```cpp template <typename K, typename D> void AVL<K, D>::_ensureBalance(TreeNode *& cur) { int balance = height(cur->right) - height(cur->left); if ( balance == -2 ) { int l_balance = height(cur->left->right) - height(cur->left->left); if ( l_balance == -1 ) _rotateRight( cur ); else _rotateLeftRight( cur ); } else if (balance == 2) { int r_balance = height(cur->right->right) - height(cur->right->left); if ( r_balance == 1 ) _rotateLeft( cur ); else _rotateRightLeft( cur );
   } _updateHeight(cur); }

template <typename K, typename D> void AVL<K, D>::_updateHeight(TreeNode *& cur) { cur->height = 1 + max(height(cur->left), height(cur->right)); }

template <typename K, typename D> void AVL<K, D>::_rotateLeft(TreeNode *& cur) { TreeNode *x = cur; TreeNode *y = cur->right;

x->right = y->left; y->left = x; cur = y;

_updateHeight(x); _updateHeight(y); }

```cpp
template <typename K, typename D>
const D & AVL<K, D>::_iopRemove(TreeNode *& node, TreeNode *& iop) {
  if (iop->right != nullptr) {
    const D & d = _iopRemove(node, iop->right);
    if (iop) _ensureBalance(iop); 
    else return d;
  }
  _swap(node, iop);
  std::swap(node, iop);

  return _remove(iop);
}

B-Tree

Each tree node contains multiple keys: order m

• For a B-tree “of order m”
  1. All keys within a node are in sorted order
  2. Each node contains no more than m-1 keys
  3. Each internal node can have at most m children, so a B-tree of order m is like an m-way tree
  4. Each internal node has exactly one more child than key
     • A root node can be a leaf or have [2, m] children
     • Each non-root, internal node has [ceil(m/2), m] children
  5. All leaves are on the same level

     Hashing