C++

Forum

 
 
AVL Tree this-> was a null ptr exception

Jorge626 (50)
I need help with my project for data structures. I am trying to construct an AVL Tree, I keep getting an exception thrown that states this -> was a null pointer. I know that the line called before I get the error is in my SearchTree.h file, on line 243 in my restructure function and where the error takes place is in my BinaryTree.h file on line 34 of my parent() function, however I can't figure out how to prevent it. Here is a github link to my project.

https://github.com/Jorge626/CSCI-220-AVL-Tree-Project

I know it may be a lot to go over, but any help would be greatly appreciated!
Last edited on
salem c (3685)
So, have you actually run the code in the debugger to try to trace where the problem is?

You start with the smallest tree which generates the problem.
Then use the debugger to set breakpoints and then single step the code one line at a time. At each step, make sure what it actually does matches your expectation.

lastchance (6980)
@Jorge626,
I can't even get your code to compile.

Is there no way that you could a post a smaller, preferably single-file, version of the minimal content that produces your errors on this forum?


A lot of the compilation errors are simply down to a failure to
#include <string>

However, there are some that I simply can't fathom.

General call - anyone know what the following is likely to accrue from? Many of the other compilation errors seem to be knock-on errors from it.
In file included from Source.cpp:2:
AVLTree.h:14:26: error: expected nested-name-specifier
         typedef typename SearchTree< Entry<std::string, std::string, std::string> > ST;


Hmmm. Removing "typename" fixes that. Not sure what is was there for in the first place.



OK ... now to find workarounds in RunTimeException.h, 'cos they stop it compiling as well....
Last edited on
lastchance (6980)
OK, did enough workarounds to get it to compile.

First, does a normal tree work ...

Comment out the rebalancing by commenting it out in SearchTree.h (function insert):
1
2
3
4
5
6
7
 
        Iterator insert(const C& c, const P& p, const N& n)
        {
                TPos tempInsert = inserter(c, p, n);
                setHeight(tempInsert);
//              rebalance(tempInsert);
                return Iterator(tempInsert);
        }


Produces
           Menu
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Search for a record
2) Insert a record
3) Delete a record
4) List all records
5) Exit
Please enter any choice: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
6001 3648 "Alameda, CA"
6019 1242 "Fresno, CA"
6037 22851 "Los Angeles, CA"
6047 341 "Merced, CA"
6055 225 "Napa, CA"
6059 6214 "Orange, CA"
6065 1784 "Riverside, CA"
6067 1809 "Sacramento, CA"
6071 1920 "San Bernardino, CA"
6073 5351 "San Diego, CA"
6075 2039 "San Francisco, CA"
6083 721 "Santa Barbara, CA"
6097 655 "Sonoma, CA"
6111 1130 "Ventura, CA"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
           Menu
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1) Search for a record
2) Insert a record
3) Delete a record
4) List all records
5) Exit
Please enter any choice: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~


So, now you need to follow through your obscure rebalance procedure
Allowing the call to rebalance() causes the program to crash.


