Binary Search Trees

  • Binary search trees use the concepts underpinning the binary search algorithm to create a dynamic data structure. The key word here is dynamic. Unlike sorted arrays, binary search trees support the efficient addition and removal of elements in addition to searches, making them the perfect blend of the algorithmic efficiency of binary search and the adaptability of dynamic data structures. They also make for wonderful decorative mobiles for any room.

../_images/tree.png

  • This is what one looks like. Isn’t it cool? Also I can add images now it’s really easy lowkey.

  • Nodes are a good example of a search tree, cuz they’re like, data that connects to more data.

  • It’s a lot like using a system like linux where everything is all connected to your root or whatever

  • We search a binary search tree by walking down from the root node. At each step, we determine whether to explore the left or right subtree by comparing the value at the current node with the target value.

  • Basically, exploring a node tree is a binary search but it can branch out and have a bit more depth to itself

  • Really good if your data can be used for multiple things, and it’s all interconnected. An array can still work for simpler things though. It’s like my mom always said, KISS: Keep It Simple, Stupid.

#include <iostream>
using namespace std;

// Define a node in the Binary Search Tree
struct Node {
int data;          // Value stored in the node
Node* left;        // Pointer to the left child
Node* right;       // Pointer to the right child

// Constructor to initialize the node
Node(int value) {
data = value;
left = right = nullptr;
}
};

// Class for Binary Search Tree operations
class BST {
private:
Node* root;

// Helper function for insertion (recursive)
Node* insert(Node* node, int value) {
if (node == nullptr) {
// Create a new node if reached a null spot
return new Node(value);
}

if (value < node->data) {
// Insert in the left subtree
node->left = insert(node->left, value);
} else if (value > node->data) {
// Insert in the right subtree
node->right = insert(node->right, value);
}
// If value == node->data, do nothing (no duplicates)

return node;
}

// Helper function to search a value in the tree
bool search(Node* node, int value) {
if (node == nullptr) {
return false; // Value not found
}

if (value == node->data) {
return true; // Value found
} else if (value < node->data) {
return search(node->left, value); // Search left
} else {
return search(node->right, value); // Search right
}
}

// Helper function for in-order traversal
void inOrderTraversal(Node* node) {
if (node == nullptr) return;

inOrderTraversal(node->left);       // Visit left subtree
cout << node->data << " ";          // Visit current node
inOrderTraversal(node->right);      // Visit right subtree
}

public:
// Constructor to initialize BST
BST() {
root = nullptr;
}

// Public insert function
void insert(int value) {
root = insert(root, value);
}

// Public search function
bool search(int value) {
return search(root, value);
}

// Public in-order traversal function
void displayInOrder() {
cout << "In-order traversal: ";
inOrderTraversal(root);
cout << endl;
}
};

// Main function to demonstrate BST operations
int main() {
BST tree;

// Insert values
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);

// Display the tree (in-order should print sorted values)
tree.displayInOrder();

// Search for some values
int key = 40;
if (tree.search(key)) {
cout << "Found " << key << " in the tree.\n";
} else {
cout << key << " not found in the tree.\n";
}

key = 90;
if (tree.search(key)) {
cout << "Found " << key << " in the tree.\n";
} else {
cout << key << " not found in the tree.\n";
}

return 0;
}