I\'m having trouble implementing a delete function for an AVL tree. I would like

Question

I'm having trouble implementing a delete function for an AVL tree. I would like to use the immediate successor approach as opposed to immediate predecessor. Can you help me out? Here is my code:

template <class Record>
class AVL_tree: public Search_tree<Record> {
public:
Error_code insert(const Record &new_data);
Error_code remove(const Record &old_data);
protected:
// Auxiliary functions
Error_code avl_insert(Binary_node<Record>* &sub_root, const Record &new_data, bool &taller);
Error_code avl_delete(Binary_node<Record>* &sub_root, const Record &old_data, bool &shorter);
//void avl_remove_root(Binary_node<Record>* &sub_root, bool &shorter, Record &predecessor, Binary_node<Record>* &to_delete);
void left_balance(Binary_node<Record>* &sub_root);
void right_balance(Binary_node<Record>* &sub_root);
void rotate_left(Binary_node<Record>* &sub_root);
void rotate_right(Binary_node<Record>* &sub_root);
};

template <class Record>
Error_code AVL_tree<Record>::insert(const Record &new_data)
/*
Post: If the key of new_data is already in the AVL_tree, a code
of duplicate_error is returned.
Otherwise, a code of success is returned and the Record new_data
is inserted into the tree in such a way that the properties of
an AVL tree are preserved.
Uses: avl_insert.
*/
{
bool taller;
//return avl_insert(this->root, new_data, taller);
return avl_insert(this->root, new_data, taller);
}

template <class Record>
Error_code AVL_tree<Record>::remove(const Record &old_data)
/*
Post: If a Record with a key matching that of target belongs to the
AVL_tree, a code of success is returned, and the corresponding node
is removed from the tree. Otherwise, a code of not_present is returned.
Uses: Function search_and_destroy
*/
{
bool shorter;
return avl_delete(this->root, old_data, shorter);
}

template <class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record>* &sub_root,
const Record &new_data, bool &taller)
/*
Pre: sub_root is either NULL or points to a subtree of the AVL_tree
Post: If the key of new_data is already in the subtree, a
code of duplicate_error is returned.
Otherwise, a code of success is returned and the Record new_data
is inserted into the subtree in such a way that the
properties of an AVL tree have been preserved.
If the subtree is increased in height, the parameter taller is set to
true; otherwise it is set to false.
Uses: Methods of struct AVL_node; functions avl_insert
recursively, left_balance, and right_balance.
*/
{
Error_code result = success;
if (sub_root == NULL) {
sub_root = new AVL_node<Record>(new_data);
taller = true; //taller is true for every new node creation
}
else if (new_data == sub_root->data) {
result = duplicate_error;
taller = false;
}
//insert to LST
else if (new_data < sub_root->data) {   
result = avl_insert(sub_root->left, new_data, taller);
if (taller == true)
       switch (sub_root->get_balance()) {
case left_higher: //lh before insertion, now unbalanced
left_balance(sub_root);
taller = false;   
break;
       case equal_height:
sub_root->set_balance(left_higher);
break;
case right_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
}
}
//insert to RST
else {   
result = avl_insert(sub_root->right, new_data, taller);
if (taller == true)
switch (sub_root->get_balance()) {
case left_higher:
sub_root->set_balance(equal_height);
taller = false;
break;
case equal_height:
sub_root->set_balance(right_higher);
break;
case right_higher:
right_balance(sub_root);
taller = false;
break;
}
}
return result;
}

