AVL木
子ノードがない場合は部分木の高さを0と考えるため、1つの子ノードしか持たないノードについて、その子ノードは葉ノードとなる。すなわち、兄弟ノードを持たないノードは必ず葉ノードである。
AVL木のどの部分木もAVL木である。
AVL木は、あくまで各ノードの左右部分木の高さのバランスを保った木であり、各葉ノードの深さが均等な木というわけではない。深さが最も大きい葉ノードと最も小さい葉ノードの深さの差が2以上になって、完全二分木とはかけ離れた構造になることもある。
挿入や削除の操作は、毎回平衡条件の判定を伴うため比較的コストが掛かる。そのため、これらの操作が探索に比べてあまりにも頻繁に行われるような環境では、AVL木は性能を発揮しにくい。
AVL木は、同じく平衡二分探索木の1つである赤黒木に比べて平衡性をより厳密に維持するので、探索性能はAVL木の方がよいが、挿入や削除の性能は赤黒木の方がよい。