#include <stdio.h>
#include <stdlib.h>
struct AVLNode
{
int data;
struct AVLNode *left;
struct AVLNode *right;
int height;
};
int max(int a, int b)
{
return (a > b) ? a : b;
}
int height(struct AVLNode *node)
{
if (node == NULL)
{
return 0;
}
return node->height;
}
int cariBF(struct AVLNode *node)
{
if (node == NULL)
{
return 0;
}
return height(node->left) - height(node->right);
}
struct AVLNode *create(int data)
{
struct AVLNode
*node
= (struct AVLNode
*)malloc(sizeof(struct AVLNode
)); node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
struct AVLNode *rotateRight(struct AVLNode *pivotnode)
{
struct AVLNode *newp = pivotnode->left; // child kiri pivotnode jadi parent baru
struct AVLNode *T = newp ->right;
pivotnode->left = T; // child kanan new parent jadi child kiri pivot node
newp ->right = pivotnode; // right child newp jadi pivot
pivotnode->height = max(height(pivotnode->left), height(pivotnode->right)) + 1; // update height
newp ->height = max(height(newp ->left), height(newp ->right)) + 1;
return newp ;
}
struct AVLNode *rotateLeft(struct AVLNode *pivotnode)
{
struct AVLNode *newp = pivotnode->right; // right child pivot jadi parent baru
struct AVLNode *T = newp ->left;
pivotnode->right = T; // right child newp jadi left child pivot
newp->left = pivotnode; // left child newp jadi pivot
pivotnode->height = max(height(pivotnode->left), height(pivotnode ->right)) + 1;
newp->height = max(height(newp->left), height(newp->right)) + 1;
return newp;
}
struct AVLNode *insert(struct AVLNode *node, int data)
{
if (node == NULL)
{
return create(data);
}
if (data < node->data)
{
node->left = insert(node->left, data);
}
else if (data > node->data)
{
node->right = insert(node->right, data);
}
else
{
return node;
}
node->height = 1 + max(height(node->left), height(node->right));
int BF = cariBF(node);
if (BF > 1 && data < node->left->data)
{
return rotateRight(node);
}
if (BF < -1 && data > node->right->data)
{
return rotateLeft(node);
}
if (BF > 1 && data > node->left->data)
{
node->left = rotateLeft(node->left);
return rotateRight(node);
}
if (BF < -1 && data < node->right->data)
{
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
void hitungkolom(struct AVLNode *root, int *totalkolom, int *byk_kolom, int kolom)
{
if (root == NULL)
{
return;
}
totalkolom[kolom] += root->data; // jumlah nilai pd node
byk_kolom[kolom]++; // hitung jmlh kolom
hitungkolom(root->left, totalkolom, byk_kolom, kolom - 1); // indeks kolom
hitungkolom(root->right, totalkolom, byk_kolom, kolom + 1);
}
int kuadrat(int *totalkolom, int byk_kolom)
{
int ttl = 0;
for (int i = 0; i < byk_kolom; i++)
{
ttl += totalkolom[i] * totalkolom[i];
}
return ttl;
}
int main()
{
char cmd[10];
int node;
struct AVLNode *root = NULL;
while (scanf("%s", cmd
) != EOF
) {
if (cmd[0] == 'M')
{
root = insert(root, node);
}
else if (cmd[0] == 'H')
{
int totalkolom[1001] = {0};
int byk_kolom[1001] = {0};
hitungkolom(root, totalkolom, byk_kolom, 500);
printf("%d\n", kuadrat
(totalkolom
, 1001)); }
}
return 0;
}