C++ algorithm AVL tree implement

1) add code to complete balance() function. This means add code to implement left-right and right-left double rotations. 2) add LeftRotation() content. 3) add print function to pretty print the tree by adding spaces at each level based on height of a node. 4)add deletion code to the AVL class, so we can delete a node from the tree. 5) add a function find(T val) to look for a node in the tree with data == val. If it finds it, returns the node pt, otherwise return nullptr. 6) add test cases for all these in the testAVL code.

header.h

namespace VGP244 { template struct Node { T data; std::shared_ptr> left; std::shared_ptr> right; int8_t height; Node(T k) : data(k), left(nullptr), right(nullptr), height(0) {} };

/*template using pNode_t = std::shared_ptr>;*/

template class AVL { public: using pNode_t = std::shared_ptr>; AVL() : root(nullptr) {}

void insert(T val) { root = insert(root, val); }

void printTree() { printNode(root); }

private: pNode_t root; int8_t GetHeight(pNode_t p) { return p ? p->height : 0; }

int8_t BalanceFactor(pNode_t p) { if (!p) return 0; return GetHeight(p->right) - GetHeight(p->left); }

void ComputeHeight(pNode_t p) { int8_t h1 = GetHeight(p->left); int8_t h2 = GetHeight(p->right); p->height = std::max(h1, h2) + 1; }

pNode_t RotateRight(pNode_t p) { pNode_t q = p->left; p->left = q->right; q->right = p; ComputeHeight(p); ComputeHeight(q); return q; }

pNode_t RotateLeft(pNode_t p) { // not implemented yet

pNode_t q = p->right; p->right = q->left; q->left = p; ComputeHeight(p); ComputeHeight(q); return q; }

pNode_t balance(pNode_t p) { // double rotation not implemented yet! ComputeHeight(p); auto p_balanceF = BalanceFactor(p); if (p_balanceF == 2) { return RotateLeft(p); }

else if (p_balanceF == -2) { return RotateRight(p); }

return p; } pNode_t insert(pNode_t p, T val) { if (!p) return std::make_shared>(val);

if (val < p->data) p->left = insert(p->left, val); else p->right = insert(p->right, val);

return balance(p); }

// pretty print a tree using space offset based on height void printNode(pNode_t node) { // not implemented yet! if (node != NULL) { std::cout << node->data << ", "; printNode(node->left); printNode(node->right); } }

pNode_t Remove(pNode_t p, T val) {

}

pNode_t Find(T val) {

}

};

} // namespace VGP244

main.cpp

#include #include "Header.h" using namespace VGP244; int main() { std::cout << "AVL tree construction app: "; std::cout << "Enter int value as data. To stop, enter -1 "; AVL avl; int val = 0; while (val != -1) { std::cin >> val; if (val != -1) { avl.insert(val); } } avl.printTree();

return 0; }