C++

Forum

 
Inserting in a 2-3-4 tree

herooftime1000 (14)
I'm aware that the code here may be a little messy, but I can't seem to figure out the process of adding and splitting in the tree. No matter what I do, I always seem to lose or repeat numbers for some reason... Here's my .cpp of the tree.

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
 
template<class ItemType>
void TwoToFourTree<ItemType>::inOrder(QuadNode<ItemType>* treePtr) {
	if (treePtr->isLeaf()) {
		if (treePtr->getSmallItem() != NULL) {
			std::cout << treePtr->getSmallItem() << " ";
		}
		if (treePtr->getMidItem() != NULL) {
			std::cout << treePtr->getMidItem() << " ";
		}
		if (treePtr->getLargeItem() != NULL) {
			std::cout << treePtr->getLargeItem() << " ";
		}
	}

	else if (treePtr->isFourNode()) {
		inOrder(treePtr->getLeftChildPtr());
		if (treePtr->getSmallItem() != NULL) {
			std::cout << treePtr->getSmallItem() << " ";
		}
		inOrder(treePtr->getLeftMidChildPtr());
		if (treePtr->getMidItem() != NULL) {
			std::cout << treePtr->getMidItem() << " ";
		}
		inOrder(treePtr->getRightMidChildPtr());
		if (treePtr->getLargeItem() != NULL) {
			std::cout << treePtr->getLargeItem() << " ";
		}
		inOrder(treePtr->getRightChildPtr());
	}
	else if (treePtr->isThreeNode()) {
		inOrder(treePtr->getLeftChildPtr());
		if (treePtr->getSmallItem() != NULL) {
			std::cout << treePtr->getSmallItem() << " ";
		}
		inOrder(treePtr->getLeftMidChildPtr());
		if (treePtr->getLargeItem() != NULL) {
			std::cout << treePtr->getLargeItem() << " ";
		}
		inOrder(treePtr->getRightChildPtr());
	}
	else if (treePtr->isTwoNode()) {
		inOrder(treePtr->getLeftChildPtr());
		if (treePtr->getSmallItem() != NULL) {
			std::cout << treePtr->getSmallItem() << " ";
		}
		inOrder(treePtr->getRightChildPtr());
	}
}

template<class ItemType>
void TwoToFourTree<ItemType>::insertItem(QuadNode<ItemType>* treePtr, ItemType newItem) {

	
	if (newItem == findItem(treePtr, newItem)) {
		return;
	}

	QuadNode<ItemType>* setLeaf = nullptr;
	
	while (setLeaf == nullptr) {
	  setLeaf = locateLeaf(treePtr, newItem);
	}


	addToNode(setLeaf, newItem);


}


template<class ItemType>
QuadNode<ItemType>* TwoToFourTree<ItemType>::locateLeaf(QuadNode<ItemType>* treePtr, ItemType newItem)
{
	if (treePtr->isFull()) {
		split(treePtr);
		return nullptr;
	}

	if (treePtr->isLeaf()) {
		return treePtr;
	}

	else if (treePtr->isFourNode()) {
		if (newItem < treePtr->getSmallItem()) {
			return locateLeaf(treePtr->getLeftChildPtr(), newItem);
		}

		else if ((newItem > treePtr->getSmallItem()) && (newItem < treePtr->getMidItem())) {
			return locateLeaf(treePtr->getLeftMidChildPtr(), newItem);
		}

		else if ((newItem > treePtr->getMidItem()) && (newItem < treePtr->getLargeItem())) {
			return locateLeaf(treePtr->getRightMidChildPtr(), newItem);
		}

		else if (newItem > treePtr->getLargeItem()) {
			return locateLeaf(treePtr->getRightChildPtr(), newItem);
		}
	}

	else if (treePtr->isThreeNode()) {
		if (newItem < treePtr->getSmallItem()) {
			return locateLeaf(treePtr->getLeftChildPtr(), newItem);
		}

		else if (newItem < treePtr->getLargeItem()) {
			return locateLeaf(treePtr->getLeftMidChildPtr(), newItem);
		}
		
		else {
			return locateLeaf(treePtr->getRightChildPtr(), newItem);
		}
	}

	else if (treePtr->isTwoNode()) {
		if (newItem < treePtr->getSmallItem()) {
			return locateLeaf(treePtr->getLeftChildPtr(), newItem);
		}

		else {
			return locateLeaf(treePtr->getRightChildPtr(), newItem);
		}
	}
}

