Question

Please write a class "template" AVLTree in C++. The class must be placed in a single...

Please write a class "template" AVLTree in C++.

The class must be placed in a single header file called AVLTree.h

The class must contain the following public member functions:

-       necessary constructors for your implementation

-       destructor

-       isEmpty () – determines if the tree is empty - returns 1 if it is empty; 0 otherwise

-       height () – returns the height of the node or -1 if a nullptr

-       insert () – inserts data into the tree – must abide by AVL balancing properties

-       remove () – removes a specific item from the tree - must abide by AVL balancing properties

-       clear () – removes all nodes from the tree

-       findMin () – returns the smallest item in the tree

-       findMax () – returns the largest item in the tree

-       printInOrder () – prints the data in the nodes in increasing order

-       others?

This class must also contain at least the following private data member:

-       a pointer to the root AVLNode

Homework Answers

Answer #1

Here is the header file for all AVL Tree operations:

#include<iostream>

using namespace std;

class AVL
{
    struct node
    {
        int data;
        node* left;
        node* right;
        int height;
    };

    node* root;

    
public:
    BST()
    {
        root = NULL;
    }

    void insert(int x)
    {
        root = insert(x, root);
    }

    void remove(int x)
    {
        root = remove(x, root);
    }

    void display()
    {
        inorder(root);
        cout << endl;
    }
    
    void makeEmpty(node* t)
    {
        if(t == NULL)
            return;
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }

    node* insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->height = 0;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
        {
            t->left = insert(x, t->left);
            if(height(t->left) - height(t->right) == 2)
            {
                if(x < t->left->data)
                    t = singleRightRotate(t);
                else
                    t = doubleRightRotate(t);
            }
        }
        else if(x > t->data)
        {
            t->right = insert(x, t->right);
            if(height(t->right) - height(t->left) == 2)
            {
                if(x > t->right->data)
                    t = singleLeftRotate(t);
                else
                    t = doubleLeftRotate(t);
            }
        }

