Binary Search Trees
In computer science, a Binary Search Tree (BST) is a type of binary tree that has a special property. It follows an ordering property where the value of every node in the left subtree is less than the value of the root node, and the value of every node in the right subtree is greater than the value of the root node.
Binary search trees have several advantages, including efficient searching, insertion, and deletion operations. The ordering property of BSTs enables these operations to have an average time complexity of O(log n), making them highly efficient.
Let's take a look at an example of creating a binary search tree in C++:
TEXT/X-C++SRC
1#include <iostream>
2using namespace std;
3
4// Definition of a Binary Search Tree node
5struct Node {
6 int data;
7 Node* left;
8 Node* right;
9};
10
11// Function to create a new node
12Node* createNode(int data)
13{
14 Node* newNode = new Node;
15 if (!newNode) {
16 cout << "Memory error\n";
17 return NULL;
18 }
19 newNode->data = data;
20 newNode->left = newNode->right = NULL;
21 return newNode;
22}
23
24int main()
25{
26 // Create an empty Binary Search Tree
27 Node* root = NULL;
28
29 // Insert values into the Binary Search Tree
30 root = createNode(50);
31 root->left = createNode(30);
32 root->right = createNode(70);
33 root->left->left = createNode(20);
34 root->left->right = createNode(40);
35 root->right->left = createNode(60);
36 root->right->right = createNode(80);
37
38 return 0;
39}xxxxxxxxxx43
}using namespace std;// Definition of a Binary Search Tree nodestruct Node { int data; Node* left; Node* right;};// Function to create a new nodeNode* createNode(int data){ Node* newNode = new Node; if (!newNode) { cout << "Memory error\n"; return NULL; } newNode->data = data; newNode->left = newNode->right = NULL; return newNode;}int main(){ // Create an empty Binary Search Tree Node* root = NULL; // Insert values into the Binary Search TreeOUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
