Editing AVL tree (section)

===Searching===
Searching for a specific key in an AVL tree can be done the same way as that of any balanced or unbalanced [[Binary search tree#Searching|binary search tree]].<ref name="dixit-mastering-data-structures">{{Cite book |last=Dixit |first=J. B. |title=Mastering data structures through 'C' language |publisher=University Science Press, an imprint of Laxmi Publications Pvt. Ltd. |year=2010 |isbn=9789380386720 |location=New Delhi, India |oclc=939446542}}</ref>{{rp|ch. 8}} In order for search to work effectively it has to employ a comparison function which establishes a [[total order]] (or at least a [[Weak ordering#Total preorders|total preorder]]) on the set of keys.<ref name="brass-advanced-data-structures">{{Cite book |last=Brass |first=Peter |title=Advanced data structures |date=2008 |publisher=Cambridge University Press |isbn=9780511438202 |location=Cambridge |oclc=312435417}}</ref>{{rp|23}} The number of comparisons required for successful search is limited by the height {{math|''h''}} and for unsuccessful search is very close to {{math|''h''}}, so both are in {{math|O(log ''n'')}}.<ref name="hubbard-outline-theory-problems">{{Cite book |last=Hubbard |first=John Rast |url=https://archive.org/details/schaumsoutlineof0000hubb |title=Schaum's outline of theory and problems of data structures with Java |date=2000 |publisher=McGraw-Hill |isbn=0071378707 |location=New York |oclc=48139308 |url-access=registration}}</ref>{{rp|216}}