$//$ myAVLtree.hpp

#ifndef MY$\_$AVLTREE$\_$HPP

#define MY$\_$AVLTREE$\_$HPP

#include

#include

#include

struct node $\{$

int data;

int height;

node$*$ left;

node$*$ right;

node$($int data$)$ : data$($data$),$ height$(0),$ left$($nullptr$),$ right$($nullptr$)\{\}$

$\}$;

extern node$*$ root;

int height$($node$*$ t$)$;

void insert$($int x$,$ node$*$ & t$)$;

void balance$($node$*$ & t$)$;

void rotateWithLeftChild$($node$*$ & k$2)$;

void rotateWithRightChild$($node$*$ & k$1)$;

void doubleWithLeftChild$($node$*$ & k$3)$;

void doubleWithRightChild$($node$*$ & k$3)$;

void remove$($int data, node$*$ & t$)$;

void treeMedian$($const std::vector$*$ instructions$)$;

#endif

void treeMedian$($const std::vector$*$ instructions$)\{\}$

I just need implementation for avl treeMedian

void heapMedian$($const std::vector$*$ instructions$)\{$

$//$ Initialize two heaps: one for the smaller half $($max heap$)$ and one for the larger half $($min heap$)$

std::priority$\_$queue, std::less $>$ small; $//$ Max heap for the smaller half

std::priority$\_$queue, std::greater $>$ large; $//$ Min heap for the larger half

$//$ Iterate through the instructions

for $($int instruction : $*$instructions$)\{$

$//$ Check if the instruction is a pop median operation

if $($instruction $==-1)\{$

$//$ Print and remove the median element from the smaller heap

std::cout $<<$ small.top$()<<""$;

small.pop$()$;

$//$ Balance the heaps if the sizes are not equal

if $($small$.$size$()<$ large.size$())\{$

small.push$($large$.$top$())$;

large.pop$()$;

$\}$

$\}$ else $\{//$ Insert operation

$//$ Determine where to insert the element based on the current median

if $($small$.$empty$()||$ instruction $<=$ small.top$())\{$

small.push$($instruction$)$; $//$ Insert into the smaller heap

$\}$ else $\{$

large.push$($instruction$)$; $//$ Insert into the larger heap

$\}$

$//$ Balance the heaps if necessary

if $($small$.$size$()>$ large.size$()+1)\{$

large.push$($small$.$top$())$; $//$ Move the top element of the smaller heap to the larger heap

small.pop$()$;

$\}$ else if $($large$.$size$()>$ small.size$())\{$

small.push$($large$.$top$())$; $//$ Move the top element of the larger heap to the smaller heap

large.pop$()$;

$\}$

$\}$

$\}$

$\}$