template <class Record>
Error_code AVL_tree<Record>::avl_delete(Binary_node<Record>* &sub_root,
const Record &old_data, bool &shorter)
{
Error_code result = success;
Binary_node<Record> *temp;
if (sub_root == NULL) {
result = not_present;
shorter = false;
}
else if (old_data == sub_root->data) {
Binary_node<Record> *to_delete = sub_root;
shorter = true;
if (sub_root->right == NULL) {
sub_root = sub_root->left;
}
else if (sub_root->left == NULL) {
sub_root = sub_root->right;
}
else {
to_delete = sub_root->right;
Binary_node<Record> *parent = sub_root;
while (to_delete->left != NULL) {
parent = to_delete;
to_delete = to_delete->left;
}
sub_root->data = to_delete->data;
if (parent == sub_root) {
sub_root->right = to_delete->right;
}
else {
parent->left = to_delete->right;
}
}
delete to_delete;
}
else if (old_data < sub_root->data) {
result = avl_delete(sub_root->left, old_data, shorter);
if (shorter == true)
switch (sub_root->get_balance()) {
case left_higher:
sub_root->set_balance(equal_height);
shorter = true;
break;
case equal_height:
sub_root->set_balance(right_higher);
shorter = false;
break;
case right_higher:
temp = sub_root->right;
if (temp->get_balance() == equal_height) {
shorter = true;
}
else {
shorter = false;
}
right_balance(sub_root);
break;
}
}
else {
result = avl_delete(sub_root->right, old_data, shorter);
if (shorter == true)
switch (sub_root->get_balance()) {
case left_higher:
temp = sub_root->left;
if (temp->get_balance() == equal_height) {
shorter = true;
}
else {
shorter = false;
}
left_balance(sub_root);
break;
case equal_height:
sub_root->set_balance(left_higher);
shorter = false;
break;
case right_higher:
sub_root->set_balance(equal_height);
shorter = true;
break;
}
}
return result;
}

template <class Record>
void AVL_tree<Record>::left_balance(Binary_node<Record>* &sub_root)
/*
Pre: sub_root points to a subtree of an AVL_tree that
is doubly unbalanced on the left.
Post: The AVL properties have been restored to the subtree.
Uses:
  
*/
{
}

template <class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of an AVL_tree that
is unbalanced on the right.
Post: The AVL properties have been restored to the subtree.
Uses: Methods of struct AVL_node;
functions rotate_right and rotate_left.
*/
{
Binary_node<Record>* &right_tree = sub_root->right;
// case right_higher: sigle left rotation
// O ub --> subroot
//
// O rh --> right_tree
//
// O
switch (right_tree->get_balance()) {
case right_higher: // single left rotation
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
rotate_left(sub_root); //pointer adjustment
break;
case equal_height: // impossible case
cout << "WARNING: If you see this in an insertion, program error is detected in right_balance" << endl;
right_tree->set_balance(left_higher);
rotate_left(sub_root);
break;
// case left_higher: double rotation left
// O ub --> sub_root
//
// O lh --> right_tree
// /
// O three cases --> sub_tree
case left_higher:   
Binary_node<Record> *sub_tree = right_tree->left;
   //set balance of sub_root and right_tree assuming rotation is done
switch (sub_tree->get_balance()) {
case equal_height:
sub_root->set_balance(equal_height);
right_tree->set_balance(equal_height);
break;
case left_higher:
sub_root->set_balance(equal_height);
right_tree->set_balance(right_higher);
break;
case right_higher:
sub_root->set_balance(left_higher);
right_tree->set_balance(equal_height);
break;
}
   //set balance of sub_tree after rotation
sub_tree->set_balance(equal_height);
   //perform actual rotation
rotate_right(right_tree);
rotate_left(sub_root);
break;
}
}

//adjustment of pointers
template <class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of the AVL_tree.
This subtree has a nonempty right subtree.
Post: sub_root is reset to point to its former right child, and the former
sub_root node is the left child of the new sub_root node.
*/
{
if (sub_root == NULL || sub_root->right == NULL) // impossible cases
cout << "WARNING: program error detected in rotate_left" << endl;
else {
Binary_node<Record> *right_tree = sub_root->right;
sub_root->right = right_tree->left;
right_tree->left = sub_root;
sub_root = right_tree;
}
}

template <class Record>
void AVL_tree<Record>::rotate_right(Binary_node<Record> *&sub_root)
/*
Pre: sub_root points to a subtree of the AVL_tree.
This subtree has a nonempty left subtree.
Post:
*/
{
}

Explanation / Answer

My Code:

/* AVL node */
template <class T>
class AVLnode {
public:
    T key;
    int balance;
    AVLnode *left, *right, *parent;

    AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
                        left(NULL), right(NULL) {}

    ~AVLnode() {
        delete left;
        delete right;
    }
};

/* AVL tree */
template <class T>
class AVLtree {
public:
    AVLtree(void);
    ~AVLtree(void);
    bool insert(T key);
    void deleteKey(const T key);
    void printBalance();

private:
    AVLnode<T> *root;

