avl tree
unknown
plain_text
a year ago
2.4 kB
1
Indexable
Never
#include<iostream> #include<stdlib.h> using namespace std; struct Node { int key; struct Node *left; struct Node *right; int height; }; int getHeight(struct Node *n){ if(n == NULL) return 0; return n->height; } struct Node* createNode(int key){ struct Node* node = (struct Node *) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; return node; } int max(int a, int b){ return (a>b)?a:b; } int getBalanceFactor(struct Node*n){ if(n == NULL){ return 0; } return getHeight(n->left) - getHeight(n->right); } struct Node* rightRotate(struct Node* y){ struct Node*x = y->left; struct Node*T2; x->right = y; y->left = T2; x->height = max(getHeight(x->right) , getHeight(x->left)); x->height = max(getHeight(y->right) , getHeight(y->left)); return x; } struct Node* leftRotate(struct Node* x){ struct Node* y = x->right; struct Node* T2 = x->left; y->left = x; x->right = T2; x->height = max(getHeight(x->right), getHeight(x->left)); y->height = max(getHeight(y->right), getHeight(y->left)); return y; } struct Node *insert (struct Node* node, int key){ if( node == NULL) return createNode(key); if(key < node->key) node->left = insert (node->left , key ); else if(key > node->key) node->right = insert(node->right , key); node->height = 1 + max(getHeight(node->left), getHeight(node->right)); int bf = getBalanceFactor(node); //left left case if(bf>1 && key < node->left->key){ return rightRotate(node); } //right right case if(bf<-1 && key > node->right->key){ return leftRotate(node); } //left right case if(bf<-1 && key > node->right->key){ node->left = leftRotate(node->left); return rightRotate(node); } // right left case if(bf<-1 && key < node->right->key){ node->right = rightRotate(node->right); return leftRotate(node); } return node; } void inorder(struct Node *root) { if(root != NULL){ inorder(root->left); printf(" %d " , root->key); inorder(root->right); } } int main(){ struct Node * root = NULL; root = insert(root , 32); root = insert(root , 4); root = insert(root , 34); root = insert(root , 2); root = insert(root , 30); root = insert(root , 8); inorder(root); return 0; }