If anyone else can fathom it out, here's the relevant bit of code from file
SearchTree.h.

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
        void rebalance(const TPos& v)
        {
                TPos z = v;
                while (!(z == root())) {                        // rebalance up to root
                        z = z.parent();
                        setHeight(z);                                   // compute new height
                        if (!isBalanced(z)) {                           // restructuring needed
                                TPos x = tallGrandchild(z);
                                z = restructure(x);                             // trinode restructure
                                setHeight(z.left());                            // update heights
                                setHeight(z.right());
                                setHeight(z);
                        }
                }
        }

        TPos tallGrandchild(const TPos& z) const {
                TPos zl = z.left();
                TPos zr = z.right();
                if (height(zl) >= height(zr))                   // left child taller
                        if (height(zl.left()) >= height(zl.right()))
                                return zl.left();
                        else
                                return zl.right();
                else                                            // right child taller
                        if (height(zr.right()) >= height(zr.left()))
                                return zr.right();
                        else
                                return zr.left();
        }

        TPos restructure(const TPos x)
        {
                TPos y = x.parent();
                TPos z = y.parent();
                TPos a, b, c, T0, T1, T2, T3;

                if (z.left() == y && y.left() == x)
                {
                        a = x;
                        b = y;
                        c = z;
                        T0 = a.left();
                        T1 = a.right();
                        T2 = b.right();
                        T3 = c.right();
                }

                else if (z.right() == y && y.right() == x)
                {
                        a = z;
                        b = y;
                        c = x;
                        T0 = a.left();
                        T1 = b.left();
                        T2 = c.left();
                        T3 = c.right();
                }

                else if (z.left() == y && y.right() == x)
                {
                        a = x;
                        b = y;
                        c = z;
                        T0 = a.left();
                        T1 = b.left();
                        T2 = b.right();
                        T3 = c.right();
                }

                else if (z.right() == y && y.left() == x)
                {
                        a = x;
                        b = y;
                        c = z;
                        T0 = z.left();
                        T1 = b.left();
                        T2 = b.right();
                        T3 = c.right();
                }

                if (z.isRoot())
                        b = root();

                b.left() = a;
                b.right() = c;
                a.parent() = b;
                c.parent() = b;
                a.left() = T0;
                a.right() = T1;
                T0.parent() = a;
                T1.parent() = a;
                c.left() = T2;
                c.right() = T3;

                return b;
        }


If you are working from some reference, please provide a link to it.
Last edited on
lastchance (6980)
I would guess that the end of the restructure routine should look like the following.

You DON'T check that T0 and T1 are not null before you TRY TO ASSIGN their parents. I think you probably need to do something similar with T2 and T3 as well.

1
2
3
4
5
6
7
8
9
10
11
12
 
               b.left() = a;
                b.right() = c;
                a.parent() = b;
                c.parent() = b;
                a.left() = T0;
                a.right() = T1;
                if ( T0 != nullptr ) T0.parent() = a;    // DO THE CHECK
                if ( T1 != nullptr ) T1.parent() = a;
                c.left() = T2;
                c.right() = T3;
                if ( T2 != nullptr ) T2.parent() = c;        // added line
                if ( T3 != nullptr ) T3.parent() = c;        // ditto




Also, I think that your two cases following
else if (z.left() == y && y.right() == x)
and
else if (z.right() == y && y.left() == x)
are both wrong. You are aiming to return the (ordered) middle value, which in both these alternate-direction cases would be x. Surely b should be set equal to x in these cases?

DRAW SOME CAREFUL DIAGRAMS.


There is also something wrong with your height-setting routines. Try just simply printing all the nodes and their heights with any rebalancing commented out.
Last edited on
Jorge626 (50)
Sorry for all the compilation errors, the majority of it came from our textbook. After not being able to trace and understand most of the code, I rewrote it so that it could make a bit more sense for myself. (Which is why there is probably a few errors, but the majority of it is copied directly from the textbook)

@salem c Yeah I tried to retrace it to the best of my ability, after I posted this and some further debugging I fixed the first problem I was having, but then the same problem came up further down the compilation

@lastchance Thank you for trying your best to help out! It's really greatly appreciated. As for why the typename was there, it was because I did not want to have to type it out over and over again in that file. Mostly the iterator because I have some functions that return an iterator and I did not want to have to copy and paste that over and over again. It's mostly just so that my code doesn't look so cluttered. Also, I did not know where my problem may have been, that is why I just provided the whole project. Apologies for making it so inconvenient, I will try and put code I feel may be relevant next time.

I worked around the part about checking if it was a nullpointer by adding this to the start of the restructure function

1
2
 
if (x.isExternal())
		binaryTree.expandExternal(x);


Since x would have been the grandchild, this problem would arise when it was the external node. I'm not sure if this is a good fix, but it worked for a while. After being able to go further down the compilation, the same exception would be thrown in the height function. I found that the height and setHeight functions wasn't doing what I was expecting it do, which was access the height and setHeight functions in my Entry.h file. I've been trying to find a way to do this but I can't seem to figure it out. In the textbook, it makes the tree a friend class, but when I do that I get an unexpected token(s) error for some reason.

