Example 1: avl tree implementation c++
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left;
Node *right;
int height;
};
int max(int a, int b);
int height(Node *N) {
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node *newNode(int key) {
Node *node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return (node);
}
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;
}
int getBalanceFactor(Node *N) {
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}
Node *insertNode(Node *node, int key) {
if (node == NULL)
return (newNode(key));
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),
height(node->right));
int balanceFactor = getBalanceFactor(node);
if (balanceFactor > 1) {
if (key < node->left->key) {
return rightRotate(node);
} else if (key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
}
if (balanceFactor < -1) {
if (key > node->right->key) {
return leftRotate(node);
} else if (key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
}
return node;
}
Node *nodeWithMimumValue(Node *node) {
Node *current = node;
while (current->left != NULL)
current = current->left;
return current;
}
Node *deleteNode(Node *root, int key) {
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
if ((root->left == NULL) ||
(root->right == NULL)) {
Node *temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
Node *temp = nodeWithMimumValue(root->right);
root->key = temp->key;
root->right = deleteNode(root->right,
temp->key);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->left),
height(root->right));
int balanceFactor = getBalanceFactor(root);
if (balanceFactor > 1) {
if (getBalanceFactor(root->left) >= 0) {
return rightRotate(root);
} else {
root->left = leftRotate(root->left);
return rightRotate(root);
}
}
if (balanceFactor < -1) {
if (getBalanceFactor(root->right) <= 0) {
return leftRotate(root);
} else {
root->right = rightRotate(root->right);
return leftRotate(root);
}
}
return root;
}
void printTree(Node *root, string indent, bool last) {
if (root != nullptr) {
cout << indent;
if (last) {
cout << "R----";
indent += " ";
} else {
cout << "L----";
indent += "| ";
}
cout << root->key << endl;
printTree(root->left, indent, false);
printTree(root->right, indent, true);
}
}
int main() {
Node *root = NULL;
root = insertNode(root, 33);
root = insertNode(root, 13);
root = insertNode(root, 53);
root = insertNode(root, 9);
root = insertNode(root, 21);
root = insertNode(root, 61);
root = insertNode(root, 8);
root = insertNode(root, 11);
printTree(root, "", true);
root = deleteNode(root, 13);
cout << "After deleting " << endl;
printTree(root, "", true);
}
Example 2: avl tree c implementation
#include <stdio.h>
#include "avltree.h"
void dispose(node* t)
{
if( t != NULL )
{
dispose( t->left );
dispose( t->right );
free( t );
}
}
node* find(int e, node* t )
{
if( t == NULL )
return NULL;
if( e < t->data )
return find( e, t->left );
else if( e > t->data )
return find( e, t->right );
else
return t;
}
node* find_min( node* t )
{
if( t == NULL )
return NULL;
else if( t->left == NULL )
return t;
else
return find_min( t->left );
}
node* find_max( node* t )
{
if( t != NULL )
while( t->right != NULL )
t = t->right;
return t;
}
static int height( node* n )
{
if( n == NULL )
return -1;
else
return n->height;
}
static int max( int l, int r)
{
return l > r ? l: r;
}
static node* single_rotate_with_left( node* k2 )
{
node* k1 = NULL;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->height = max( height( k2->left ), height( k2->right ) ) + 1;
k1->height = max( height( k1->left ), k2->height ) + 1;
return k1;
}
static node* single_rotate_with_right( node* k1 )
{
node* k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->height = max( height( k1->left ), height( k1->right ) ) + 1;
k2->height = max( height( k2->right ), k1->height ) + 1;
return k2;
}
static node* double_rotate_with_left( node* k3 )
{
k3->left = single_rotate_with_right( k3->left );
return single_rotate_with_left( k3 );
}
static node* double_rotate_with_right( node* k1 )
{
k1->right = single_rotate_with_left( k1->right );
return single_rotate_with_right( k1 );
}
node* insert(int e, node* t )
{
if( t == NULL )
{
t = (node*)malloc(sizeof(node));
if( t == NULL )
{
fprintf (stderr, "Out of memory!!! (insert)\n");
exit(1);
}
else
{
t->data = e;
t->height = 0;
t->left = t->right = NULL;
}
}
else if( e < t->data )
{
t->left = insert( e, t->left );
if( height( t->left ) - height( t->right ) == 2 )
if( e < t->left->data )
t = single_rotate_with_left( t );
else
t = double_rotate_with_left( t );
}
else if( e > t->data )
{
t->right = insert( e, t->right );
if( height( t->right ) - height( t->left ) == 2 )
if( e > t->right->data )
t = single_rotate_with_right( t );
else
t = double_rotate_with_right( t );
}
t->height = max( height( t->left ), height( t->right ) ) + 1;
return t;
}
node* delete( int e, node* t )
{
printf( "Sorry; Delete is unimplemented; %d remains\n", e );
return t;
}
int get(node* n)
{
return n->data;
}
void display_avl(node* t)
{
if (t == NULL)
return;
printf("%d",t->data);
if(t->left != NULL)
printf("(L:%d)",t->left->data);
if(t->right != NULL)
printf("(R:%d)",t->right->data);
printf("\n");
display_avl(t->left);
display_avl(t->right);
}