Smart Insert Function For Trees
So, I was trying to check if the tree that I had made using a pre and an inOrder traversal of some elements is correct or not. And for that, I had to manually create that Tree and then perform preOrder traversal in it. But the problem arising here was that I had to manually create so many nodes and then assign all the pointers manually too which was too much of a work. So I have made a smartInsert function to insert the character elements in a tree, by passing the root node, the character to insert and lastly, the position in the form of a string, like-->"llr" which means go to left left and finally insert at right.
#include <bits/stdc++.h>
// #include<iostream>
using namespace std;
/*
* 14th November 2022
* Code to check BST and AVL Trees' answers
*
*/
// Node for AVL Tree
typedef struct node{
struct node* left;
struct node* right;
int data,height;
}node;
// Node for Tree containing Chars
typedef struct char_node{
char elem;
struct char_node* left;
struct char_node* right;
}char_node;
// For Creating integer nodes
struct node* createNode(int key){
struct node* newNode=(node*)malloc(sizeof(node));
newNode->left=NULL;
newNode->right=NULL;
newNode->height=1;
newNode->data=key;
return newNode;
}
// To get height of a node in AVL Tree
int getHeight(node* nod){
if(nod==NULL){
return 0;
}
return nod->height;
}
// To get the Balance Factor
int getBalanceFactor(node* nod){
if(nod==NULL){
return 0;
}
return getHeight(nod->left)-getHeight(nod->right);
}
// Rotations(left and right)
node* leftR(node* nod){
node* x=nod->right;
node* y=x->left;
x->left=nod;
nod->right=y;
return x;
}
node* rightR(node* nod){
node* x=nod->left;
node* y=x->right;
x->right=nod;
nod->left=y;
return x;
}
/* *******THIS FUNCTION HAS SOME LOGICAL ERROR*********
*
* Inserting in an AVL Tree, and then rotating acc to the
* requirement
*
*/
struct node* insert(node* nod,int key){
// Will insert a key into an AVL Tree
if(nod==NULL){
return createNode(key);
}
if(key<nod->data){
nod->left=insert(nod->left,key);
}
else if(key==nod->data){
cout<<"Wrong insertion! Already Exists!\n";
return NULL;
}
else{
// When key is greater than node's data
nod->right=insert(nod->right,key);
// return nod;
}
return nod;
nod->height=1+max(getHeight(nod->left),getHeight(nod->right));
int bf=getBalanceFactor(nod);
// Handling LL insertion
if(bf>1 && key<nod->left->data){
nod=rightR(nod);
}
// Handling RR insertion
if(bf<-1 && key>nod->right->data){
nod=leftR(nod);
}
// Handling LR rotation
if(bf>1 && key>nod->left->data){
nod->left=leftR(nod->left);
nod=rightR(nod);
}
// Handling RL rotation
if(bf<-1 && key<nod->right->data){
nod->right=rightR(nod->right);
nod=leftR(nod);
}
return nod;
}
// Pre and In Order traversals for Trees containing Ints
void preOrder(node* root){
if(root!=NULL){
cout<<root->data<<" ";
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(node* root){
if(root!=NULL){
inOrder(root->left);
cout<<root->data<<" ";
inOrder(root->right);
}
}
// A Try for some idea, needs more work
char_node* insert_char(char_node* node1,char_node* node2,char choice){
if(node1==NULL or node2==NULL){
cout<<"Don't Goof Around!\n";
return NULL;
}
if(choice=='l'){
node1->left=node2;
}
else{
node1->right=node2;
}
return node1;
}
char_node* cNode(char key){
char_node* n=(char_node*)malloc(sizeof(char_node));
n->left=NULL;
n->right=NULL;
n->elem=key;
return n;
}
/** The Smart Insert Function **/
char_node* smartInsert(char_node* root,char key,string s){
int n=s.size();
int i;
char_node* ptr=root;
// Making a New Node To insert at the desired position
char_node* new_node=(char_node*)malloc(sizeof(char_node));
new_node->left=NULL;
new_node->right=NULL;
new_node->elem=key;
for(i=0;i<n-1;i++){
if(s[i]=='l'){
ptr=ptr->left;
}
else{
ptr=ptr->right;
}
}
if(s[i]=='l'){
// Insert at the left position it there's on elem
if(ptr->left!=NULL){
cout<<"There's an element at the selected postition!\n";
return root;
}
ptr->left=new_node;
}else{
// Insert at the right position if there's no elem
if(ptr->right!=NULL){
cout<<"There's an element at the selected postition!\n";
return root;
}
ptr->right=new_node;
}
return root;
free(ptr);
}
// PreOrder Traversal in Tree containing chars
void preOrderChar(char_node* root){
if(root!=NULL){
cout<<root->elem<<" ";
preOrderChar(root->left);
preOrderChar(root->right);
}
}
int main() {
char_node* F=cNode('F');
char_node* A=cNode('A');
F->left=A;
F=smartInsert(F,'K',"lr");
F=smartInsert(F,'C',"lrl");
F=smartInsert(F,'E',"ll");
F=smartInsert(F,'D',"r");
F=smartInsert(F,'G',"rr");
F=smartInsert(F,'H',"rl");
F=smartInsert(F,'B',"rrl");
// The Tree that has been made in the above lines:-
/* This tree was my answer to a Problem
F
/ \
A D
/ \ / \
E K H G
/ /
C B
*/
cout<<"The preOrder traversal of the tree is: ";
preOrderChar(F);
// Below is the work of an AVL Tree
// node* root=insert(root,40);
// root=insert(root,25);
// root=insert(root, 12);
// root=insert(root, 5);
// root=insert(root, 17);
// root=insert(root, 7);
// root=insert(root, 28);
// root=insert(root, 20);
// root=insert(root, 9);
// root=insert(root, 16);
// preOrder(root);
// inOrder(root);
/* The below line is obviously a bad practice, so we
will handle this thing in the insert function and
will always use the insert function to put elements
in the tree(AVL) instead of manually making nodes
point to each other
*/
// root->height=3;
// cout<<"Hola Todo El Mundo!\n";
// cout<<getBalanceFactor(root)<<endl;
// cout<<"Height of root node "<<root->height<<endl;
return 0;
}
Comments
Post a Comment