BST / AVL木ビジュアライザー
値を挿入して木が成長する様子を見てみましょう。AVLモードに切り替えると自動的な再平衡が見られます。
Logarithmic Efficiency in Tree Structures 🖖
Binary Search Trees mandate a strict hierarchical organization, ensuring left-child nodes hold lesser values. AVL trees enhance this by algorithmically enforcing a maximum height differential of one between subtrees. This mathematical self-balancing requires precise rotational transformations upon insertion or deletion. Such structural constraints guarantee search, insertion, and deletion operations remain bounded by O(log n) time complexity, optimizing rapid data retrieval.
各ステップで半分を捨てる 🖖
二分探索木は辞書で単語を引く作業に似ています。各ノードで値を比較し、あなたの値を含みえない側の半分をまるごと捨てるのです。だからよく整った木なら、100万件の中から目的の値をおよそ20回の比較で見つけられます。ただし木の形は挿入順で決まります。すでにソート済みの値(10, 20, 30, …)を入れてみると、木が一本の傾いた線に崩れ、リストを一つずつ調べるのと同じ速さになってしまいます。
AVL木に潜む黄金比 🖖
AVLモードに切り替えて、こう問うてみましょう。ノード数を決めたとき、バランスの取れた木はどこまで高くなれるのか。その答えには黄金比が隠れています。各高さで最も節点の少ない正当なAVL木はフィボナッチ木で、二つの小さなフィボナッチ木から作られるため、その節点数はフィボナッチ数列に従います。だからこそ高さの上界には定数 1.44 が現れます。これはまさに 1 / log₂(φ) であり、φ ≈ 1.618、すなわち黄金比です。