package Ġcom . aar on . binary tree . bst Ċ Ċ import Ġkotlin . math . abs Ċ import Ġkotlin . math . max Ċ Ċ /** Ċ Ġ* Ġ@ author Ġa aron zz x up @ gmail . com Ċ Ġ* Ġ@ since Ġ 2 0 2 1 / 1 2 / 3 Ċ Ġ*/ Ċ class ĠA VL Tree < E >( comparator : ĠComparator < E >? Ġ= Ġnull ) Ġ: ĠB ST < E >( comparator ) Ġ{ ĊĊĠĠĠ Ġoverride Ġfun Ġafter Add ( node : ĠBase Node < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck Balance And Fix ( node , Ġtrue ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġafter Remove ( node : ĠBase Node < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck Balance And Fix ( node , Ġfalse ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġcheck Balance And Fix ( node : ĠBase Node < E >, Ġfor Add : ĠBoolean ) Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġ_ node : ĠA VL Node < E >? Ġ= Ġnode Ġas ĠA VL Node < E > ĊĠĠĠĠĠĠĠ Ġwhile Ġ(_ node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ node . is Bal anced ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ_ node . update Height () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġre balance (_ node ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( for Add ) Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ node Ġ= Ġ_ node . parent () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġre balance ( grand : ĠA VL Node < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġson Ġ= Ġgrand . t aller Child !! ĊĠĠĠĠĠĠĠ Ġval Ġgrand son Ġ= Ġson . t aller Child !! ĊĠĠĠĠĠĠĠ Ġif Ġ( son . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( grand son . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠLL ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( grand ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠLR ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( son ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( grand ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( grand son . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRL ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Right ( son ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( grand ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠRR ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġrotate Left ( grand ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġrotate Left ( grand : ĠA VL Node < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġson Ġ= Ġgrand . right () !! ĊĠĠĠĠĠĠĠ Ġval Ġgrand son Ġ= Ġson . left () ĊĠĠĠĠĠĠĠ Ġgrand . right Ġ= Ġgrand son ĊĠĠĠĠĠĠĠ Ġson . left Ġ= Ġgrand ĊĠĠĠĠĠĠĠ Ġafter Rotate ( grand , Ġson , Ġgrand son ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġrotate Right ( grand : ĠA VL Node < E >) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġson Ġ= Ġgrand . left () !! ĊĠĠĠĠĠĠĠ Ġval Ġgrand son Ġ= Ġson . right () ĊĠĠĠĠĠĠĠ Ġgrand . left Ġ= Ġgrand son ĊĠĠĠĠĠĠĠ Ġson . right Ġ= Ġgrand ĊĠĠĠĠĠĠĠ Ġafter Rotate ( grand , Ġson , Ġgrand son ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġafter Rotate ( grand : ĠA VL Node < E >, Ġson : ĠA VL Node < E >, Ġgrand son : ĠA VL Node < E > ?) Ġ{ ĊĠĠĠĠĠĠĠ Ġson . parent Ġ= Ġgrand . parent () ĊĠĠĠĠĠĠĠ Ġif Ġ( grand . is Left Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrand . parent ?. left Ġ= Ġson ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġif Ġ( grand . is Right Child ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġgrand . parent ?. right Ġ= Ġson ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġroot Ġ= Ġson ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġgrand son ?. parent Ġ= Ġgrand ĊĠĠĠĠĠĠĠ Ġgrand . parent Ġ= Ġson ĊĊĠĠĠĠĠĠĠ Ġgrand . update Height () ĊĠĠĠĠĠĠĠ Ġson . update Height () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun Ġcreate Node ( item : ĠE , Ġparent : ĠBase Node < E >? ): ĠBase Node < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠA VL Node ( item , Ġparent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġclass ĠA VL Node < E >( item : ĠE , Ġparent : ĠBase Node < E > ?) Ġ: ĠBase Node < E >( item , Ġparent ) Ġ{ ĊĊĠĠĠĠĠĠĠ Ġvar Ġheight Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprivate Ġset ĊĊĠĠĠĠĠĠĠ Ġval Ġbalance Factor : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġleft Height Ġ- Ġright Height ĊĊĠĠĠĠĠĠĠ Ġval Ġis Bal anced : ĠBoolean ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġabs ( balance Factor ) Ġ<= Ġ 1 ĊĊĠĠĠĠĠĠĠ Ġval Ġt aller Child : ĠA VL Node < E >? ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Height Ġ> Ġright Height ) Ġreturn Ġcast ( left ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( left Height Ġ< Ġright Height ) Ġreturn Ġcast ( right ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( is Left Child ) Ġcast ( left ) Ġelse Ġcast ( right ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġleft Height : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġcast ( left )?. height Ġ?: Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġval Ġright Height : ĠInt ĊĠĠĠĠĠĠĠĠĠĠĠ Ġget () Ġ= Ġcast ( right )?. height Ġ?: Ġ 0 ĊĊĠĠĠĠĠĠĠ Ġfun Ġupdate Height () Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġheight Ġ= Ġ 1 Ġ+ Ġmax ( left Height , Ġright Height ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġparent (): ĠA VL Node < E >? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcast ( parent ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġleft (): ĠA VL Node < E >? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcast ( left ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfun Ġright (): ĠA VL Node < E >? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġcast ( right ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprivate Ġfun Ġcast ( node : ĠBase Node < E >? ): ĠA VL Node < E >? Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnode Ġas ? ĠA VL Node < E > ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }