Binary Search Trees (BST)¶
A binary search tree is a type of binary tree whose nodes of the left sub-tree are less than that node’s value and the nodes of the right sub-tree are greater than that node’s value.
5
3 8
1 4 10
Marshall
Lily Robin Ted
Barney
Here is the interface of a BST:
- Search it for a value
- Insert an item
- Delete an item
- Find the height
- Traverse it
- Free the memory
Searching a BST:
Algorithm: 1. Start at the root of the tree 2. While a node is not nullptr
- If the inputted value is equal to the current node’s value, return true
- If it is less than the current node’s value, go left
- If it is greater than the current node’s value, go right
- If the node is nullptr, return false
Code Iterative Version:
bool search(int value, Node *ptr)
{
while (ptr != nullptr)
{
if (value == ptr->value)
return true;
else if (value < ptr->value)
ptr = ptr->left;
else
ptr = ptr->right;
}
return false;
}
Code Recursive Version:
bool search(int value, Node *ptr)
{
if (ptr == nullptr)
return false;
else if (value == ptr->value)
return true;
else if (value < ptr->value)
return (search(value, ptr->left));
else
return (search(value, ptr->right));
}
d
b e
a c
Example:
Search for c
c < d, go left
Node is c
c > b, go right
Node is c
Return true
Example:
Search for e
e > d, go right
Node is e
Return true
Example:
Search for f
f > d, go right
Node is f
f > e, go right
Node is nullptr
Return false
The average big-O of this search, for a BSt with n values, is O(log(n)).
The worst case big-O is O(n).
Worst case:
z
y
x
w
v
u
etc.
Inserting an item into a BST:
Algorithm:
- If the tree is empty
- Allocate a new node and put the inputted value in
- Point the root pointer to the new node
- Return
- Start at the root of the tree
- While we haven’t returned
- If the value is equal to the current node’s value, return
- If the value is less than the current node’s value
- If there is a left child, go left
- Otherwise allocate a new node and put the value in it. Set the current node’s left pointer to the new node
- If the value is greater than the current node’s value
- If there is a right child, go right
- Otherwise allocate a new node and put the value in it. Set the current node’s right pointer to the new node
Code:
void insert (const string &value)
{
if (root == nullptr)
{
root = new Node(value);
return;
}
Node *cur = root;
for (;;)
{
if (value == cur->value)
return;
if (value < cur->value)
{
if (cur->left != nullptr) // Go left
cur = cur->left;
else
{
cur->left = new Node(value);
return;
}
}
else if (value > cur->value)
{
if (cur->right != nullptr) // Go right
cur = cur->right;
else
{
cur->right = new Node(value);
return;
}
}
}
The average big-O of insertion is O(log(n)) (to find the right place), the worst case is O(n).
You want your BST to be busty and balanced, like a Christmas tree, not a line.
Good:
d
b e
a c
Bad:
e
d
c
b
a
b
a c
d
e
Finding the minimum value of a BST (left-most node):
Code Iterative Version:
int min(Node *ptr)
{
if (ptr == nullptr)
return -1; // empty tree
while (ptr->left != nullptr) // Keep on going left until you get to the left-most
ptr = ptr->left;
return (ptr->value);
}
Code Recursive Version:
int min(Node *ptr)
{
if (ptr == nullptr)
return -1; // empty tree
if (ptr->left == nullptr) // Stop iterating when you get to the left-most
return (ptr->value);
return (min(ptr->left));
}
Finding the maximum value of a BST (right-most node):
Code Iterative Version:
int max(Node *ptr)
{
if (ptr == nullptr)
return -1; // empty tree
while (ptr->right != nullptr) // Keep on going right until you get to the right-most
ptr = ptr->right;
return (ptr->value);
}
Code Recursive Version:
int max(Node *ptr)
{
if (ptr == nullptr)
return -1; // empty tree
if (ptr->right == nullptr) // Stop iterating when you get to the right-most
return (ptr->value);
return (max(ptr->right));
}
Printing out the values of a BST in alphabetical order: This is same as traversing a binary tree with an in-order traversal.
// In-order traversal
void print(Node *cur)
{
if (cur == nullptr)
return;
print(cur->left);
cout << cur->value << endl;
print(cur->right);
}
Big-o of this is O(n).
Freeing all of the memory of the tree: This is the same as traversing a binary tree with post-order traversal
// Post-order traversal
void free(Node *cur)
{
if (cur == nullptr)
return;
free(cur->left);
free(cur->right);
delete cur;
}
This is also O(n).
Deleting a node from a BST: This is more complicated than you may think. There are two major steps.
Algorithm: 1. Find the value in the tree with a standard BST search, but use two pointers: cur and parent. Cur should point to the node you want to delete, parent should point to that node’s parent. 2. If the node is found, determine what case it falls into:
- The node is a leaf
- The node has one child
- The node has two children
- If case a,
- If cur is the root node, set the root pointer to nulltpr
- Otherwise set either the parent’s left or right pointer nullptr (depends on whether cur is the left or right child)
- Delete cur
- If case b,
- Create a grandchild pointer and set it to either cur’s left or right pointer (depends on whether it has a left or a right child)
b. If cur is the root node, set the root pointer to the grandchild b. Otherwise link either the parent’s left or right pointer to the grandchild (depends on whether cur is the left or right child) c. Delete cur
- If case c,
- Find either the largest child (right-most child) of the value’s left sub-tree or the smallest child (left-most child) of the right sub-tree
- Copy that node’s value into temp
- Remove that node
- Copy temp into the node you wish to delete
void delete(Node *cur)
{
Node* parent = nullptr;
cur = root;
while (cur != nullptr)
{
if (value == cur->value)
break; // Found the value
if (value < cur->value)
{
parent = cur;
cur = cur->left;
}
else if (value > cur->value)
{
parent = cur;
cur = cur->right;
}
}
if (cur->left == nullptr && cur->right == nullptr) // Case a
{
if (parent == root)
root = nullptr;
else if (parent->left == cur)
parent->left = nullptr;
else
parent->right = nullptr;
delete cur;
}
else if (cur->left != nullptr || cur->right != nullptr) // Case b
{
Node *grandchild;
if (cur->left != nullptr)
grandchild = cur->left;
else
grandchild = cur->right;
if (parent == cur)
root = grandchild;
else if (parent->left == cur)
parent->left = grandchild;
else if (parent->right == cur)
parent->right = grandchild;
delete cur;
}
else if (cur->left != nullptr && cur->right != nullptr) // Case c
{
Node *ptr;
if (cur->left != nullptr)
{
ptr = cur->left;
while (ptr->right != nullptr)
ptr = ptr->right;
}
else // If there isn't a left child
{
ptr = cur->right;
while (ptr->left != nullptr)
ptr = ptr->left;
}
int temp = ptr->value;
if (ptr->left == nullptr && ptr->right == nullptr)
// Delete it with case a
if (ptr->left != nullptr || ptr->right != nullptr)
// Delete it with case b
cur->value = temp;
}
}