template<class ItemType>
void TwoToFourTree<ItemType>::split(QuadNode<ItemType>* treePtr) {

	QuadNode<ItemType>* parentPtr = new QuadNode<ItemType>();

	if (treePtr->getParentPtr() != nullptr) {
		parentPtr = treePtr->getParentPtr();
		std::cout << "Got Parent" << std::endl;
		
	}

	else {
		parentPtr = treePtr;
		std::cout << "Root" << std::endl;
	}

	QuadNode<ItemType>* n1 = new QuadNode<ItemType>();
	n1->setSmallItem(treePtr->getSmallItem());
	if (treePtr->getLeftChildPtr() != nullptr) {
		n1->setLeftChildPtr(treePtr->getLeftChildPtr());
	}
	if (treePtr->getLeftMidChildPtr() != nullptr) {
		n1->setRightChildPtr(treePtr->getLeftMidChildPtr());
	}
	n1->setParentPtr(parentPtr);

	QuadNode<ItemType>* n2 = new QuadNode<ItemType>();
	n2->setSmallItem(treePtr->getLargeItem());
	if (treePtr->getRightMidChildPtr() != nullptr) {
		n2->setLeftChildPtr(treePtr->getRightMidChildPtr());
	}
	if (treePtr->getRightChildPtr() != nullptr) {
		n2->setRightChildPtr(treePtr->getRightChildPtr());
	}
	n2->setParentPtr(parentPtr);

	ItemType temp = treePtr->getMidItem();

	if (parentPtr->isFourNode()) {

		parentPtr->setLeftChildPtr(n1);
		parentPtr->setRightChildPtr(n2);
		parentPtr->setLargeItem(NULL);
		parentPtr->setMidItem(NULL);
		parentPtr->setSmallItem(temp);
	}

	else if (parentPtr->isThreeNode()) {
		if (parentPtr->getLeftChildPtr() == treePtr){

			parentPtr->setLeftChildPtr(n1);
			parentPtr->setLeftMidChildPtr(n2);
			addToNode(parentPtr, temp);

		}

		else if (parentPtr->getLeftMidChildPtr() == treePtr) {

			parentPtr->setLeftMidChildPtr(n1);
			parentPtr->setRightMidChildPtr(n2);
			addToNode(parentPtr, temp);

		}

		else if (parentPtr->getRightChildPtr() == treePtr) {

			parentPtr->setRightMidChildPtr(n1);
			parentPtr->setRightChildPtr(n2);
			addToNode(parentPtr, temp);

		}
	}
	
	else if (parentPtr->isTwoNode()) {
		std::cout << "TwoNode Parent" << std::endl;
		if (parentPtr->getLeftChildPtr() == treePtr) {

			parentPtr->setLeftChildPtr(n1);
			parentPtr->setLeftMidChildPtr(n2);
			parentPtr->setLargeItem(parentPtr->getSmallItem());
			parentPtr->setSmallItem(temp);

		}

		else if (parentPtr->getRightChildPtr() == treePtr) {

			parentPtr->setLeftMidChildPtr(n1);
			parentPtr->setRightChildPtr(n2);
			parentPtr->setLargeItem(temp);
		}
	}

	else if (parentPtr->isLeaf()) {
		std::cout << "Leaf" << std::endl;
		parentPtr->setLeftChildPtr(n1);
		parentPtr->setRightChildPtr(n2);
		parentPtr->setLargeItem(NULL);
		parentPtr->setMidItem(NULL);
		parentPtr->setSmallItem(temp);
	}

	std::cout << parentPtr->getSmallItem() << std::endl;
	std::cout << parentPtr->getMidItem() << std::endl;
	std::cout << parentPtr->getLargeItem() << std::endl;
}

