トピックの下でJavaのデータ構造を調べていSkip listたところ、次のことに遭遇しました。
のスキップ リストでは、とn nodesのそれぞれについて、ノードの位置·はノードの位置· ( )を指します。これは、図 3.17a に示すように、2 つおきのノードが 2 つ先のノードを指し、4 つおきのノードが 4 つ先のノードを指す、ということを意味します。これは、リストのノードに異なる数の参照フィールドを持たせることによって実現されます。ノードの半分には参照フィールドが 1 つだけあり、ノードの 4 分の 1 には 2 つの参照フィールドがあり、ノードの 8 分の 1 には 3 つの参照フィールドがあります。の上。参照フィールドの数は各ノードのレベルを示し、レベルの数は です。ki1 ≤ k ≤lg n1 ≤ i ≤
n/2k–1⎦ – 12k–1i2k–1i + 1maxLevel = ⎣lg n⎦ + 1
図は次のとおりです。(a) 等間隔のノードと (b) 等間隔の異なるレベルのノードを含むスキップ リスト。(c) 参照ノードが明確に示されているスキップ リスト。
私は数学的な部分を理解していません.sktipリストとは正確には何ですか?