        t->height = max(height(t->left), height(t->right))+1;
        return t;
    }

    node* singleRightRotate(node* &t)
    {
        node* u = t->left;
        t->left = u->right;
        u->right = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(u->left), t->height)+1;
        return u;
    }

    node* singleLeftRotate(node* &t)
    {
        node* u = t->right;
        t->right = u->left;
        u->left = t;
        t->height = max(height(t->left), height(t->right))+1;
        u->height = max(height(t->right), t->height)+1 ;
        return u;
    }

    node* doubleLeftRotate(node* &t)
    {
        t->right = singleRightRotate(t->right);
        return singleLeftRotate(t);
    }

    node* doubleRightRotate(node* &t)
    {
        t->left = singleLeftRotate(t->left);
        return singleRightRotate(t);
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* remove(int x, node* t)
    {
        node* temp;

        // Element not found
        if(t == NULL)
            return NULL;

        // Searching for element
        else if(x < t->data)
            t->left = remove(x, t->left);
        else if(x > t->data)
            t->right = remove(x, t->right);

        // Element found
        // With 2 children
        else if(t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }
        // With one or zero child
        else
        {
            temp = t;
            if(t->left == NULL)
                t = t->right;
            else if(t->right == NULL)
                t = t->left;
            delete temp;
        }
        if(t == NULL)
            return t;

        t->height = max(height(t->left), height(t->right))+1;

        // If node is unbalanced
        // If left node is deleted, right case
        if(height(t->left) - height(t->right) == 2)
        {
            // right right case
            if(height(t->left->left) - height(t->left->right) == 1)
                return singleLeftRotate(t);
            // right left case
            else
                return doubleLeftRotate(t);
        }
        // If right node is deleted, left case
        else if(height(t->right) - height(t->left) == 2)
        {
            // left left case
            if(height(t->right->right) - height(t->right->left) == 1)
                return singleRightRotate(t);
            // left right case
            else
                return doubleRightRotate(t);
        }
        return t;
    }

    int height(node* t)
    {
        return (t == NULL ? -1 : t->height);
    }

    int getBalance(node* t)
    {
        if(t == NULL)
            return 0;
        else
            return height(t->left) - height(t->right);
    }

    void inorder(node* t)
    {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->data << " ";
        inorder(t->right);
    }

};
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
IntNode class I am providing the IntNode class you are required to use. Place this class...
IntNode class I am providing the IntNode class you are required to use. Place this class definition within the IntList.h file exactly as is. Make sure you place it above the definition of your IntList class. Notice that you will not code an implementation file for the IntNode class. The IntNode constructor has been defined inline (within the class declaration). Do not write any other functions for the IntNode class. Use as is. struct IntNode { int data; IntNode *next;...
The output only produces the values from the first linkedlist and not the second. Please fix...
The output only produces the values from the first linkedlist and not the second. Please fix the code to produce the desired objective. Thanks for your help! Objective: Interleave Example: Define the calling list as a set of ordered nodes, $L1 = {4, 2, 8 ,5, 8}$, and define the list that is passed as a parameter as a set of ordered nodes, $L2 = {5, 1, 8, 4, 5, 9}$. L1.interleave(L2) yields the set ${4, 5, 2, 1, 8,...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue...
You must alter the Queue class you created in L5 to make it a CIRCULAR Queue class . Call your class Queue. it must be a template class. public class Queue { } I have put a driver program in the module . It is called CircularQueue.java This driver program should then run with your Queue class (no modifications allowed to the driver program). Your Queue class should have at least the following methods: one or more constructors, enqueue, dequeue,...
ALL CODE MUST BE IN C++ Before you begin, you must write yourself a LinkedList class...
ALL CODE MUST BE IN C++ Before you begin, you must write yourself a LinkedList class and a Node class (please name your classes exactly ​as I did here). Please follow the below specifications for the two classes. Node.cpp ● This must be a generic class. ● Should contain a generic member variable that holds the nodes value. ● Should contain a next and prev Node* as denoted here. ● All member variables should be private. ● Use public and...
Data Structures using C++ Consider the classes QueueADT and ArrayQueueType: QueueADT: #ifndef QUEUEADT_H #define QUEUEADT_H template...
Data Structures using C++ Consider the classes QueueADT and ArrayQueueType: QueueADT: #ifndef QUEUEADT_H #define QUEUEADT_H template <class ItemType> class QueueADT { public:        // Action responsibilities        virtual void resetQueue() = 0;           // Reset the queue to an empty queue.           // Post: Queue is empty.        virtual void add(const ItemType& newItem) = 0;           // Function to add newItem to the queue.           // Pre: The queue exists and is not full.          ...
Data Structures using C++ Consider the following class #ifndef LINKEDQUEUETYPE_H #define LINKEDQUEUETYPE_H #include <iostream> #include <new>...
Data Structures using C++ Consider the following class #ifndef LINKEDQUEUETYPE_H #define LINKEDQUEUETYPE_H #include <iostream> #include <new>    #include <cstdlib> #include "QueueADT.h" using namespace std; // Definition of the node template <class ItemType> struct NodeType {        ItemType info;        NodeType<ItemType> *next; }; template <class ItemType> class LinkedQueueType: public QueueADT<ItemType> { public:        // Constructor        LinkedQueueType();           // Default constructor.           // Post: An empty queue has been created. queueFront = NULL;           //       queueBack = NULL;...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the...
import java.util.ArrayList; /* Rules:         1. Allow Tester to iterate through all nodes using the in-order traversal as the default.             This means, in Tester the following code should work for an instance of this class             called bst that is storing Student objects for the data:                 BinarySearchTree_Lab08<String> bst = new BinarySearchTree_Lab08<String>();                 bst.add("Man");       bst.add("Soda");   bst.add("Flag");                 bst.add("Home");   bst.add("Today");   bst.add("Jack");                ...
a) Please Select All That Apply: What are the possible applications of Priority Queue?      CPU Scheduling...
a) Please Select All That Apply: What are the possible applications of Priority Queue?      CPU Scheduling All queue applications where priority is involved.               kernel of NT for keep track of process information b) Running Time Analysis: Give the tightest possible big-O upper bound for the worst case running time for each operation listed below in terms of N. Assume no duplicate values and that you can implement the operation as a member function of the class – with access to...
IntList Lab Specifications You are required to come up with a single header file (IntList.h) that...
IntList Lab Specifications You are required to come up with a single header file (IntList.h) that declares and implements the IntNode class (just copy it exactly as it is below) as well as declares the IntList Class interface only. You are also required to come up with a separate implementation file (IntList.cpp) that implements the member functions of the IntList class. While developing your IntList class you must write your own test harness (within a file named main.cpp). Never implement...