BST to AVL Don't understand the difference

[GybDjE8b]

How can i change the BNS TO AVL With this code? What is the difference and what do i need to change to make it different?

#include <iostream>
#include <string>


using namespace std;

class Node
{
    public:
    Node(int k, string v){
        key = k;
        value = v;
        leftchild = rightchild = NULL;
    }
    int key;
    string value;
    Node *leftchild;
    Node *rightchild;
};

class BST
{
    public:
    BST(){
        root = NULL;
    }
    void insert(int key, string value);
    string search(int key);
    int getHeight();
    void delete_node(int key);

    private:
    Node *root;
    int delete_internal(Node*& root, int key);
    Node* popMinNode(Node*& root);
    void insert_internal(Node* &root, Node* newptr);
    string search_internal(Node* root, int key);
    int getHeight_internal(Node* root);
};


void BST::delete_node(int key)
{
    int del = delete_internal(root, key);
    if(del == 0)
    {
        cout << "Key not found" << endl;
    }
    else
    {
	cout << "deletion successful" << endl;
    }
}


int BST::getHeight()
{
       return getHeight_internal(root);
}

int BST::getHeight_internal(Node *node)
{
    if(node == NULL)  return -1;
    else
        {
        int h_left = getHeight_internal(node->leftchild);
        int h_right = getHeight_internal(node->rightchild);
        if(h_left >= h_right){
            return h_left + 1;
        }
        else
        {
            return h_right + 1;
        }
    }
}


string BST::search(int key)
{
    return search_internal(root, key);
}

string BST::search_internal(Node *root, int key)
{
    if(root == NULL)
    {
	   return "Not found";
    }
    else if(root->key == key)
    {
	   return root->value;
    }
    else if(root->key > key)
    {
        return search_internal(root->leftchild, key);
    }
    else if(root->key < key)
    {
        return search_internal(root->rightchild, key);
    }
}

int BST::delete_internal(Node*& root, int key)
{
    if(root == NULL)
    {
        return 0;
    }
    else if(root->key > key)
    {
        return delete_internal(root->leftchild, key);
    }
    else if(root->key < key)
    {
        return delete_internal(root->rightchild, key);
    }
    else if(root->key == key)
    {
	if(root->leftchild == NULL and root->rightchild == NULL)
	{
        	delete root;
                root = NULL;
	}
	else if(root->leftchild == NULL and root->rightchild != NULL)
	{
		Node * temp = root->rightchild;
		delete root;
		root = temp;
	}
	else if(root->rightchild == NULL and root->leftchild != NULL)
	{
		Node * temp = root->leftchild;
                delete root;
                root = temp;
	}
	else
	{
		Node* min = popMinNode(root->rightchild);
		cout << "Min key : " << min->key << endl;
		root->key = min->key;
                root->value = min->value;
	}
	return 1;
    }
}

Node* BST::popMinNode(Node*& root)
{
	if(root->leftchild == NULL)
    {
		Node *temp = root;
		root = root->rightchild;
		return temp;
    }
	else
	{
		return popMinNode(root->leftchild);
	}
}


void BST::insert(int key, string value)
{
    Node *newptr = new Node(key, value);
    insert_internal(root, newptr);
}

void BST::insert_internal(Node* &root, Node* newptr)
{
    if(root == NULL)
    {
           root = newptr;
    }
    else if(root->key > newptr->key)
    {
        insert_internal(root->leftchild, newptr);
    }
    else if(root->key < newptr->key)
    {
        insert_internal(root->rightchild, newptr);
    }

}


int main()
{
    cout << "Hello World" << endl;
    BST bst;
    bst.insert(1001,"Hello");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1002,"World");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1003,"What");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1004,"Where");
    cout << "Height : " << bst.getHeight() << endl;
    bst.insert(1000,"Which");
    cout << "Height : " << bst.getHeight() << endl;
    cout << bst.search(1001) << endl;
    bst.delete_node(1001);
    cout << bst.search(1001) << endl;
    cout << "New Height : " << bst.getHeight() << endl;
    return 0;
}

[TheIdeasMan]

https://en.wikipedia.org/wiki/AVL_tree

I Googled that. :+) Wiki and Google are your best friends.

And this, about 3/4 the way down there is a C++ implementation.

https://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/AVL_tree

Some other things, which you should know by now:

Don't have using namespace std;. Google to see why it's bad. Just put std:: before every std thing - it's the best way. You can use find & replace to change everything easily.

std::endl is a little inefficient because it flushes the buffer, just put '\n' in the output instead.

Good Luck!!

[GybDjE8b]

How would i implement the rest? Cause I need to create a new class call AVLSearch
and in that Avlsearch class
i think we need right rotation and left rotation and balance to check if it is balanced but everytime i try to code it i get a lot of error. That my void function can't return a Node.
Can you let me know if this is the right code for rotating

class AVLSearch
{
    friend class Node;
    friend class BST;
    int getbalance;

    private:
    Node *y;
    Node *x;
    Node* rightRotate(Node* y);
    Node* leftRotate(Node* x);
};

Node* AVLSearch::rightRotate(Node *y)
{
    Node *x = y->leftchild;
    Node *T2 = x->rightchild;
    x->rightchild= y;
    y->leftchild = T2;
    return x;
}
Node* AVLSearch::leftRotate(Node *x)
{
    Node *y = x->rightchild;
    Node *T2 = y->leftchild;
    y->leftchild = x;
    x->rightchild = T2;
    return y;
}

[TheIdeasMan]

Hi,

Did you look at the code in the wiki-books link I gave? It's quite clear.

[GybDjE8b]

Yea i did i looked at both of the links and I'm still using it at the moment... It seems totally different with all its different function and everything and my assignment ask me to create another class call AVL and extend the BST that i have on top

So the only think i missing in the AVL tree would be the balance , right , left rotate and when i l look at it and tried to replicate it to fix my program it doesn't work out well and i get a lot of bugs

[TheIdeasMan]

i think we need right rotation and left rotation and balance to check if it is balanced but everytime i try to code it i get a lot of error. That my void function can't return a Node.

If you have errors, then post them and the code here.

By definition void functions cannot return a value.

[GybDjE8b]

Alright yeah i learn my lesson about the void xD that how i changed it to "Node" *AVLSearch
since it is the only way i can return a Node. However I'm getting a error with the getbalance
all the way at the end. It's keep saying getHeight is not declared but i already declared it in the BST and used friend class to access it
and I'm not 100% sure if that is the right function for rotating and to check the balance of the tree
Sorry for wasting your time :S

class AVLSearch
{
    friend class Node;
    friend class BST;
    int getbalance;

    private:
    Node *y;
    Node *x;
    Node* rightRotate(Node* y);
    Node* leftRotate(Node* x);
};

Node* AVLSearch::rightRotate(Node *y)
{
    Node *x = y->leftchild;
    Node *T2 = x->rightchild;
    x->rightchild= y;
    y->leftchild = T2;
    return x;
}
Node* AVLSearch::leftRotate(Node *x)
{
    Node *y = x->rightchild;
    Node *T2 = y->leftchild;
    y->leftchild = x;
    x->rightchild = T2;
    return y;
}

int getbalance(Node *B)
{
    if(B == NULL)
        return 0;
    return getHeight(B->leftchild) - getHeight(B-rightchild);
}

[TheIdeasMan]

It's keep saying getHeight is not declared but i already declared it in the BST and used friend class to access it

You need to access it through an Object, B ? If B is a BST ?

Also missing the > in getHeight(B->rightchild);

If your classes have a sufficient interface, they may not need so many friends :+)