/*Patrick Catalin Alexandru Sava
University of Bucharest
Faculty of Mathematics and Computer Science*/
#include <fstream>
#include <cassert>
#include <vector>
#include <cstdio>
using namespace std ;
ifstream cin ("hashuri.in") ; // what is the input file
ofstream cout ("hashuri.out") ; // what is the output file
/*AVL tree
support duplicates but not in different nodes
duplicates are kept by an variable -> freq
insert -> O (logN)
delete -> O (logN)
find -> O (logN)
*/
class ArboreAVL {
public :
ArboreAVL() { // constructor without parameters
Root = NULL ; // initialize the root of tree with nullptr
avl_size = 0 ; // keep the number of elements from tree
deallocate = true ; // deallocate memory by default when call destructor
}
ArboreAVL(vector <int> &Elements) { // constructor with parameters
Root = NULL ; // initialize the root of tree with nullptr
avl_size = 0 ; // keep the number of elements from tree
deallocate = true ; // deallocate memory by default when call destructor
for (auto x : Elements) { // insert each element in AVL
this->InsertKey (x) ;
}
}
ArboreAVL(ArboreAVL &other) { // constructor for copy the content of other object (with the same type)
Root = NULL ; // initialize the root of tree with nullptr
avl_size = 0 ; // keep the number of elements from tree
deallocate = true ; // deallocate memory by default when call destructor
vector <int> OtherTraversal = other.SortedOrder () ;
for (auto x : OtherTraversal) { // insert each element in AVL
this->InsertKey (x) ;
cout << "am bagat " << x << endl ;
}
}
~ArboreAVL() { // destructor
if (deallocate == true) { // if is set on true, deallocate
erase_all (Root) ;
}
}
ArboreAVL operator + (ArboreAVL &other) { // overload + operator
ArboreAVL Result ; // keep an auxiliar instance
Result.CantDeallocate() ; // can t deallocate the elements of the tree nested there
vector <int> OtherTraversal = other.InOrderTraversal () ; // in order traversal without duplicates
vector <int> CurrentTraversal = this-> InOrderTraversal () ; // in order traversal without duplicates
for (auto x : OtherTraversal) { // move all elements in AVL tree
Result.InsertKey (x) ;
}
for (auto x : CurrentTraversal) { // move elements
if (Result.FindKey(x) == false) { // only if is not yet in tree
Result.InsertKey (x) ;
}
}
return Result ;
}
ArboreAVL& operator = (ArboreAVL &&other) {
// cout << "entered\n" ;
this -> clear() ; // equal means that the old content is discarded
vector <int> OtherTraversal = other.SortedOrder () ; // with duplicates
for (auto x : OtherTraversal) { // move elements
this -> InsertKey (x) ;
}
return *this ;
}
bool operator > (ArboreAVL &other) { // overload > operator
return this->MaximalElement() > other.MaximalElement() ;
}
bool operator < (ArboreAVL &other) { // overload < operator
return this->MaximalElement() < other.MaximalElement() ;
}
friend ostream &operator<< (ostream &output, ArboreAVL &other) { // overload write operator
vector <int> Elements = other.SortedOrder() ;
for (auto x : Elements) {
output << x << ' ' ;
}
output << '\n' ;
}
friend istream &operator>> (istream &input, ArboreAVL &other) { // overload read operator
other.clear() ; // is overwritten on the current tree
int n ;
input >> n ;
while (n --) {
int x ;
input >> x ;
other.InsertKey (x) ;
}
}
void InsertKey (int value) {
avl_size += 1 ; // the number of element from tree is increased by 1
if (find_node_of_key (Root, value) != NULL) { // if is already
//find_node_of_key (Root, value) -> freq += 1 ; // only increase the freq for that node
//cout << "mai era si inainte\n" ;
}
else {
Root = insert_key (Root, value) ; // else, create a new node
}
update_heights(Root) ; // update the height of root
//cout << "inaltimea dupa inserite este : " << wheight(Root) << '\n' ;
// ^ verify if the height is correct
}
void DeleteKey (int value) {
if (not FindKey (value)) {
return ; // ignore if the command is invalid
}
avl_size -= 1 ; // the number of element from tree is decreased by 1
if (-- find_node_of_key (Root, value) -> freq == 0) { // decrease the freq from the node where the value is located
delete_key (Root, value) ; // delete the node from tree if the node appears 0 times
}
update_heights(Root) ; // update height
//cout << "inaltimea dupa deletie este : " << wheight(Root) << '\n' ;
// ^ verify if the height is correct
}
bool FindKey (int value) {
if (find_node_of_key (Root, value) == NULL) { // if there is no node with that value
return false ; // the value is not in tree
}
return true ; // otherwise
}
vector <int> InOrderTraversal () {
return in_order (Root) ; // without duplicates
}
vector <int> PreOrderTraversal () {
return pre_order (Root) ; // without duplicates
}
vector <int> PostOrderTraversal () {
return post_order (Root) ; // without duplicates
}
vector <int> SortedOrder () {
return sorted_order (Root) ; // with duplicates
}
int Size () {
return avl_size ; // number of elements from tree
}
void CantDeallocate() {
deallocate = false ; // decide if you want to remove nodes from Struct AVL when you delete the instance
}
int MaximalElement()
{
assert (Size() != 0) ; // if the tree is empty, throw an exception
return get_max (Root) ; // get the max element
}
private :
struct AVL {
int key ; // the key
int freq ; // number of appearances
unsigned char height ; // height, is enough
AVL *leftson ; // pointer to the left son
AVL *rightson ; // pointer to the right one
AVL (int otherkey, int otherfreq, unsigned char otherheight, AVL *otherleftson, AVL *otherightson) {
this -> key = otherkey ;
this -> freq = otherfreq ;
this -> height = otherheight ;
this -> leftson = otherleftson ;
this -> rightson = otherightson ;
}
};
AVL *Root ;
int avl_size ;
bool deallocate ;
int wheight (AVL *&node) { // wraper function on node; careness for avoid killed by signal
if (node == NULL) {
return 0 ;
}
return (int)node -> height ;
}
int balance_factor (AVL *&node) { // balance factor is defined as the difference between heights of children
if (node == NULL) {
return 0 ;
}
return wheight (node -> leftson) - wheight (node -> rightson) ;
}
void update_heights (AVL *&node) { // update heights for calculate correctly the balance factor and mantain the tree
if (node == NULL) { // with log N height everytime
return ;
}
int left_height = wheight (node -> leftson) ;
int right_height = wheight (node -> rightson) ;
if (left_height > right_height) {
node -> height = 1 + left_height ;
}
else {
node -> height = 1 + right_height ;
}
}
void rotate_left (AVL *&node) {
/* 1
/ \
2 5
/ \ / \
3 4 6 7
rotation to the left node 1 produces the next tree
5
/ \
1 7
/ \
2 6 */
assert (node != NULL) ;
assert (node -> rightson != NULL) ;
AVL *_5 = node -> rightson ;
AVL *_6 = _5 -> leftson ;
_5 -> leftson = node ;
node -> rightson = _6 ;
node = _5 ;
update_heights (node -> leftson) ; // rotate and then update height
update_heights (node -> rightson) ;
update_heights (node) ;
}
void rotate_right (AVL *&node) {
/* 1
/ \
2 5
/ \ / \
3 4 6 7
rotation to the right node 1 produces the next tree
2
/ \
3 1
/ \
4 5 */
assert (node != NULL) ;
assert (node -> leftson != NULL) ;
AVL *_2 = node -> leftson ;
AVL *_4 = _2 -> rightson ;
_2 -> rightson = node ;
node -> leftson = _4 ;
node = _2 ;
update_heights (node -> leftson) ; // rotate and then update height
update_heights (node -> rightson) ;
update_heights (node) ;
}
void balance (AVL *&node) {
if (node != NULL) {
update_heights (node -> leftson) ;
update_heights (node -> rightson) ;
}
update_heights (node) ;
if (balance_factor (node) == 2) { // balance by rotating subtrees depending balance_factor
if (balance_factor (node -> leftson) < 0) {
rotate_left (node -> leftson) ;
}
rotate_right (node) ;
}
if (balance_factor (node) == -2) {
if (balance_factor (node -> rightson) > 0) {
rotate_right (node -> rightson) ;
}
rotate_left (node) ;
}
}
AVL *find_node_of_key (AVL *node, int value) // find by recursion the node where value is located
{
if (node == NULL) {
return NULL ; // otherwise return NULL
}
if (node -> key < value) {
return find_node_of_key (node -> rightson, value) ;
}
if (node -> key > value) {
return find_node_of_key (node -> leftson, value) ;
}
return node ;
}
AVL* insert_key (AVL *&node, int value) {
if (node == NULL) { // where the value should be
return new AVL (value, 1, 1, NULL, NULL) ;
}
if (value < node -> key) { // find by recursion
node -> leftson = insert_key (node -> leftson, value) ;
}
else {
node -> rightson = insert_key (node -> rightson, value) ;
}
balance (node) ; // do not forget to balance
return node ;
}
pair <int, int> extract_min (AVL *&node) { // get minimal element from the sub tree rooted in node, with removing it
if (node -> leftson == NULL) {
pair <int, int> answer = make_pair (node -> key, node -> freq) ;
AVL *&keep = node -> rightson ;
delete node ;
node = keep ;
balance(node) ;
return answer ;
}
return extract_min (node -> leftson) ;
}
int get_max (AVL *&node) { // get maximal element from the sub tree rooted in node, without removing it
if (node -> rightson == NULL) {
return node -> key ;
}
return get_max (node -> rightson) ;
}
void delete_key (AVL *&node, int value) {
if (node == NULL) {
return ;
}
if (node -> key > value) { // find by recursion
delete_key (node -> leftson, value) ;
}
else if (node -> key < value) {
delete_key (node -> rightson, value) ;
}
else { // find the place where the element is
AVL *&rightson = node -> rightson ;
AVL *&leftson = node -> leftson ;
delete node ;
node = NULL ;
if (rightson == NULL) { // if doesn t have left son
node = leftson ; // rightson become the new node after deletion
return ;
}
pair <int, int> minimal_element = extract_min (rightson) ; // ptherwise, get the minimal element from the right subtree
node = new AVL (minimal_element.first, minimal_element.second, 0, leftson, rightson) ;
}
balance (node) ; // do not forget to balance
}
vector <int> in_order (AVL *&node) {
// (Left, Root, Right)
if (node == NULL) { // in order traversal, without duplicates
return vector <int> () ;
}
vector <int> temp = in_order (node -> leftson) ;
temp.push_back (node -> key) ;
vector <int> temp_right = in_order (node -> rightson) ;
for (auto x : temp_right) {
temp.push_back (x) ;
}
return temp ;
}
vector <int> pre_order (AVL *&node) {
// (Root, Left, Right)
if (node == NULL) { // pre order traversal, without duplicates
return vector <int> () ;
}
vector <int> temp ;
temp.push_back (node -> key) ;
vector <int> sons = pre_order (node -> leftson) ;
for (auto x : sons) {
temp.push_back (x) ;
}
sons = pre_order (node -> rightson) ;
for (auto x : sons) {
temp.push_back (x) ;
}
return temp ;
}
vector <int> post_order (AVL *&node) {
// (Left, Right, Root)
if (node == NULL) { // post order traversal, without duplicates
return vector <int> () ;
}
vector <int> temp ;
vector <int> sons = pre_order (node -> leftson) ;
for (auto x : sons) {
temp.push_back (x) ;
}
sons = pre_order (node -> rightson) ;
for (auto x : sons) {
temp.push_back (x) ;
}
temp.push_back (node -> key) ;
return temp ;
}
vector <int> sorted_order (AVL *&node) {
// (Left, Root, Right)
if (node == NULL) { // sorted order
return vector <int> () ; // with the help of binary search tree
} // properties; with duplicates
vector <int> temp = sorted_order (node -> leftson) ;
int times = node -> freq ;
//cout << "times este " << times << " pentru " << node -> key << '\n' ;
while (times --) {
temp.push_back (node -> key) ;
}
vector <int> temp_right = sorted_order (node -> rightson) ;
for (auto x : temp_right) {
temp.push_back (x) ;
}
return temp ;
}
void erase_all (AVL *&node) { // erase the entire list
if (node == NULL) {
return ;
}
erase_all (node -> leftson) ;
erase_all (node -> rightson) ;
delete node ;
}
void clear ()
{
// reset all the variables
avl_size = 0 ;
erase_all(Root) ;// and erase the list
Root = NULL ;
deallocate = true ;
}
};
int main () {
// a little demo
ArboreAVL *A = new ArboreAVL() ;
int op ;
cin >> op ;
while (op --) {
int type ;
cin >> type ;
if (type == 1) {
int x ;
cin >> x ;
A -> InsertKey (x) ;
}
else if (type == 2) {
int x ;
cin >> x ;
A -> DeleteKey (x) ;
}
else {
int x ;
cin >> x ;
cout << A -> FindKey (x) << '\n' ;
}
}
return 0 ;
ArboreAVL *B = new ArboreAVL() ;
int n ;
cin >> n ;
vector <int> ForFind ;
for (int i = 1 ; i <= n; ++ i) {
int x ;
cin >> x ;
A -> InsertKey (x) ;
B -> InsertKey (x) ;
if (i % 2 == 0) {
A -> DeleteKey (x) ;
}
else {
ForFind.push_back (x) ;
}
}
cout << *A ;
cout << *B ;
// return 0 ;
ArboreAVL *C = new ArboreAVL() ;
//*C = *A ;
*C = *A + *B ;
cout << *C ;
ArboreAVL *D = new ArboreAVL(*C) ;
vector <int> aux ;
aux.push_back(14) ;
//return 0 ;
ArboreAVL *E = new ArboreAVL (aux) ;
cout << *D ;
*D = *D + *E ;
cout << *D ;
return 0 ;
//return 0 ;
//cout << C -> Size () << ' ' << B -> Size() << '\n' ;
//return 0 ;
// assert (C -> Size() == B -> Size()) ;
for (auto x : ForFind) {
assert (A -> FindKey (x) == true) ;
}
cout << *A ;
cout << *B ;
cout << C -> Size() << '\n' ;
//return 0 ;
cout << *C ;
C -> InsertKey (7) ;
cout << C -> Size() << '\n' ;
//return 0 ;
cout << *C ;
C -> InsertKey (7) ;
cout << *C ;
C -> DeleteKey (7) ;
cout << *C ;
C -> DeleteKey (7) ;
cout << *C ;
C -> DeleteKey (1) ;
cout << *C ;
cout << (*C > *A) << '\n' ;
cin >> *C ;
cout << *C ;
delete A ;
delete B ;
delete C ;
/*int last = -1 ;
vector< pair <int, int> > Solution = C -> Pop () ;
for (auto &x : Solution) {
while (x.second --) {
cout << x.first << ' ' ;
}
assert (last <= x.first) ;
last = x.first ;
}*/
return 0 ;
}
Patrick Sava xtreme77