AVL木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
AVL木

AVL木(えーぶいえるき、AVL tree、Adelson-Velskii and Landis' tree)は、コンピュータプログラムにおけるデータ構造、特に木構造の一つ。AVL木平衡条件を満たす平衡2分探索木である。左右の部分木の高さの差を多くとも1にする。

このAVL木を平衡2分木と呼ぶことがあるが、平衡2分探索木と混同して使用されることが多い。

AVLとは、1962年に論文を発表したソ連の数学者、ゲオルギー・アデルソン・ヴェルスキー英語版エフゲニー・ランディス英語版の名に由来する。

AVL木平衡条件[編集]

  1. 2つの子をもつ各節点について、左部分木の高さと右部分木の高さが高々1しか異ならない。
  2. 1つの子しかもたない各節点について、その子は葉である。

関連項目[編集]