AVL class

Make sure you study the BST/AVL discussion

No duplicates allowed in this data structure.

in order for you to implement an AVL class, you must add the following functions to your BST functions header file:

// ---------------- ROTATIONS --------------------------
template <typename T>
tree_node<T>* rotate_right(tree_node<T>* &root);
template <typename T>
tree_node<T>* rotate_left(tree_node<T>* &root);
template <typename T>
tree_node<T>* rotate(tree_node<T>* & root); //decide which rotate is needed based on balance factor

Now, you can implement an AVL class:

template <typename T>
class AVL{
public:
    AVL();
    AVL(const T *list, int size = -1);
    //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    AVL(const AVL<T> &copy_me);
    AVL<T> &operator=(const AVL<T> &rhs);
    ~AVL();
    //. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    bool insert(const T &insert_me);
    bool erase(const T &target);

    bool contains(const T &target) const;

    void clear();
    void clear_all();
    bool empty()const
    ;
    string pre_order() const;
    string in_order() const;
    string post_order() const;

    bool search(const T &target, tree_node<T> *&found_ptr) const;

    void output_inorder(ostream &outs);

    friend ostream& operator <<(ostream& outs, const AVL<T>& tree){
        tree_print(tree._root, 0, outs);
        return outs;
    }
    AVL<T> &operator+=(const AVL<T> &rhs);

private:

    tree_node<T>* _root;
};

Testing:

You will write individual functions that will test every aspect of this class. The insertion, the deletion, the copying and clearing and of course searching.

You will also write an interactive function that gives the user the following options:

[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: 

Here is a sample interaction:

[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 28
[28]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 77
    [77]
[28]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 42
    [77]
[42]
    [28]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 84
        [84]
    [77]
[42]
    [28]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 89
        [89]
    [84]
        [77]
[42]
    [28]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 13
        [89]
    [84]
        [77]
[42]
    [28]
        [13]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 54
        [89]
    [84]
        [77]
            [54]
[42]
    [28]
        [13]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 9
        [89]
    [84]
        [77]
            [54]
[42]
        [28]
    [13]
        [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 80
        [89]
    [84]
            [80]
        [77]
            [54]
[42]
        [28]
    [13]
        [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 78
            [89]
        [84]
    [80]
            [78]
        [77]
            [54]
[42]
        [28]
    [13]
        [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 66
            [89]
        [84]
    [80]
        [78]
[77]
            [66]
        [54]
    [42]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 97
            [97]
        [89]
            [84]
    [80]
        [78]
[77]
            [66]
        [54]
    [42]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 52
            [97]
        [89]
            [84]
    [80]
        [78]
[77]
            [66]
        [54]
            [52]
    [42]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 79
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
            [66]
        [54]
            [52]
    [42]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 75
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
                [75]
            [66]
        [54]
            [52]
    [42]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 32
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
                [75]
            [66]
        [54]
            [52]
    [42]
                [32]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 57
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
                [75]
            [66]
                [57]
        [54]
            [52]
    [42]
                [32]
            [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 37
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
                [75]
            [66]
                [57]
        [54]
            [52]
    [42]
                [37]
            [32]
                [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: r
-- Inserting 98
                [98]
            [97]
        [89]
            [84]
    [80]
            [79]
        [78]
[77]
                [75]
            [66]
                [57]
        [54]
            [52]
    [42]
                [37]
            [32]
                [28]
        [13]
            [9]

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: s 79
? item is found. |79|
=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: s -79
? item not found.

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: c

=========================
[R]andom  [I]nsert  [C]clear  [S]earch   e[X]it: x

=========================

================================
Press <RETURN> to close this window...

PCC316815:/ sassanbarkeshli$