एवीएल ट्री एक संतुलित बाइनरी सर्च ट्री है। पोस्ट ने बाइनरी सर्च ट्री पेश किया। बाइनरी ट्री के लिए खोज, सम्मिलन और विलोपन का समय पेड़ की ऊंचाई पर निर्भर करता है। सबसे खराब स्थिति में, ऊँचाई O(n) है। यदि कोई पेड़ पूरी तरह से संतुलित है-यानी, एक पूर्ण बाइनरी पेड़-तो उसकी ऊंचाई लॉग एन है। क्या हम एक पूर्णतः संतुलित वृक्ष बनाए रख सकते हैं? हां, लेकिन ऐसा करना महंगा पड़ेगा. समझौता एक अच्छी तरह से संतुलित पेड़ को बनाए रखने के लिए है- यानी, प्रत्येक नोड के दो उपपेड़ों की ऊंचाई लगभग समान है।

एवीएल पेड़ अच्छी तरह से संतुलित हैं। एवीएल पेड़ों का आविष्कार 1962 में दो रूसी कंप्यूटर वैज्ञानिकों, जी.एम. एडेलसन-वेल्स्की और ई.एम. लैंडिस (इसलिए इसका नाम एवीएल) द्वारा किया गया था। एवीएल वृक्ष में, प्रत्येक नोड के दो उपवृक्षों की ऊंचाई के बीच का अंतर 0 या 1 है। यह दिखाया जा सकता है कि AVL पेड़ की अधिकतम ऊंचाई O(log n) है।

एवीएल ट्री में किसी तत्व को सम्मिलित करने या हटाने की प्रक्रिया नियमित बाइनरी सर्च ट्री के समान ही है, सिवाय इसके कि आपको सम्मिलन या विलोपन ऑपरेशन के बाद ट्री को पुनर्संतुलित करना पड़ सकता है। एक नोड का संतुलन कारक उसके दाएं उपवृक्ष की ऊंचाई घटाकर उसके बाएं उपवृक्ष की ऊंचाई है। एक नोड को संतुलित कहा जाता है यदि इसका संतुलन कारक -1, 0, या 1 है। एक नोड को बाएं-भारी माना जाता है यदि इसका संतुलन कारक -1 है, और दाएं-भारी यदि इसका संतुलन कारक 1 है।