I made a similar post on here but I did not get any useful feedback. I thus tried to re-do my code a bit to see if that would lead to any decent results. So far my code compiles but yet does not print anything and I am not sure why.
I have an example in int main() that should give me a tree that looks like:
/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/
Here is my code:
#include <algorithm>
#include <iostream>
#include <memory>
#include <utility>
#include <stack>
#include <queue>
struct Node {
int data;
int height;
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
Node(const int& x, const int& y, std::unique_ptr<Node>&& p = nullptr, std::unique_ptr<Node>&& q = nullptr) :
data(x),
height(y),
left(std::move(p)),
right(std::move(q)) {}
Node(const int& data) : data(data) {}
};
std::unique_ptr<Node> root = nullptr;
int height(std::unique_ptr<Node>& root) {
if (!root) return 0;
return root->height;
}
void fixHeight(std::unique_ptr<Node>& root) {
auto h1 = height(root->left);
auto h2 = height(root->right);
root->height = (h1 > h2 ? h1 : h2) + 1;
}
void rightRotate(std::unique_ptr<Node>& p) {
std::unique_ptr<Node> q = std::move(p->left);
p->left = std::move(q->right);
q->right = std::move(p);
fixHeight(p);
fixHeight(q);
}
void leftRotate(std::unique_ptr<Node>& q) {
std::unique_ptr<Node> p = std::move(q->left);
q->right = std::move(p->left);
p->left = std::move(q);
fixHeight(q);
fixHeight(p);
}
int heightDiff(std::unique_ptr<Node>& root) {
if (!root) return 0;
return height(root->left) - height(root->right);
}
void balance(std::unique_ptr<Node>& root) {
fixHeight(root);
if (heightDiff(root) == 2) {
if (heightDiff(root->right) < 0)
rightRotate(root->right);
leftRotate(root);
}
if (heightDiff(root) == -2) {
if (heightDiff(root->left) > 0)
leftRotate(root->left);
rightRotate(root);
}
}
void insert(std::unique_ptr<Node>& root, const int& theData) {
std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
if (!root) {
root = std::move(newNode);
return;
}
if (theData < root->data)
insert(root->left, theData);
else
insert(root->right, theData);
balance(root);
}
auto findMin(std::unique_ptr<Node>& root) {
while (root->left != nullptr) root = std::move(root->left);
return root.get();
}
void deleteNode(std::unique_ptr<Node>& root, const int& theData) {
// Step 1: Perform regular deletion for BST
if (!root) return;
else if (theData < root->data) deleteNode(root->left, theData);
else if (theData > root->data) deleteNode(root->right, theData);
else {
// Case 1: No child
if (root->left == nullptr && root->right == nullptr) {
root = nullptr;
}
// Case 2: One child
else if (root->left == nullptr) {
root = std::move(root->left);
}
else if (root->right == nullptr) {
root = std::move(root->right);
}
// Case 3: Two children
else {
auto temp = findMin(root->right);
temp->data = root->data;
deleteNode(root->right, temp->data);
}
}
if (!root) return;
// Step 2: Update height of the current node
root->height = 1 + std::max(height(root->left), height(root->right));
// Step 3: Get the balalce factor of the this node (to
// check whether this node became unbalanced)
int balance = heightDiff(root);
// If this node becomes unbalanced, then there are 4 cases
// Left Left Case
if (balance > 1 && heightDiff(root->left) >= 0)
rightRotate(root);
// Left Right Case
if (balance > 1 && heightDiff(root->left) < 0) {
leftRotate(root->left);
rightRotate(root);
}
// Right Right Case
if (balance < -1 && heightDiff(root->right) <= 0)
leftRotate(root);
// Right Left Case
if (balance < -1 && heightDiff(root->right) > 0) {
rightRotate(root->right);
leftRotate(root);
}
}
void inorderTraversal(std::unique_ptr<Node>& root) {
if (!root) {
inorderTraversal(root->left);
std::cout << root->data << " ";
inorderTraversal(root->right);
}
}
void preorderTraversal(std::unique_ptr<Node>& root) {
if (root != nullptr) {
std::cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
}
void postorderTraversal(std::unique_ptr<Node>& root) {
if (root != nullptr) {
postorderTraversal(root->left);
postorderTraversal(root->right);
std::cout << root->data << " ";
}
}
void DFS(std::unique_ptr<Node>& root) {
if (!root) return;
std::stack<Node const *> s;
s.push(root.get());
while (!s.empty()) {
auto p = s.top();
s.pop();
if (p->right != nullptr) s.push(p->right.get());
if (p->left != nullptr) s.push(p->left.get());
std::cout << p->data << " ";
}
}
void BFS(std::unique_ptr<Node>& root) {
if (!root) return;
std::queue<Node const *> q;
q.push(root.get());
while (!q.empty()) {
auto p = q.front();
q.pop();
if (p->left != nullptr) q.push(p->left.get());
if (p->right != nullptr) q.push(p->right.get());
std::cout << p->data << " ";
}
}
bool exists(int d) {
auto temp = root.get();
while (temp != nullptr) {
if (temp->data == d) {
return true;
}
else {
if (d > temp->data) {
temp = temp->right.get();
}
else {
temp = temp->left.get();
}
}
}
return false;
}
int main() {
// 8
// / \
// 4 10
// / \ / \
// 2 6 9 12
//insert(root, 8);
//insert(root, 10);
//insert(root, 4);
//insert(root, 2);
//insert(root, 6);
//insert(root, 12);
//insert(root, 9);
/* Constructing tree given in the above figure */
insert(root, 9);
insert(root, 5);
insert(root, 10);
insert(root, 0);
insert(root, 6);
insert(root, 11);
insert(root, -1);
insert(root, 1);
insert(root, 2);
/* The constructed AVL Tree would be
9
/ \
1 10
/ \ \
0 5 11
/ / \
-1 2 6
*/
printf("Preorder traversal of the constructed AVL "
"tree is \n");
preorderTraversal(root);
//deleteNode(root, 10);
/* The AVL Tree after deletion of 10
1
/ \
0 9
/ / \
-1 5 11
/ \
2 6
*/
//printf("\nPreorder traversal after deletion of 10 \n");
//preorderTraversal(root);
/*inorderTraversal(root);
std::cout << "\n";
preorderTraversal(root);
std::cout << "\n";
postorderTraversal(root);
std::cout << "\n";
DFS(root);
std::cout << "\n";
BFS(root);
std::cout << "\n";
exists(4) ? std::cout << "Yes" << std::endl : std::cout << "No" << std::endl;*/
std::cin.get();
}
