AVL木かどうかの判定について

Question

AVL木についての質問です。

AVL木ってどのノードの左右部分木の高さも1以下のものを指すと思うんですが、その定義でいくと上の画像のようなものもAVL木と見なして良いのでしょうか？

こうなってくるとあまりバランスが良いとは言えないため、b-treeとかが生まれてきた感じなんですかね？

各ノードについて左右の部分木の高さを記入すると上の画像のようになって、高さの差はどれも1以下になっているような気がするのですがどうでしょうか。

Answer 1

すべてのノードについて左右の高さの差が1以下でなければなりません。その図では根のすぐ右側のノードなど満たしてないものがあるのでAVL木として成立していません。

Comments

[takuyaKK]

自分が認識している各ノードの部分木の左右の高さを、追記したのですが僕の認識はどこが間違ってますでしょうか？

[yudedako67]

図の中で丸で書かれているものすべてがノードです。今数字が書かれていないようなノードでも、左右どちらかの子が無い場合には高さ0の部分木とみなして条件を満たされるようにしなければなりませ。

[takuyaKK]

なるほど、確かにそうですね！ありがとうございます