Demo entry 4785800

AVL Tree

   

Submitted by Irsyad Rizaldi on May 17, 2016 at 17:44
Language: C++. Code size: 3.2 kB.

//AVL TREE by IRSYAD RIZALDI
//reference: http://kukuruku.co/hub/cpp/avl-trees

#include <bits/stdc++.h>
using namespace std;

//binary tree structure
struct btree{
	int value, height;
	btree *left, *right;
	btree(int x){
		value=x;
		height=1;
		left=right=NULL;
	}
};

//get height of a parent
void height(btree *&parent){
	int hl, hr;
	parent->left?hl=parent->left->height:hl=0;
	parent->right?hr=parent->right->height:hr=0;
	parent->height=max(hl,hr)+1;
}

//rotate sub-tree to right
void rotateright(btree *&parent){
	btree *pr=parent;
	parent=parent->left;
	pr->left=parent->right;
	parent->right=pr;
	height(pr);
	height(parent);
}

//rotate sub-tree to left
void rotateleft(btree *&parent){
	btree *pl=parent;
	parent=parent->right;
	pl->right=parent->left;
	parent->left=pl;
	height(pl);
	height(parent);
}

//balance factor, decide when a sub-tree need to be balanced
int bfactor(btree *&parent){
	int bl,br;
	parent->left?bl=parent->left->height:bl=0;
	parent->right?br=parent->right->height:br=0;
	return bl-br;
}

//balancing sub-tree
void balance(btree *&parent){
	height(parent);
	int bf=bfactor(parent);
	if(bf == 2){
		if(bfactor(parent->left) < 0)
			rotateleft(parent->left);
		rotateright(parent);
	}
	else if(bf == -2){
		if(bfactor(parent->right) > 0)
			rotateright(parent->right);
		rotateleft(parent);
	}
}

//insert value to tree
void insert(btree *&parent, int value){
	if(!parent)
		parent=new btree(value);
	else if(value < parent->value)
		insert(parent->left, value);
	else
		insert(parent->right, value);
	balance(parent);
}

//find minimum value in a sub-tree
void findmin(btree *&parent, btree *&min){
	if(!parent->left){
		min = parent;
		parent = parent->right;
	}
	else{
		findmin(parent->left, min);
		balance(parent);
	}
}

//remove value from tree
void remove(btree *&parent, int value){
	if(!parent)
		return;
	else if(value < parent->value)
		remove(parent->left, value);
	else if(value > parent->value)
		remove(parent->right, value);
	else{
		btree *pl=parent->left, *pr=parent->right;
		if(!pr){
			parent=pl;
			return;
		}
		else{
			btree *min=pr;
			findmin(pr, min);
			delete parent;
			parent=min;
			parent->left=pl;
			parent->right=pr;
			balance(min);
		}
	}
	balance(parent);
}

//find value in a tree
void find(btree *&parent, int value){
	if(!parent)
		puts("No Data\n");
	else if(parent->value == value)
		printf("Data Found!\n");
	else if(value < parent->value)
		find(parent->left, value);
	else
		find(parent->right, value);
}

//print tree in preorder traversal
void preorder(btree *&parent){
	if(!parent)
		return;
	printf("%d",parent->value);
	preorder(parent->left);
	preorder(parent->right);
}

//print tree in inorder traversal
void inorder(btree *&parent){
	if(!parent)
		return;
	inorder(parent->left);
	printf("%d",parent->value);
	inorder(parent->right);
}

//print tree in postorder traversal
void postorder(btree *&parent){
	if(!parent)
		return;
	postorder(parent->left);
	postorder(parent->right);
	printf("%d",parent->value);
}

int main(){
	btree *root=NULL;
	//codes here
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).