blob: 3631fc634744e3ee85e2fec13f979016ef1a0d62 (
plain)
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
|
/*
* cTree.cpp
*
* Created on: Jan 30, 2017
* Author: jonas
*/
#include "cTree.h"
cTree::cTree()
{
root = new cEndnode();
}//Constructor
cTree::~cTree()
{
delete root;
}//Destructor
void cTree::insert(cData* _data)
{
root->insert(_data, &root);
}//insert
void cTree::insert(string _data)
{
cData* tmp = new cData(_data);
insert(tmp);
}//insert
void cTree::remove(cData* _data)
{
//Remove
sSubTree subTree;
root->remove(_data, &subTree, &root);
//Re-Insert subtree
if(subTree.nextBigger && subTree.nextSmaller)
{
cNode* newRoot = subTree.nextSmaller->getFirstNode( &(subTree.nextSmaller)); //returns zero
if(newRoot) //Only insert if nextSmaller is no Endnode
{
root->insert(newRoot, &root );
}
}
if (subTree.nextBigger) {
if(!subTree.nextBigger->isEndnode()) //Inserting Endnodes is pointless
root->insert(subTree.nextBigger, &root);
else
delete subTree.nextBigger; //Delete pointless Endnode
}
if(subTree.nextSmaller) {
if(!subTree.nextSmaller->isEndnode())
root->insert(subTree.nextSmaller, &root);
else
delete subTree.nextSmaller;
}
}//remove
void cTree::getList(list<cData>* _list)
{
root->getSortet(_list);
}//getList
void cTree::draw()
{
root->draw(0);
}//draw
cData* cTree::search(string _search)
{
return root->search(_search);
}//search
void cTree::clear()
{
delete root;
root = new cEndnode();
}//clear
void cTree::insertList(list<cData>* _list)
{
unsigned int oldSize = _list->size(); //used bc size of list changes during for-loop
list<cData> tmpList;
if (oldSize <= 0) //Nothing to do if list is empty
return;
for (unsigned int i = 0; i < oldSize / 2; i++) //copy first half of list into tmpList, deleting in _list
{
tmpList.push_back(_list->front());
_list->pop_front();
}
insert(_list->front().clone()); //middle element of _list is inserted as new root of subtree
_list->pop_front();
insertList(&tmpList); //Insert first half(smaller value) of list below new root
tmpList.clear();
if(_list->size() <= 0) //Nothing to do if list is empty
return;
insertList(_list); //Insert second half(bigger value) of list below new root
}//insertList
void cTree::sort()
{
list<cData> sortetList;
root->getSortet(&sortetList); //get inorder
clear(); //clear tree
insertList(&sortetList); //re insert inorderlist
}//sort
unsigned int cTree::size()
{
return root->getSubtreeSize();
}//size
unsigned int cTree::depth()
{
return root->getDepth(0);
}//depth
unsigned int cTree::gradeOfUnbalance()
{
if(root->getSubtreeSize() == 0)
return 0;
double minDepth = log2(size());
unsigned int iDepth = depth();
return (iDepth / minDepth) - 1; //-1 so 100% = 0
}//gradeOfUnbalance
cData *cTree::operator [](unsigned int _i)
{
unsigned int a = 0;
return root->getById(_i, a);
}
|