from AVLTree import AVLTree

from ExtendedAVLNode import ExtendedAVLNode

class ExtendedAVLTree$($AVLTree$)$:

def $\_\_$init$\_\_($self$)$:

super$().\_\_$init$\_\_()$

# Override to create ExtendedAVLNodes

def make$\_$new$\_$node$($self$,$ key$)$:

return ExtendedAVLNode$($key$)$

def update$\_$all$\_$subtree$\_$counts$($self$,$ node$)$:

$"""$Update the subtree size for all ancestors of the node."""

current$\_$node $=$ node

while current$\_$node:

current$\_$node.update$\_$subtree$\_$key$\_$count$()$

current$\_$node $=$ current$\_$node.parent

def insert$($self$,$ key$)$:

$"""$Override insert to update subtree counts."""

new$\_$node $=$ super$().$insert$($key$)$ # Insert the node using AVL insert logic.

# After insertion, update the subtree key count of all affected nodes

self.update$\_$all$\_$subtree$\_$counts$($new$\_$node$)$

return new$\_$node

def remove$($self$,$ key$)$:

$"""$Override remove to update subtree counts."""

node$\_$to$\_$remove $=$ super$().$remove$($key$)$ # Remove the node using AVL remove logic.

# After removal, update the subtree key count of all affected nodes

if node$\_$to$\_$remove:

self.update$\_$all$\_$subtree$\_$counts$($node$\_$to$\_$remove.parent$)$

return node$\_$to$\_$remove

def get$\_$nth$\_$key$($self$,$ n$)$:

$"""$Efficiently get the nth key by using subtree key counts."""

current$\_$node $=$ self.root

while current$\_$node:

left$\_$size $=$ current$\_$node.left.subtree$\_$key$\_$count if current$\_$node.left else $0$

if n $<$ left$\_$size:

current$\_$node $=$ current$\_$node.left

elif n $==$ left$\_$size:

return current$\_$node.key

else:

n $-=($left$\_$size $+1)$ # Adjust n for the nodes in the left subtree

current$\_$node $=$ current$\_$node.right

return None # In case n is out of bounds.