空のサブツリーを1つ持つバイナリツリーをバランスの取れたバイナリツリーにすることはできますか？もしそうなら、いつ？

Question

平衡二分木は、任意のノードの2つのサブツリーの高さが2つ以上異なることのないような木であると定義される。

私の質問は、サブツリーのいずれかが存在しないか、基本的にサブツリーが

Answer 1

空のサブツリーカウントNULLである場合は、1つのサブツリーが空の場合は長さ0のように、他のサブツリーは、深さ0を持っているか、しなければならないものです1.例えばこれらは平衡ツリー：

A   A 
/\  /\ 
    B 

これはない：

A 
/\ 
    B 
    /\ 
    C D 

(B(C,D))の右サブツリーは深さ2を有しているので、左の部分木は、深さ0

を有しています(B(C,D))サブツリー自体はバランスが取れていますが、そのツリー全体には含まれていません。