procedure search (xintegervar pnodevar hboolean)var node(adens _avltrees *begin (*~ *if nil then (*insert*new( ) key :xp count : left :nilp right :nilp bal : :trueelsif key then search(xp lefth)if then (*left branch has grown*if bal then bal : :false elsif bal then bal :- else (*bal - rebalance* : leftif bal - then (*single ll rotation* left : rightp right :pp bal : : else (*double lr rotation* : rightp right : leftp left : left : rightp right :pif bal - then bal : else bal : endif bal + then bal :- else bal : endp : endp bal : :false end end elsif key then search(xp righth)if then (*right branch has grown*if bal - then bal : :false elsif bal then bal : else (*bal + rebalance* : rightif bal then (*sinlge rr rotation* right : leftp left :pp bal : : else (*double rl rotation* : leftp left : rightp right : right : leftp left :pif bal + then bal :- else bal : endif bal - then bal : else bal : endp : endp bal : :false end end else inc( countend end search two particularly interesting questions concerning the performance of the balanced tree insertion algorithm are the following