Untitled
unknown
plain_text
a month ago
3.5 kB
4
Indexable
include <iostream> using namespace std; class Node { public: int data; Node* left; Node* right; int height; Node(int value) { data = value; left = NULL; right = NULL; height = 1; } }; class AVL { Node* root; int height(Node* node) { if (node == NULL) { return 0; } return node->height; } int getBalance(Node* node) { if (node == NULL) { return 0; } return height(node->left) - height(node->right); } Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; x->right = y; y->left = T2; y->height = max(height(y->left), height(y->right)) + 1; x->height = max(height(x->left), height(x->right)) + 1; return x; } Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; y->left = x; x->right = T2; x->height = max(height(x->left), height(x->right)) + 1; y->height = max(height(y->left), height(y->right)) + 1; return y; } Node* insert(Node* node, int value) { if (node == NULL) { return new Node(value); } if (value < node->data) { node->left = insert(node->left, value); } else if (value > node->data) { node->right = insert(node->right, value); } else { return node; } node->height = 1 + max(height(node->left), height(node->right)); int balance = getBalance(node); if (balance > 1 && value < node->left->data) { return rightRotate(node); } if (balance < -1 && value > node->right->data) { return leftRotate(node); } if (balance > 1 && value > node->left->data) { node->left = leftRotate(node->left); return rightRotate(node); } if (balance < -1 && value < node->right->data) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } void inorder(Node* root) { if (root != NULL) { inorder(root->left); cout << root->data << " "; inorder(root->right); } } void preorder(Node* root) { if (root != NULL) { cout << root->data << " "; preorder(root->left); preorder(root->right); } } void postorder(Node* root) { if (root != NULL) { postorder(root->left); postorder(root->right); cout << root->data << " "; } } public: AVL() { root = NULL; } void insert(int value) { root = insert(root, value); } void inorder() { inorder(root); cout << endl; } void preorder() { preorder(root); cout << endl; } void postorder() { postorder(root); cout << endl; } }; int main() { AVL tree; tree.insert(10); tree.insert(20); tree.insert(30); tree.insert(40); tree.insert(50); tree.insert(60); tree.insert(70); tree.inorder(); tree.preorder(); tree.postorder(); return 0; }
Editor is loading...
Leave a Comment