#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct AVLNode_t
{
int data;
struct AVLNode_t *left,*right;
int height;
}AVLNode;
typedef struct AVL_t
{
AVLNode *_root;
unsigned int _size;
}AVL;
/* Struktur Node */
typedef struct queueNode_t {
int data;
struct queueNode_t *next;
} QueueNode;
typedef struct queue_t {
QueueNode *_front,
*_rear;
unsigned _size;
} Queue;
AVLNode* _avl_createNode(int value) {
AVLNode
*newNode
= (AVLNode
*) malloc(sizeof(AVLNode
)); newNode->data = value;
newNode->height=1;
newNode->left = newNode->right = NULL;
return newNode;
}
AVLNode* _search(AVLNode *root, int value) {
while (root != NULL) {
if (value < root->data)
root = root->left;
else if (value > root->data)
root = root->right;
else
return root;
}
return root;
}
int _getHeight(AVLNode* node){
if(node==NULL)
return 0;
return node->height;
}
int _max(int a,int b){
return (a > b)? a : b;
}
AVLNode* _rightRotate(AVLNode* pivotNode) {
AVLNode* newParrent=pivotNode->left;
pivotNode->left=newParrent->right;
newParrent->right=pivotNode;
pivotNode->height=_max(_getHeight(pivotNode->left),
_getHeight(pivotNode->right))+1;
newParrent->height=_max(_getHeight(newParrent->left),
_getHeight(newParrent->right))+1;
return newParrent;
}
AVLNode* _leftRotate(AVLNode* pivotNode) {
AVLNode* newParrent=pivotNode->right;
pivotNode->right=newParrent->left;
newParrent->left=pivotNode;
pivotNode->height=_max(_getHeight(pivotNode->left),
_getHeight(pivotNode->right))+1;
newParrent->height=_max(_getHeight(newParrent->left),
_getHeight(newParrent->right))+1;
return newParrent;
}
AVLNode* _leftCaseRotate(AVLNode* node){
return _rightRotate(node);
}
AVLNode* _rightCaseRotate(AVLNode* node){
return _leftRotate(node);
}
AVLNode* _leftRightCaseRotate(AVLNode* node){
node->left=_leftRotate(node->left);
return _rightRotate(node);
}
AVLNode* _rightLeftCaseRotate(AVLNode* node){
node->right=_rightRotate(node->right);
return _leftRotate(node);
}
int _getBalanceFactor(AVLNode* node){
if(node==NULL)
return 0;
return _getHeight(node->left)-_getHeight(node->right);
}
AVLNode* _insert_AVL(AVL *avl,AVLNode* node,int value) {
if(node==NULL) // udah mencapai leaf
return _avl_createNode(value);
// Bebas mau dijadikan anak kanan atau anak kiri
if(value <= node->data)
node->left = _insert_AVL(avl,node->left,value);
else if(value > node->data)
node->right = _insert_AVL(avl,node->right,value);
node->height= 1 + _max(_getHeight(node->left),_getHeight(node->right));
int balanceFactor=_getBalanceFactor(node);
if(balanceFactor > 1 && value < node->left->data) // skewed kiri (left-left case)
return _leftCaseRotate(node);
if(balanceFactor > 1 && value > node->left->data) //
return _leftRightCaseRotate(node);
if(balanceFactor < -1 && value > node->right->data)
return _rightCaseRotate(node);
if(balanceFactor < -1 && value < node->right->data)
return _rightLeftCaseRotate(node);
return node;
}
AVLNode* _findMinNode(AVLNode *node) {
AVLNode *currNode = node;
while (currNode && currNode->left != NULL)
currNode = currNode->left;
return currNode;
}
AVLNode* _remove_AVL(AVLNode* node,int value){
if(node==NULL)
return node;
if(value > node->data)
node->right=_remove_AVL(node->right,value);
else if(value < node->data)
node->left=_remove_AVL(node->left,value);
else{
AVLNode *temp;
if((node->left==NULL)||(node->right==NULL)){
temp=NULL;
if(node->left==NULL) temp=node->right;
else if(node->right==NULL) temp=node->left;
if(temp==NULL){
temp=node;
node=NULL;
}
else
*node=*temp;
}
else{
temp = _findMinNode(node->right);
node->data=temp->data;
node->right=_remove_AVL(node->right,temp->data);
}
}
if(node==NULL) return node;
node->height=_max(_getHeight(node->left),_getHeight(node->right))+1;
int balanceFactor= _getBalanceFactor(node);
if(balanceFactor>1 && _getBalanceFactor(node->left)>=0)
return _leftCaseRotate(node);
if(balanceFactor>1 && _getBalanceFactor(node->left)<0)
return _leftRightCaseRotate(node);
if(balanceFactor < -1 && _getBalanceFactor(node->right)<=0)
return _rightCaseRotate(node);
if(balanceFactor < -1 && _getBalanceFactor(node->right)>0)
return _rightLeftCaseRotate(node);
return node;
}
void avl_init(AVL *avl) {
avl->_root = NULL;
avl->_size = 0u;
}
bool avl_isEmpty(AVL *avl) {
return avl->_root == NULL;
}
bool avl_find(AVL *avl, int value) {
AVLNode *temp = _search(avl->_root, value);
if (temp == NULL)
return false;
if (temp->data == value)
return true;
else
return false;
}
void avl_insert(AVL *avl,int value){
// if(!avl_find(avl,value)){
avl->_root=_insert_AVL(avl,avl->_root,value);
avl->_size++;
// }
}
void avl_remove(AVL *avl,int value){
if(avl_find(avl,value)){
avl->_root=_remove_AVL(avl->_root,value);
avl->_size--;
}
}
// QUEUE untuk nyari Index
void queue_init(Queue *queue)
{
queue->_size = 0;
queue->_front = NULL;
queue->_rear = NULL;
}
bool queue_isEmpty(Queue *queue) {
return (queue->_front == NULL && queue->_rear == NULL);
}
void queue_push(Queue *queue, int value)
{
QueueNode
*newNode
= (QueueNode
*) malloc(sizeof(QueueNode
)); if (newNode) {
queue->_size++;
newNode->data = value;
newNode->next = NULL;
if (queue_isEmpty(queue))
queue->_front = queue->_rear = newNode;
else {
queue->_rear->next = newNode;
queue->_rear = newNode;
}
}
}
void queue_pop(Queue *queue)
{
if (!queue_isEmpty(queue)) {
QueueNode *temp = queue->_front;
queue->_front = queue->_front->next;
if (queue->_front == NULL)
queue->_rear = NULL;
queue->_size--;
}
}
int queue_front(Queue *queue)
{
if (!queue_isEmpty(queue)) {
return (queue->_front->data);
}
return (int)0;
}
void preorder(AVLNode *root) {
if (root) {
preorder(root->left);
preorder(root->right);
}
}
void inorder(AVLNode *root, Queue *queue) {
if (root) {
inorder(root->left, queue);
queue_push(queue, root->data);
inorder(root->right, queue);
}
}
void postorder(AVLNode *root) {
if (root) {
postorder(root->left);
postorder(root->right);
}
}
int main(){
AVL avlku;
avl_init(&avlku);
int Q; //Query
int T; //Input
while(scanf("%d", &Q
) != EOF
){ if(Q == 1){
avl_insert(&avlku, T);
}
else{
if(!avl_find(&avlku, T)){
printf("M44f h3l c4r1 4ngk4 l4in y4\n"); }
else{
Queue queueku;
queue_init(&queueku);
inorder(avlku._root, &queueku);
int index = 1;
int same = 0;
// array buat nyimpen nilai yang akan dicek
// indeks nya menunjukkan nilai yang sama (same)
int cek[1000];
// dihapus satu-satu sambil dicek ada yang sama atau ndak
while(!queue_isEmpty(&queueku)){
if(queue_front(&queueku) != T){
queue_pop(&queueku);
index++;
}
else{
cek[same]=index;
queue_pop(&queueku);
same++;
index++;
}
}
if(same
== 1) printf("%d\n", cek
[0]); else{
if(same % 2 == 0)
printf("%d\n", cek
[same
/ 2 - 1]); else printf("%d\n", cek
[same
/ 2]); }
}
}
}
}