And you're right, those two cases were wrong, thank you for pointing that out! I fixed them

Update
I've updated my code so that it will actually compile ( at least on visual studios ). I got past the second insertion, (which was when I would get the error ) and now I get the error on the third insertion after it attempts to restructure. I worked around the height problem by adding an int to keep track of height onto my node directly in BinaryTree.h , this seems to have fixed the problem of not being able to access an integer for my height. I got past my first two insertions, but now I get the error in the same height ( ) function in SearchTree.h . I get the null pointer error on my isExternal() function this time in BinaryTree.h ( Also, on a side note, I am not even sure if I am utilizing my Entry.h file at this point )

Here is some code I think would be relevant to fixing the problem,

in SearchTree.h 
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
 
int height(const TPos& currentPosition) const
	{
		return (currentPosition.isExternal() ? 0 : currentPosition.height());
	}

	void setHeight(TPos currentPosition)
	{
		int hl = height(currentPosition.left());
		int hr = height(currentPosition.right());
		currentPosition.setHeight(1 + std::max(hl, hr));
	}

	bool isBalanced(const TPos& v) const
	{
		int bal = height(v.left()) - height(v.right());
		return ((-1 <= bal) && (bal <= 1));
	}

	void rebalance(const TPos& v)
	{
		TPos z = v;
		while (!(z == root())) {			// rebalance up to root
			z = z.parent();
			setHeight(z);					// compute new height
			if (!isBalanced(z)) {				// restructuring needed
				TPos x = tallGrandchild(z);
				z = restructure(x);				// trinode restructure
				setHeight(z.left());				// update heights
				setHeight(z.right());
				setHeight(z);
			}
		}
	}

	TPos tallGrandchild(const TPos& z) const {
		TPos zl = z.left();
		TPos zr = z.right();
		if (height(zl) >= height(zr))			// left child taller
			if (height(zl.left()) >= height(zl.right()))
				return zl.left();
			else
				return zl.right();
		else 						// right child taller
			if (height(zr.right()) >= height(zr.left()))
				return zr.right();
			else
				return zr.left();
	}

	TPos restructure(const TPos x)
	{
		if (x.isExternal())
			binaryTree.expandExternal(x);

		TPos y = x.parent();
		TPos z = y.parent();
		TPos a, b, c, T0, T1, T2, T3;

		if (z.left() == y && y.left() == x)
		{
			a = x;
			b = y;
			c = z;
			T0 = a.left();
			T1 = a.right();
			T2 = b.right();
			T3 = c.right();
		}

		else if (z.right() == y && y.right() == x)
		{
			a = z;
			b = y;
			c = x;
			T0 = a.left();
			T1 = b.left();
			T2 = c.left();
			T3 = c.right();
		}

		else if (z.left() == y && y.right() == x)
		{
			a = y;
			b = x;
			c = z;
			T0 = a.left();
			T1 = a.right();
			T2 = c.left();
			T3 = c.right();
		}

		else if (z.right() == y && y.left() == x)
		{
			a = z;
			b = x;
			c = y;
			T0 = a.left();
			T1 = a.right();
			T2 = c.left();
			T3 = c.right();
		}

		if (z.isRoot())
			b = root();

		b.left() = a;
		b.right() = c;
		a.parent() = b;
		c.parent() = b;
		a.left() = T0;
		a.right() = T1;
		T0.parent() = a;
		T1.parent() = a;
		c.left() = T2;
		c.right() = T3;
		T2.parent() = c;
		T3.parent() = c;

		return b;
	}


in BinaryTree.h 
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
43
44
45
46
47
48
49
50
51
 
struct Node {
		Elem element;
		Node* parent;
		Node* left;
		Node* right;
		int ht;
		Node() : element(), parent(NULL), left(NULL), right(NULL), ht(0) { }
	};

