1つのポインタに複数の高速レーンを含むリストをスキップする

私は実際にどこに投稿するべきかわからない/これを尋ねるので、私はこれが場所かもしれないと考えました。

I came out with an idea of different implementation of a Skip
List. This is how default Skip List is defined Skip List

私たちは主に、空間の複雑さよりも時間の複雑さを気にします。上記のリンクをクリックすると、Skip
Listの平均と最悪の時間と空間の複雑さについて読むことができます。スキップリストに1つ以上の「急行」レーンがある場合があります。別の高速レーンを追加することで、各ノードに別のポインタが必要となるため、より多くのスペースを割り当てる必要があります。

通常のONE-WAYリンクリストは次のように定義されています:

class LinkedList{
  int value;
  LinkedList next;  
}

単純なONE-WAYスキップリストは次のように定義されます:

class SkipList{  
  int value;  
  SkipList next;  
  SkipList lane_1;  
  ...  
  SkipList lane_n;  
}  

私たちの車線が増えるほど、必要なポインタが増えることが分かります。
lane_nポインタがなければ、スキップリストはリンクされたリストにすぎません。

通常のONE-WAY 3エクスプレスレーンの実装は、次のようになります。

class SkipList{
  int value;  
  SkipList next;  
  SkipList lane_1;  
  SkipList lane_2;  
  SkipList lane_3;  
}      

私の考えは:
我々は4つのポインタを実装する3つの高速レーンを持つことを選択します。しかし、我々は2つのポインタといくつかのルールでそれを行うでしょう。

最高速のレーンでスキップするノードの数を選択する必要があります。
その後、私たちはこのルールに従います:より低速の高速レーンごとに、上の高速レーンのスキップされたノードの数をとり、それらを2で割ります。例:

LANE 3:s3 = 20;
LANE 2:s2 = s3/2 = 10;
LANE 1:s1 = s2/2 = 5;
LANE 0:s0 = 1 =リンクリスト

今度は新しいSkip Listを定義します:

class SkipList{
  int value;
  SkipList next;
  SkipList lane;
}

今度は、このルールで3つの高速レーンを1つにまとめます: 遅い高速レーンは次のノードから始まります。

node_0.next = node_1
node_0.lane = node_20
node_1.next = node_2
node_1.lane = node_11(理由は2番目のノードからレーン2が始まり、10をスキップするためです)
node_2.next = node_3
node_2.lane = node_7(理由は?レーン1は3番目のノードから始まり、5をスキップするためです)

それはどのように見えるはずです写真がここにあります:

One lane Skip List

要約:
lane_3がnode_0から始まり、20:0,20,40,60、…をスキップすると
lane_2がnode_1から開始し、10:1,11,21,31,41,51,61をスキップすると、

lane_1がnode_2から開始し、5:2,7,12,17,22,27,32,37,42,47,52,57,62、…をスキップすると

レーンは決して会うことはありませんが、それを行うにはポインタが1つしかありません。
少し時間をかけてスペースを節約します。遅い車線に飛ぶにはO(1)が必要です。

これはどんな使い方ですか?あなたの意見を聞きたい。ありがとう。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です