86 lines
2.7 KiB
C++
86 lines
2.7 KiB
C++
#include "ExtendedBinaryTreeNode.h"
|
|
|
|
#include <iostream>
|
|
|
|
ExtendedBinaryTreeNode::ExtendedBinaryTreeNode(Ware *key, int priority) {
|
|
this->key = key;
|
|
this->left = nullptr;
|
|
this->right = nullptr;
|
|
this->priority = priority;
|
|
}
|
|
|
|
ExtendedBinaryTreeNode *ExtendedBinaryTreeNode::insert(Ware *key,
|
|
int priority) {
|
|
if (key->getVerkaufspreis() > this->key->getVerkaufspreis()) {
|
|
if (this->right == nullptr) {
|
|
ExtendedBinaryTreeNode *temp = new ExtendedBinaryTreeNode(key, priority);
|
|
this->right = temp;
|
|
return this->right;
|
|
}
|
|
this->right->insert(key, priority);
|
|
} else {
|
|
if (this->left == nullptr) {
|
|
ExtendedBinaryTreeNode *temp = new ExtendedBinaryTreeNode(key, priority);
|
|
this->left = temp;
|
|
return this->left;
|
|
}
|
|
this->left->insert(key, priority);
|
|
}
|
|
return this;
|
|
}
|
|
|
|
ExtendedBinaryTreeNode *ExtendedBinaryTreeNode::deleteItem(Ware *key) {
|
|
ExtendedBinaryTreeNode *node = this;
|
|
|
|
if (node == nullptr) {
|
|
return this;
|
|
} else if (key->getVerkaufspreis() < node->key->getVerkaufspreis()) {
|
|
node->left = node->left->deleteItem(key);
|
|
} else if (key->getVerkaufspreis() > node->key->getVerkaufspreis()) {
|
|
node->right = node->right->deleteItem(key);
|
|
} else {
|
|
if (node->left == nullptr && node->right == nullptr) {
|
|
delete node;
|
|
node = nullptr;
|
|
} else if (node->left == nullptr) { // only children in right subtree
|
|
ExtendedBinaryTreeNode *temp = node;
|
|
node = node->right;
|
|
delete temp;
|
|
} else if (this->right == nullptr) { // only children in left subtree
|
|
ExtendedBinaryTreeNode *temp = node;
|
|
node = node->left;
|
|
delete temp;
|
|
} else { // we have to keep the BST structure, here, we look for the minimum
|
|
// in the right subtree (see lecture)
|
|
ExtendedBinaryTreeNode *temp = node->right;
|
|
while (temp->left != nullptr) {
|
|
temp = temp->left;
|
|
}
|
|
node->key = temp->key;
|
|
node->right = node->right->deleteItem(temp->key);
|
|
}
|
|
}
|
|
return node;
|
|
}
|
|
|
|
ExtendedBinaryTreeNode *ExtendedBinaryTreeNode::leftRotation() {
|
|
// std::cout << "Do a left rotation on node " << this->key << "\n";
|
|
ExtendedBinaryTreeNode *rightNode = this->right;
|
|
ExtendedBinaryTreeNode *leftOfRightNode = rightNode->left;
|
|
|
|
rightNode->left = this;
|
|
this->right = leftOfRightNode;
|
|
return rightNode;
|
|
}
|
|
|
|
// perform a right rotation (see lecture)
|
|
ExtendedBinaryTreeNode *ExtendedBinaryTreeNode::rightRotation() {
|
|
// std::cout << "Do a right rotation on node " << this->key << "\n";
|
|
ExtendedBinaryTreeNode *leftNode = this->left;
|
|
ExtendedBinaryTreeNode *rightOfLeftNode = leftNode->right;
|
|
|
|
leftNode->right = this;
|
|
this->left = rightOfLeftNode;
|
|
|
|
return leftNode;
|
|
} |