Can someone teach me how to code left and right rotation of binary search tree i
ID: 3737741 • Letter: C
Question
Can someone teach me how to code left and right rotation of binary search tree in C++.
I added my bst c++ code in below.
#include <iostream>
#include <cstdlib>
using namespace std;
class BinarySearchTree {
private:
struct node {
int key;
node* left;
node* right;
};
node* root;
int *catephillar;
void add_leaf_Private(int key, node* newNode);
void print_inorder_Private(node* newNode);
node* get_node_Private(int key, node* newNode);
node* find_smallest_Private(node* newNode);
public:
BinarySearchTree();
~BinarySearchTree();
node* create_leaf(int key);
void add_leaf(int key);
void print_inorder();
node* get_node(int key);
int get_root_key();
void print_children(int key);
node* find_smallest();
};
BinarySearchTree::BinarySearchTree() {
root = NULL;
}
BinarySearchTree::~BinarySearchTree() {
}
BinarySearchTree::node* BinarySearchTree::create_leaf(int key) {
node* newNode = new node;
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
void BinarySearchTree::add_leaf(int key) {
if (root == NULL) {
root = create_leaf(key);
}
else {
add_leaf_Private(key, root);
}
}
void BinarySearchTree::add_leaf_Private(int key, node* newNode) {
if(key < newNode->key){
if (newNode->left != NULL) {
add_leaf_Private(key, newNode->left);
}
else {
newNode->left = create_leaf(key);
}
} else if (key > newNode->key) {
if (newNode->right != NULL) {
add_leaf_Private(key, newNode->right);
}
else {
newNode->right = create_leaf(key);
}
}
else {
cout << "The key " << key << " is in tree already" << endl;
}
}
void BinarySearchTree::print_inorder() {
if (root == NULL) {
cout << "The tree is empty" << endl;
}
else {
print_inorder_Private(root);
}
}
void BinarySearchTree::print_inorder_Private(node* newNode) {
if (newNode->left != NULL) {
print_inorder_Private(newNode->left);
}
cout << newNode->key << " ";
if (newNode->right != NULL) {
print_inorder_Private(newNode->right);
}
}
BinarySearchTree::node* BinarySearchTree::get_node(int key) {
if (root == NULL) {
cout << "The tree is empty" << endl;
}
else {
return get_node_Private(key, root);
}
}
BinarySearchTree::node* BinarySearchTree::get_node_Private(int key, node* newNode) {
if (newNode != NULL) {
if (key == newNode->key) {
return newNode;
} else if (key < newNode->key){
return get_node_Private(key, newNode->left);
} else if (key > newNode->key){
return get_node_Private(key, newNode->right);
}
} else {
return NULL;
}
}
int BinarySearchTree::get_root_key() {
if (root != NULL) {
return root->key;
}
else {
return -99999;
}
}
void BinarySearchTree::print_children(int key) {
node* newNode = get_node(key);
if (newNode != NULL) {
cout << "Parent Node = " << newNode->key << endl;
newNode->left == NULL ?
cout << "Left child is NULL" << endl :
cout << "Left child is " << newNode->left->key << endl;
newNode->right == NULL ?
cout << "Right child is NULL" << endl :
cout << "Right child is " << newNode->right->key << endl;
}
else {
cout << key << " is not in the tree" << endl;
}
}
BinarySearchTree::node* BinarySearchTree::find_smallest() {
if (root == NULL) {
return NULL;
}
return find_smallest_Private(root);
}
BinarySearchTree::node* BinarySearchTree::find_smallest_Private(node* newNode) {
if (newNode->left == NULL) {
return newNode;
}
else {
find_smallest_Private(newNode->left);
}
}
Explanation / Answer
This is a C++ Program to perform Left Rotation in Binary Search Trees. In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations. There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of a rotation depends on the side which the tree nodes are shifted upon whilst others say that it depends on which child takes the root’s place (opposite of the former). This article takes the approach of the side where the nodes get shifted to.
Here is source code of the C++ Program to Perform Left Rotation on a Binary Search Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.