درخت AVL (پاورپوینت)

درخت AVL

در ﺳﺎل ۱۹۶۲Adelson-Velskii و Landis ﺳﺎﺧﺘﺎر درﺧﺖ دودوﯾﯽ را ﻣﻌﺮﻓﯽ ﮐﺮدﻧﺪ ﮐﻪ ﺑﺮ ﺣﺴﺐ ارﺗﻔﺎع (ﻋﻤﻖ) زﯾﺮدرﺧﺘﺎن آن ﻣﺘﻌﺎدل ﺑﻮد.
ﯾﮏ درﺧﺖ دودوﯾﯽ ﺗﻬﯽ از ﻧﻈﺮ ارﺗﻔﺎع ﻣﺘﻌﺎدل اﺳﺖ . اﮔﺮ T ﯾﮏ درﺧﺖ دودوﯾﯽ ﻏﯿﺮﺗﻬﯽ ﺑﺎ زﯾﺮدرﺧﺘﺎن ﺳﻤﺖ ﭼﭗ و راﺳﺖ TL و TRﺑﺎﺷﺪ ،آﻧﮕﺎه Tﯾﮏ درﺧﺖ ﻣﺘﻌﺎدل از ﻧﻈﺮ ارﺗﻔﺎع اﺳﺖ اﮔﺮ و ﻓﻘﻂ اﮔﺮ:
۱) TL و TR از ﻧﻈﺮارﺗﻔﺎع ﻣﺘﻌﺎدل ﺑﻮده
۲) ۱=>|HL-HR| که در آن HL وHR به ترتیب TL و TR هستند.
ﺑﻪ ﺑﯿﺎن ﺳﺎده ﺗﺮ درﺧﺖ T از ﻧﻈﺮ ارﺗﻔﺎع ﻣﺘﻌﺎدل اﺳﺖ اﮔﺮ و ﻓﻘﻂ اﮔﺮ ﺗﻔﺎﺿﻞ ارﺗﻔﺎع زﯾﺮ درﺧﺖ ﭼﭗ و راﺳﺖ آن ﮐﻮﭼﺘﺮ ﯾﺎ ﻣﺴﺎوي ۱ ﺑﺎﺷﺪ و ﻫﻢ ﭼﻨﯿﻦ دو زﯾﺮدرﺧﺖ ﭼﭗ و راﺳﺖ آن ﻣﺘﻌﺎدل
درﺧﺖ AVL درﺧﺖ BSTاي اﺳﺖ ﮐﻪ ﻣﺘﻮازن ﺑﺎﺷﺪ.