public:
	class Position {
	private:
		Node* position;
	public:
		Position(Node* _pos = NULL) : position(_pos) { }

		Elem& operator*() { return position->element; }

		Position left() const { return Position(position->left); }

		Position right() const { return Position(position->right); }

		Position parent() const { return Position(position->parent); }

		bool isRoot() { return position->parent == NULL; }

		bool isExternal() const { return position->left == NULL && position->right == NULL; }

		bool isInternal() const { return !isExternal(); }

		bool operator==(const Position& comparedPosition) const { return position == comparedPosition.position; }

		bool operator != (const Position comparedPosition) const { return !(*this == comparedPosition); }

		int height() const { return position->ht; }			// get height

		void setHeight(int h) { position->ht = h; }			// set height

		friend class BinaryTree<Elem>;

	};

void expandExternal(const Position& currentPosition)
	{
		Node* expandedNode = currentPosition.position;
		expandedNode->left = new Node;
		expandedNode->left->parent = expandedNode;
		expandedNode->right = new Node;
		expandedNode->right->parent = expandedNode;
		totalNodes += 2;
	}

Last edited on
lastchance (6980)
@Jorge, I would focus on fixing your height-setting routines first. Comment out any restructuring and get your code to work out, then print out, the height of all nodes. Until that is sorted out you won't be able to do any rebalancing.

Just seen your edit: your latest restructuring routine still doesn't check that T0, T1, T2, T3 are not null before it tries to assign their parents. Also, they have NOT been set correctly in your alternating-direction cases: you really need to draw some diagrams for each of those cases.

Make sure that your height-setting routines work before you try to rebalance. I can't work out what your isExternal routine is really trying to do. If I want to check that I'm at "the end of the line" I just check for NULL.
Last edited on
Jorge626 (50)
@lastchance I think I've got the height functions working properly now, but now I'm running into a problem of an infinite loop and my program freezes. I am pretty sure that this is due to the fact that z is the root node. I am confident that this is the problem because it is during the 3rd insert, and when I check the locals before the restructure code finishes, the correct nodes are on the left and right, however, z would remain to be the parent node after it returns to the setHeight functions in my rebalance function. I tried setting b to be the root node with this code:

1
2
3
4
5
6
7
8
9
10
11
12
 
if (z.isRoot())
			root() = b;

		else if (z.parent().left() == z)
		{
			z.parent().left() = b;
		}
		else if (z.parent().right() == z)
		{
			z.parent().right() = b;
		}


after my cases for determining which is a,b,c and T's, but it doesn't seem to work. Any suggestions?
lastchance (6980)
@Jorge626,
Your assignment of nodes in your last code is still not right. The last two cases should be
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
                else if (z.left() == y && y.right() == x)
                {
                        a = y;
                        b = x;
                        c = z;
                        T0 = a.left();
                        T1 = b.left();         // <=====
                        T2 = b.right();        // <=====
                        T3 = c.right();
                }

                else if (z.right() == y && y.left() == x)
                {
                        a = z;
                        b = x;
                        c = y;
                        T0 = a.left();
                        T1 = b.left();         // <=====
                        T2 = b.right();        // <=====
                        T3 = c.right();
                }


In that code you are still not checking that T0, T1, T2, T3 are not null before attempting to set their parents. You need something like
1
2
3
4
5
6
7
8
9
10
11
12
 
                b.left() = a;
                b.right() = c;
                a.parent() = b;
                c.parent() = b;
                a.left() = T0;
                a.right() = T1;
                if ( T0 != NULL ) T0.parent() = a;
                if ( T1 != NULL ) T1.parent() = a;
                c.left() = T2;
                c.right() = T3;
                if ( T2 != NULL ) T2.parent() = c;
                if ( T3 != NULL ) T3.parent() = c;


When I last ran your code, it was producing nonsense for the heights of some nodes. I don't know whether that is fixed, because your code keeps changing. Please try:
- Turn off the call to rebalance on insert, so that you can at least produce a tree, even if unbalanced;
- With that (unbalanced) tree, amend your printing routine to print each of the node's data AND its height. Are these heights correct? Don't even think about balancing until they are.


When you have made the suggested amendments and verified the correct working of the height routines then - and only then - please post (below) an updated version of SearchTree.h

Last edited on
Jorge626 (50)
I think i've got it to work, thank you for all your help!
Topic archived. No new replies allowed.