Binary Search Trees
Binary Search Trees (BSTs) are a type of tree data structure that provide efficient searching and sorting operations. In a BST, each node has at most two child nodes, referred to as the left child and the right child. The key property of a BST is that the value of each node in the left subtree is less than its parent, and the value of each node in the right subtree is greater than its parent.
BSTs are commonly used to store data in sorted order, making it easy to find, insert, and delete elements from the tree.
Operations on Binary Search Trees
- Insert: Adding a new element to the tree in a way that maintains the BST property.
- Search: Finding a particular element in the tree by comparing its value with the values of the nodes.
- Delete: Removing a node from the tree while maintaining the BST property.
To better understand how BSTs work, let's take a look at an example of implementing a BST in C++.
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4struct Node {
5 int data;
6 Node* left;
7 Node* right;
8
9 Node(int value) {
10 data = value;
11 left = nullptr;
12 right = nullptr;
13 }
14};
15
16// Insert function to add a new node to the BST
17Node* insert(Node* root, int value) {
18 if (root == nullptr) {
19 return new Node(value);
20 }
21
22 if (value < root->data) {
23 root->left = insert(root->left, value);
24 } else if (value > root->data) {
25 root->right = insert(root->right, value);
26 }
27
28 return root;
29}
30
31int main() {
32 // Create an empty BST
33 Node* root = nullptr;
34
35 // Insert nodes into the BST
36 root = insert(root, 50);
37 root = insert(root, 30);
38 root = insert(root, 20);
39 root = insert(root, 40);
40 root = insert(root, 70);
41 root = insert(root, 60);
42 root = insert(root, 80);
43
44 // Display the BST
45 cout << "Binary Search Tree: " << root->data << endl;
46 cout << " / \\" << endl;
47 cout << " / \\" << endl;
48 cout << " / \\" << endl;
49 cout << " / \\" << endl;
50 cout << " / \\" << endl;
51 cout << " / \\" << endl;
52
53 return 0;
54}xxxxxxxxxx54
}using namespace std;struct Node { int data; Node* left; Node* right; Node(int value) { data = value; left = nullptr; right = nullptr; }};// Insert function to add a new node to the BSTNode* insert(Node* root, int value) { if (root == nullptr) { return new Node(value); } if (value < root->data) { root->left = insert(root->left, value); } else if (value > root->data) { root->right = insert(root->right, value); } return root;}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