    AVLnode<T>* rotateLeft          ( AVLnode<T> *a );
    AVLnode<T>* rotateRight         ( AVLnode<T> *a );
    AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n );
    AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n );
    void rebalance                  ( AVLnode<T> *n );
    int height                      ( AVLnode<T> *n );
    void setBalance                 ( AVLnode<T> *n );
    void printBalance               ( AVLnode<T> *n );
    void clearNode                  ( AVLnode<T> *n );
};

/* AVL class definition */
template <class T>
void AVLtree<T>::rebalance(AVLnode<T> *n) {
    setBalance(n);

    if (n->balance == -2) {
        if (height(n->left->left) >= height(n->left->right))
            n = rotateRight(n);
        else
            n = rotateLeftThenRight(n);
    }
    else if (n->balance == 2) {
        if (height(n->right->right) >= height(n->right->left))
            n = rotateLeft(n);
        else
            n = rotateRightThenLeft(n);
    }

    if (n->parent != NULL) {
        rebalance(n->parent);
    }
    else {
        root = n;
    }
}

template <class T>
AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) {
    AVLnode<T> *b = a->right;
    b->parent = a->parent;
    a->right = b->left;

    if (a->right != NULL)
        a->right->parent = a;

    b->left = a;
   a->parent = b;

    if (b->parent != NULL) {
        if (b->parent->right == a) {
            b->parent->right = b;
        }
        else {
            b->parent->left = b;
        }
    }

    setBalance(a);
    setBalance(b);
    return b;
}

template <class T>
AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) {
    AVLnode<T> *b = a->left;
    b->parent = a->parent;
    a->left = b->right;

    if (a->left != NULL)
        a->left->parent = a;

    b->right = a;
    a->parent = b;

    if (b->parent != NULL) {
        if (b->parent->right == a) {
            b->parent->right = b;
        }
        else {
            b->parent->left = b;
        }
    }

    setBalance(a);
    setBalance(b);
    return b;
}

template <class T>
AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) {
    n->left = rotateLeft(n->left);
    return rotateRight(n);
}

template <class T>
AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) {
    n->right = rotateRight(n->right);
    return rotateLeft(n);
}

template <class T>
int AVLtree<T>::height(AVLnode<T> *n) {
    if (n == NULL)
        return -1;
    return 1 + std::max(height(n->left), height(n->right));
}

template <class T>
void AVLtree<T>::setBalance(AVLnode<T> *n) {
    n->balance = height(n->right) - height(n->left);
}

template <class T>
void AVLtree<T>::printBalance(AVLnode<T> *n) {
    if (n != NULL) {
        printBalance(n->left);
        std::cout << n->balance << " ";
        printBalance(n->right);
    }
}

template <class T>
AVLtree<T>::AVLtree(void) : root(NULL) {}

template <class T>
AVLtree<T>::~AVLtree(void) {
    delete root;
}

template <class T>
bool AVLtree<T>::insert(T key) {
    if (root == NULL) {
        root = new AVLnode<T>(key, NULL);
    }
    else {
        AVLnode<T>
            *n = root,
            *parent;

        while (true) {
            if (n->key == key)
                return false;

            parent = n;

            bool goLeft = n->key > key;
            n = goLeft ? n->left : n->right;

            if (n == NULL) {
                if (goLeft) {
                    parent->left = new AVLnode<T>(key, parent);
                }
                else {
                    parent->right = new AVLnode<T>(key, parent);
                }

                rebalance(parent);
                break;
            }
        }
    }

    return true;
}

template <class T>
void AVLtree<T>::deleteKey(const T delKey) {
    if (root == NULL)
        return;

    AVLnode<T>
        *n       = root,
        *parent = root,
        *delNode = NULL,
        *child   = root;

    while (child != NULL) {
        parent = n;
        n = child;
        child = delKey >= n->key ? n->right : n->left;
        if (delKey == n->key)
            delNode = n;
    }
if (delNode != NULL) {
        delNode->key = n->key;

        child = n->left != NULL ? n->left : n->right;

        if (root->key == delKey) {
            root = child;
        }
        else {

  if (parent->left == n) {
                parent->left = child;
            }
            else {
                parent->right = child;
            }
   rebalance(parent);
        }
    }
}
template <class T>
void AVLtree<T>::printBalance() {
    printBalance(root);
    std::cout << std::endl;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.