My own class of BS tree:
<code>namespace psarev
{
template < typename Key, typename Value, typename Compare = std::less< Key > >
class avlTree
{
public:
class ConstIterator;
class Iterator;
using cIter = ConstIterator;
using iter = Iterator;
using dataType = std::pair< Key, Value >;
avlTree();
avlTree(const avlTree& that);
avlTree(size_t& initSize, dataType& initData);
~avlTree();
avlTree& operator=(avlTree& that);
void clear();
private:
struct Unit
{
friend class avlTree;
dataType data;
Unit* ancest;
Unit* left;
Unit* right;
size_t hgt;
Unit(dataType data_, Unit* ancest_ = nullptr, int hgt_ = 0, Unit* left_ = nullptr, Unit* right_ = nullptr)
{
this->data = data_;
this->ancest = ancest_;
this->left = left_;
this->right = right_;
this->hgt = hgt_;
}
};
Unit* treeRoot;
size_t treeSize;
Unit* delUnit(Unit* node, const Key& key); *- problem method*
int getHeight(Unit* unit);
int getIneq(Unit* unit);
Unit* updData(Unit* unit, const dataType& data);
Unit* updData(Unit* unit, dataType&& data);
};
}
</code>
<code>namespace psarev
{
template < typename Key, typename Value, typename Compare = std::less< Key > >
class avlTree
{
public:
class ConstIterator;
class Iterator;
using cIter = ConstIterator;
using iter = Iterator;
using dataType = std::pair< Key, Value >;
avlTree();
avlTree(const avlTree& that);
avlTree(size_t& initSize, dataType& initData);
~avlTree();
avlTree& operator=(avlTree& that);
void clear();
private:
struct Unit
{
friend class avlTree;
dataType data;
Unit* ancest;
Unit* left;
Unit* right;
size_t hgt;
Unit(dataType data_, Unit* ancest_ = nullptr, int hgt_ = 0, Unit* left_ = nullptr, Unit* right_ = nullptr)
{
this->data = data_;
this->ancest = ancest_;
this->left = left_;
this->right = right_;
this->hgt = hgt_;
}
};
Unit* treeRoot;
size_t treeSize;
Unit* delUnit(Unit* node, const Key& key); *- problem method*
int getHeight(Unit* unit);
int getIneq(Unit* unit);
Unit* updData(Unit* unit, const dataType& data);
Unit* updData(Unit* unit, dataType&& data);
};
}
</code>
namespace psarev
{
template < typename Key, typename Value, typename Compare = std::less< Key > >
class avlTree
{
public:
class ConstIterator;
class Iterator;
using cIter = ConstIterator;
using iter = Iterator;
using dataType = std::pair< Key, Value >;
avlTree();
avlTree(const avlTree& that);
avlTree(size_t& initSize, dataType& initData);
~avlTree();
avlTree& operator=(avlTree& that);
void clear();
private:
struct Unit
{
friend class avlTree;
dataType data;
Unit* ancest;
Unit* left;
Unit* right;
size_t hgt;
Unit(dataType data_, Unit* ancest_ = nullptr, int hgt_ = 0, Unit* left_ = nullptr, Unit* right_ = nullptr)
{
this->data = data_;
this->ancest = ancest_;
this->left = left_;
this->right = right_;
this->hgt = hgt_;
}
};
Unit* treeRoot;
size_t treeSize;
Unit* delUnit(Unit* node, const Key& key); *- problem method*
int getHeight(Unit* unit);
int getIneq(Unit* unit);
Unit* updData(Unit* unit, const dataType& data);
Unit* updData(Unit* unit, dataType&& data);
};
}
When trying to compile, an error occurred with the key note “attempting to reference a deleted function” three times.
Method implementation:
<code>template<typename Key, typename Value, typename Compare>
typename psarev::avlTree< Key, Value, Compare >::Unit* psarev::avlTree< Key, Value, Compare >::delUnit(Unit* unit, const Key& key)
{
Compare compare;
if (unit == nullptr)
{
return unit;
}
if (compare(key, unit->data.first))
{
unit->left = delUnit(unit->left, key);
}
else if (compare(unit->data.first, key))
{
unit->right = delUnit(unit->right, key);
}
else
{
Unit* tempo = nullptr;
if ((unit->left == nullptr) && (unit->right == nullptr))
{
delete unit;
return nullptr;
}
else if (unit->right == nullptr)
{
tempo = unit->left;
*unit = *tempo; **- error here**
delete tempo;
}
else if (tempo->left == nullptr)
{
tempo = unit->right;
*unit = *tempo; **- error here**
delete tempo;
}
else
{
tempo = unit->right;
while (tempo->left != nullptr)
{
tempo = tempo->left;
}
unit->data = tempo->data; **- error here**
unit->right = delUnit(unit->right, tempo->data.first);
}
}
}
</code>
<code>template<typename Key, typename Value, typename Compare>
typename psarev::avlTree< Key, Value, Compare >::Unit* psarev::avlTree< Key, Value, Compare >::delUnit(Unit* unit, const Key& key)
{
Compare compare;
if (unit == nullptr)
{
return unit;
}
if (compare(key, unit->data.first))
{
unit->left = delUnit(unit->left, key);
}
else if (compare(unit->data.first, key))
{
unit->right = delUnit(unit->right, key);
}
else
{
Unit* tempo = nullptr;
if ((unit->left == nullptr) && (unit->right == nullptr))
{
delete unit;
return nullptr;
}
else if (unit->right == nullptr)
{
tempo = unit->left;
*unit = *tempo; **- error here**
delete tempo;
}
else if (tempo->left == nullptr)
{
tempo = unit->right;
*unit = *tempo; **- error here**
delete tempo;
}
else
{
tempo = unit->right;
while (tempo->left != nullptr)
{
tempo = tempo->left;
}
unit->data = tempo->data; **- error here**
unit->right = delUnit(unit->right, tempo->data.first);
}
}
}
</code>
template<typename Key, typename Value, typename Compare>
typename psarev::avlTree< Key, Value, Compare >::Unit* psarev::avlTree< Key, Value, Compare >::delUnit(Unit* unit, const Key& key)
{
Compare compare;
if (unit == nullptr)
{
return unit;
}
if (compare(key, unit->data.first))
{
unit->left = delUnit(unit->left, key);
}
else if (compare(unit->data.first, key))
{
unit->right = delUnit(unit->right, key);
}
else
{
Unit* tempo = nullptr;
if ((unit->left == nullptr) && (unit->right == nullptr))
{
delete unit;
return nullptr;
}
else if (unit->right == nullptr)
{
tempo = unit->left;
*unit = *tempo; **- error here**
delete tempo;
}
else if (tempo->left == nullptr)
{
tempo = unit->right;
*unit = *tempo; **- error here**
delete tempo;
}
else
{
tempo = unit->right;
while (tempo->left != nullptr)
{
tempo = tempo->left;
}
unit->data = tempo->data; **- error here**
unit->right = delUnit(unit->right, tempo->data.first);
}
}
}
Note: template argument Compare = std::less< Key >.
Error:
error log from VS
It occurred in three cases (noted them in the code).
This method deals with deleting the specified element (Unit) from the tree (without balancing, since there will be a separate method for this).
New contributor
AzraeL ‘ is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.