C++

Forum

 
Assistance with insert function for AVL tree - C++

paul5345 (5)
I also posted this to stack overflow but received no assistance. I have an AVL tree project and one of the functions I need to implement is an insert function which adds set of values in the tree. The output which I am getting is incorrect, I will show after the code. All of the code except the insert, delete, and levelOrder functions (delete and levelOrder are not asked about here) were provided by my professor so I believe it can be assumed everything is coded correctly.

My insert function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
bool AVLTree::insert(string ss, string na){
    AVLNode* newPtr = new AVLNode(ss, na);
    updateHeight(newPtr);

    //Tree is empty, make the new Node the root of a new tree
    if(root == nullptr){
        root = newPtr;
        return true;
    }
    //Tree is not empty
    else{
        AVLNode* node = root;
        while(node != nullptr){
            //If the ssn is already in the tree
            if(node->ssn.compare(newPtr->ssn) == 0){
                return false;
            }
            else if(node->ssn.compare(newPtr->ssn) > 0){
                if(node->left == nullptr){
                    break;
                }
                node = node->left;
            }
            else{
                if(node->right == nullptr){
                    break;
                }
                node = node->right;
            }
        }

        if(newPtr->ssn.compare(node->ssn) < 0){
            node->left = newPtr;
        }
        else{
            node->right = newPtr;
        }
        updateHeight(node);
        balance(root);
        return true;
    }
}

And then the two functions used in there balance() and updateHeight() were provided by the professor, here they are:

Balance()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
AVLNode* AVLTree::balance(AVLNode* node){
    updateHeight(node);
    if (balanceFactor(node) == 2) {
        if (balanceFactor(node->left) < 0) {
            node->left = rotateLeft(node->left); // for left right case
        }

        AVLNode* temp = rotateRight(node);
        updateHeight(temp);
        return temp;
    }

    if (balanceFactor(node) == -2) {
        if (balanceFactor(node->right) > 0) {
            node->right = rotateRight(node->right);  // for right left case
        }
        AVLNode* temp2 = rotateLeft(node);
        updateHeight(temp2);
        return temp2;
    }
    return node;
}

updateHeight()
1
2
3
4
5
 
void AVLTree::updateHeight(AVLNode* node){
    int hl = height(node->left);
    int hr = height(node->right);
    node->height = (hl>hr ? hl : hr) + 1;
}

Main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
#include <iostream>
#include "AVLTree.h"
using namespace std;

int main(){
  AVLTree temp;
  temp.insert("05", "a");
  temp.insert("08", "b");
  temp.insert("09", "c");
  temp.insert("03", "d");
  temp.insert("06", "d");
  temp.insert("07", "d");
  temp.insert("02", "d");

  temp.print();

 }

My current output is
1
2
3
4
5
6
7
 
      8
     / \
    5   9
   / \
  3   6
 /     \
2       7

When I believe I should be getting
1
2
3
4
5
 
        6
     /     \
    3       8
   / \     / \
  2   5   7   9

Any help at all would be greatly appreciated, I apologize if I didn't include enough information, just let me know if you need more.
Last edited on
Topic archived. No new replies allowed.