template<class ItemType>
void TwoToFourTree<ItemType>::addToNode(QuadNode<ItemType>* treePtr, ItemType newItem) {

	if ((treePtr->getSmallItem() == NULL)) {
		treePtr->setSmallItem(newItem);
	}

	else if ((newItem > treePtr->getSmallItem()) && (treePtr->getLargeItem() == NULL)) {
		treePtr->setLargeItem(newItem);
	}

	else if ((newItem < treePtr->getSmallItem()) && (treePtr->getLargeItem() == NULL)) {
		treePtr->setLargeItem(treePtr->getSmallItem());
		treePtr->setSmallItem(newItem);
	}

	else if ((newItem > treePtr->getSmallItem()) && (newItem < treePtr->getLargeItem())) {
		treePtr->setMidItem(newItem);
	}

	else if ((newItem > treePtr->getSmallItem()) && (newItem > treePtr->getLargeItem())) {
		treePtr->setMidItem(treePtr->getLargeItem());
		treePtr->setLargeItem(newItem);
	}

	else if ((newItem < treePtr->getSmallItem()) && (newItem < treePtr->getLargeItem())) {
		treePtr->setMidItem(treePtr->getSmallItem());
		treePtr->setSmallItem(newItem);
	}
}


I really need help with this. My team is really counting on me, and I have no experience to balanced search trees prior to this assignment.
Last edited on
herooftime1000 (14)
Please! I'm desperate for an answer. I don't want to let my team down.
herooftime1000 (14)
I'm still in need of assistance. ANY hint that that will keep me going. I'm running around in circles.
cute apple (10)
*Haven't read all your code.
Did you tried not use template and see what the result look like?
cute apple (10)
• If you are using class, why pass treePtr all the time? And you didn't shows the QuadNode structure to us.

• You might fell more easy to implement it if is really a tree class, not a bunch of functions.

• Would you mind remove all getters and setters and use direct access to nodes (at least in member function), I would image it is only an array so direct access is clear here.
Last edited on
dhayden (5798)
I haven't seen 2-3-4 trees before but after a short review of the wikipedia page and looking at your code, here are some thoughts.

Lines 74-77: Why does locateLeaf() split the node? If you're using it to search for a node then you probably don't want to split it. If you need to split a node, do it in the caller.

LocateLeaf() doesn't check to see if the value already exists in the tree. Is this okay?

Line 132 leaks the memory allocated at line 129

Lines 168 and 169 look suspicious to me because you appear to erase the values that were in the parent node previously. I don't see those values copied anywhere else in the tree.

Line 249: What if it already has a mid item?
herooftime1000 (14)
Thank you all so much for your feedback. I'm going to try this again and just accept my overall grade as an A- if it doesn't go well. I'm sure you are all confused about the broken up code, but I had to erase a few things to fit the limit. Here's the entire code so far. (WIP)

http://www.mediafire.com/download/wv2vb0gctatuwyn/Homework5.zip
dhayden (5798)
isTwoNode() is wrong. It will mistakenly return true for a ThreeNode and a FourNode also.
Similarly, isThreeNode() will mistakenly return true for a FourNode

isFull() assumes that ItemType can convert to bool and that the conversion properly indicates whether an item has been inserted. This might be okay for your application, but it won't be in general.

split() is still leaking memory

Review the split() algorithm in your book. When parent is a FourNode, you are currently clearing the parent's midItem and largeItem without putting them somewhere else. That can't be right.

Also, the comments inside split talk about creating a new node, but you never do that. Well, you create a new node at the very beginning, but then you change the variable right after wards. Are you using the same variable for two different purposes? It looks like you need a new node, and you also want to keep track of the treePtr's parent. If that's true then use two different variables.

That's about all I can offer right now.
herooftime1000 (14)
I was able to get it all working now. Thank you for your feedback!
Topic archived. No new replies allowed.