When your question is answered use !solved to mark the question as resolved.
Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.
#Weird string comparisons: How is "key1b">"key10b"?
tidal nimbusBOT
solemn crater
String comparisons use a equivalent function to this https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare
The character 'b' is larger than the character '0'
lucid parrot
you can give / use a custom comparison
potentially 🤔
or simply not care about it
howso breaks?
solemn crater
Or use an integer for the key?
lucid parrot
I mean you are making it right? could always simply make everything use a lexicographical compare
solemn crater
Make the function use lexiograpical comparison
Like @lucid parrot said
I assumed your function did something else than the default comparison
If you use the same comparison function when making the tree and searching it there shouldn’t be a problem
Could you post the code?
tidal nimbusBOT
template<typename KeyType, typename ItemType>
KeyType BinarySearchTree<KeyType, ItemType>::getKey(ItemType& item) {
Node<KeyType, ItemType>* curr = root;
while (curr != nullptr) {
if (item < curr->data) {
curr = curr->left;
} // end if
else if (item > curr->data) {
curr = curr->right;
} // end else if
else {
break;
} // end else
} // end while loop
return curr->key;
}
The Fenice
template<typename KeyType, typename ItemType>
bool BinarySearchTree<KeyType, ItemType>::insert(const KeyType& key,
const ItemType& item) {
// creating new node
Node<KeyType, ItemType>* curr = root;
Node<KeyType, ItemType>* parent;
search(key, curr, parent);
// checking if node already exists
if (curr != nullptr && curr->key == key) {
return false;
} // end if
Node<KeyType, ItemType>* newNode = new Node<KeyType, ItemType>;
newNode->key = key;
newNode->data = item;
newNode->left = nullptr;
newNode->right = nullptr;
if (root == nullptr) { // root doesn't exist
root = newNode;
return true;
} // end if
else {
if (key < curr->key) { // parent exists but has no right child
curr->left = newNode;
} // end else
else { // parent exists but has no left child
curr->right = newNode;
} // end else
} // end else
return true;
}
Do you have a method called search too?
tidal nimbusBOT
template<typename KeyType, typename ItemType>
void BinarySearchTree<KeyType, ItemType>::search(
KeyType key,
Node<KeyType, ItemType>*& curr,
Node<KeyType, ItemType>*& parent) {
curr = root;
parent = 0;
if (isEmpty())
return;
while (true) {
if (key == curr->key) {
break;
} else if (key < curr->key) {
if (curr->left != 0) {
parent = curr;
curr = curr->left;
} else
break;
} else {
if (curr->right != 0) {
parent = curr;
curr = curr->right;
} else
break;
}
}
}
I don’t think your getKey function is correct
Unless the items ordering is directly related to key ordering
Why do you have key value pairs then?
Just have one of them and extract the other from that
The easiest way is probably to change the getKey function
Good luck with the assignment 🙂
tidal nimbusBOT
lucid parrot
sweet :)