UIUC CS400
C++ Intro
- C++ is a strongly-typed programming language where every variable has a type, name, value and location in memory.
- The type of a variable defines the contents of the variable. Every type is either:
- Primitive
- User-defined
- Primitive types:
- int
- char
- bool
- float
- double
- void
- User-Defined types:
- std::string
- std::vector
- many more
- C++ Programs
- by c++ standard, it starts with a function
int main()
return value0
indicate the program was successful.C++ Classes
- by c++ standard, it starts with a function
- C++ classes encapsulate data and associated functionality into an object
class Cube { public: double getVolume(); private: double length_; };
- 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
- the interface/header (.h file) to the class is defined separately from the implementation (.cpp file)
- 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_; };
- 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.
- 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
- 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 = #
hereint *
denotes the variablep
is of interger pointer type and the value is the memeory address ofnum
.
- Dereference Operator
- Given a pointer, a level of indirection can be ren the dereference operator *
```cpp
#include
- 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
- 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.
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:
- allocate memory on the heap for the data structure
- initialize the data structure
- 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;
/*
- The
- allocate integer pointer numPtr on the stack
- allocate integer on the heap */ ```
nullptr
- C++
nullptr
is a pointer that points to the memory address0x0
- Address 0x0 is reserved and never used by the system
- Address 0x0 will always generate an ‘segmentation fault’ when accessed
- C++
->
Arror Operatorc->getVolume()
is identical to(*c).getVolume()
(*c)
is dereferencing the pointer to get the instance, then call the member function via.
->
is syntatical sugarClass Constructors
When an instance of a class is created, the class constructor sets up the initial state of the instance.
- 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.
- 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;
}
- 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.
- non-default custom constructors require client code to supply arguments:
- 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.
- 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_; }
- 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;
- 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.
- 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.
- 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()
- Defined in:
- When initializing a “templated” type, the template type goes inside of
<>
at the end of the type nameTemplated 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();
}
- 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
- 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};
- Array Limitations:
- 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.
- 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; }
std::vector
- Which implements an array that dynamically grows in size automatically.
```cpp
int main() {
std::vector
cubes{ Cube(11), Cube(42), Cube(400) };
- Which implements an array that dynamically grows in size automatically.
```cpp
int main() {
std::vector
// 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) {}
};
- 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
- Array Resize: double each time
- total work: O(N)
- average work per element: O(1)
- Access nth element
- Array: O(1) direct access via offset formula
- LinkedList: O(N) traverse elements to reach the index
- 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
- Find data
- Array: O(N)
- LinkedList: O(N)
- Find data in sorted collection
- Array: O(logN) using binary search
- LinkedList: O(N)
- 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
- 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.
- 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
- 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
- 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:
- Must have a root
- Must have directed edges
- 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:
- We say a tree is a “rooted, directed acyclic” structure
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
- 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
- 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:
- Maintains the height at each node
- 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
- Insert at proper place
- check for imbalance
- Rotate, if necessary
- 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”
- All keys within a node are in sorted order
- Each node contains no more than m-1 keys
- Each internal node can have at most m children, so a B-tree of order m is like an m-way tree
- 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
- All leaves are on the same level
Hashing