Nhảy biểu

Nhảy biểu (Skip List) là từ William Pugh phát minh một loại tra tìm số liệu kết cấu, duy trì đối số liệu nhanh chóng tra tìm, cắm vào cùng xóa bỏ.

Nhảy biểu kỳ vọng không gian phức tạp độ vì,Nhảy biểu tuần tra, cắm vào cùng xóa bỏ thao tác kỳ vọng thời gian phức tạp độ đều vì $O(\log n)$ .

Cơ bản tư tưởng

Xem tên đoán nghĩa, nhảy biểu là một loại cùng loại với liên biểu số liệu kết cấu. Càng thêm chính xác ra, nhảy biểu là đối có tự liên biểu cải tiến.

Vì phương tiện thảo luận, kế tiếp sở hữu có tự liên biểu cam chịu vìThăng tựBài tự.

Một cái có tự liên biểu tra tìm thao tác, chính là từ đầu bộ bắt đầu từng cái tương đối, thẳng đến trước mặt tiết điểm giá trị lớn hơn hoặc là tương đương mục tiêu tiết điểm giá trị. Thực rõ ràng, cái này thao tác phức tạp độ là.

Nhảy biểu ở có tự liên biểu cơ sở thượng, dẫn vàoPhân tầngKhái niệm. Đầu tiên, nhảy biểu mỗi một tầng đều là một cái có tự liên biểu, đặc biệt mà, tầng chót nhất là mới bắt đầu có tự liên biểu. Mỗi cái ở vào đệTầng tiết điểm cóXác suất xuất hiện ở đệTầng,Vì hằng số.

Ghi tạc n cái tiết điểm nhảy biểu trung, kỳ vọng bao hàm $\frac{1}{p}$ Cái nguyên tố tầng vì đệTầng, dễ đến $L(n) = \log_{\frac{1}{p}}n$ .

Ở nhảy biểu trung tra tìm, chính là từ đệTầng bắt đầu, trình độ mà từng cái tương đối cho đến trước mặt tiết điểm tiếp theo cái tiết điểm lớn hơn hoặc bằng mục tiêu tiết điểm, sau đó di động đến tiếp theo tầng. Lặp lại cái này quá trình cho đến tới tầng thứ nhất thả vô pháp tiếp tục tiến hành thao tác. Lúc này, nếu tiếp theo cái tiết điểm là mục tiêu tiết điểm, tắc thành công tra tìm; ngược lại, tắc nguyên tố không tồn tại. Cứ như vậy, tra tìm trong quá trình sẽ nhảy qua một ít không cần phải tương đối, cho nên so với có tự liên biểu tuần tra, nhảy biểu tuần tra càng mau. Có thể chứng minh, nhảy biểu tuần tra bình quân phức tạp độ vì $O(\log n)$ .

Phức tạp độ chứng minh

Không gian phức tạp độ

Đối với một cái tiết điểm mà nói, tiết điểm tối cao tầng số vìXác suất vì $p^{i-1}(1 - p)$ .Cho nên, nhảy biểu kỳ vọng tầng số vì $\sum_{i>=1} ip^{i - 1}(1-p) = \frac{1}{1 - p}$ ,Thả bởi vìVì hằng số, cho nên nhảy biểuKỳ vọng không gian phức tạp độVì.

Ở nhất hư dưới tình huống, mỗi một tầng có tự liên biểu tương đương mới bắt đầu có tự liên biểu, tức nhảy biểuKém cỏi nhất không gian phức tạp độVì $O(n \log n)$ .

Thời gian phức tạp độ

Từ sau về phía trước phân tích tra tìm đường nhỏ, cái này quá trình có thể chia làm từ tầng chót nhất bò đến đệTầng cùng kế tiếp thao tác hai cái bộ phận. Ở phân tích khi, giả thiết một cái tiết điểm cụ thể tin tức ở nó bị phỏng vấn phía trước là không biết.

Giả thiết trước mặt chúng ta ở vào một cái đệTầng tiết điểm,Chúng ta cũng không biếtLớn nhất tầng số cùngBên trái tiết điểm lớn nhất tầng số, chỉ biếtLớn nhất tầng số ít nhất vì.NếuLớn nhất tầng số lớn hơn,Như vậy bước tiếp theo hẳn là hướng về phía trước đi, loại tình huống này xác suất vì;NếuLớn nhất tầng số tương đương,Như vậy bước tiếp theo hẳn là hướng tả đi, loại tình huống này xác suất vì.

LệnhVì ở một cái vô hạn chiều dài nhảy biểu trung hướng về phía trước bòTầng kỳ vọng đại giới, như vậy có:

\begin{aligned} C(0) & = 0 \\ C(i) & = (1-p)(1+C(i)) + p(1+C(i-1)) \end{aligned}

Giải đến $C(i)=\frac{i}{p}$ .

Bởi vậy có thể đến ra: Ở chiều dài vìNhảy biểu trung, từ tầng chót nhất bò đến đệTầng kỳ vọng bước số tồn tại thượng giới $\frac{L(n) - 1}{p}$ .

Hiện tại chỉ cần phân tích bò đến đệTầng sau còn muốn lại đi nhiều ít bước. Dễ đến, tới rồi đệTầng sau, hướng tả đi bước số sẽ không vượt qua đệTầng cập càng cao tầng tiết điểm số tổng hoà, mà cái này tổng hoà kỳ vọng vì $\frac{1}{p}$ .Cho nên tới rồi đệTầng sau hướng tả đi kỳ vọng bước số tồn tại thượng giới $\frac{1}{p}$ .Cùng lý, tới rồi đệTầng sau hướng về phía trước đi kỳ vọng bước số tồn tại thượng giới $\frac{1}{p}$ .

Cho nên, nhảy biểu tuần tra kỳ vọng tra tìm bước số vì $\frac{L(n) - 1}{p} + \frac{2}{p}$ ,Lại bởi vì $L(n)=\log_{\frac{1}{p}}n$ ,Cho nên nhảy biểu tuần traKỳ vọng thời gian phức tạp độVì $O(\log n)$ .

Ở nhất hư dưới tình huống, mỗi một tầng có tự liên biểu tương đương mới bắt đầu có tự liên biểu, tra tìm quá trình tương đương với đối tối cao tầng có tự liên biểu tiến hành tuần tra, tức nhảy biểu tuần tra thao tácKém cỏi nhất thời gian phức tạp độVì.

Cắm vào thao tác cùng xóa bỏ thao tác chính là tiến hành một lần tuần tra quá trình, trên đường ký lục yêu cầu sửa chữa tiết điểm, cuối cùng hoàn thành sửa chữa. Dễ đến mỗi một tầng nhiều nhất chỉ cần sửa chữa một cái tiết điểm, lại bởi vì nhảy biểu kỳ vọng tầng số vì $\log_{\frac{1}{p}}n$ ,Cho nên cắm vào cùng sửa chữaKỳ vọng thời gian phức tạp độCũng vì $O(\log n)$ .

Cụ thể thực hiện

Thu hoạch tiết điểm lớn nhất tầng số

Bắt chước lấyXác suất hướng lên trên thêm một tầng, cuối cùng cùng hạn mức cao nhất giá trị lấy nhỏ nhất.

intrandomLevel(){
intlv=1;
// MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4
while((rand()&S)PS)++lv;
returnmin(MAXL,lv);
}

Tuần tra

Tuần tra nhảy biểu trung hay không tồn tại kiện giá trị vìkeyTiết điểm. Cụ thể thực hiện khi, có thể thiết trí hai cái lính gác tiết điểm lấy giảm bớt biên giới điều kiện thảo luận.

V&find(constK&key){
SkipListNodeK,V>*p=head;

// tìm được nên tầng cuối cùng một cái kiện giá trị nhỏ hơn key tiết điểm, sau đó đi hướng tiếp theo tầng
for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
}
// hiện tại là nhỏ hơn, cho nên còn cần lại sau này đi một bước
p=p->forward[0];

// thành công tìm được tiết điểm
if(p->key==key)returnp->value;

// tiết điểm không tồn tại, phản hồi INVALID
returntail->value;
}

Cắm vào

Cắm vào tiết điểm(key, value).Cắm vào tiết điểm quá trình chính là trước chấp hành một lần tuần tra quá trình, trên đường ký lục tân tiết điểm là muốn cắm vào nào một ít tiết điểm mặt sau, cuối cùng lại chấp hành cắm vào. Mỗi một tầng cuối cùng một cái kiện giá trị nhỏ hơnkeyTiết điểm, chính là yêu cầu tiến hành sửa chữa tiết điểm.

voidinsert(constK&key,constV&value){
// dùng cho ký lục yêu cầu sửa chữa tiết điểm
SkipListNodeK,V>*update[MAXL+1];

SkipListNodeK,V>*p=head;
for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
// đệ i tầng yêu cầu sửa chữa tiết điểm vì p
update[i]=p;
}
p=p->forward[0];

// nếu đã tồn tại tắc sửa chữa
if(p->key==key){
p->value=value;
return;
}

// thu hoạch tân tiết điểm lớn nhất tầng số
intlv=randomLevel();
if(lv>level){
lv=++level;
update[lv]=head;
}

// tân kiến tiết điểm
SkipListNodeK,V>*newNode=newSkipListNodeK,V>(key,value,lv);
// ở đệ 0~lv tầng cắm vào tân tiết điểm
for(inti=lv;i>=0;--i){
p=update[i];
newNode->forward[i]=p->forward[i];
p->forward[i]=newNode;
}

++length;
}

Xóa bỏ

Xóa bỏ kiện giá trị vìkeyTiết điểm. Xóa bỏ tiết điểm quá trình chính là trước chấp hành một lần tuần tra quá trình, trên đường ký lục muốn xóa tiết điểm là ở đâu một ít tiết điểm mặt sau, cuối cùng lại chấp hành xóa bỏ. Mỗi một tầng cuối cùng một cái kiện giá trị nhỏ hơnkeyTiết điểm, chính là yêu cầu tiến hành sửa chữa tiết điểm.

boolerase(constK&key){
// dùng cho ký lục yêu cầu sửa chữa tiết điểm
SkipListNodeK,V>*update[MAXL+1];

SkipListNodeK,V>*p=head;
for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
// đệ i tầng yêu cầu sửa chữa tiết điểm vì p
update[i]=p;
}
p=p->forward[0];

// tiết điểm không tồn tại
if(p->key!=key)returnfalse;

// từ tầng chót nhất bắt đầu xóa bỏ
for(inti=0;ilevel;++i){
// nếu tầng này không có p xóa bỏ liền hoàn thành
if(update[i]->forward[i]!=p){
break;
}
// tách ra p liên tiếp
update[i]->forward[i]=p->forward[i];
}

// thu về không gian
deletep;

// xóa bỏ tiết điểm khả năng dẫn tới lớn nhất tầng số giảm bớt
while(level>0&&head->forward[level]==tail)--level;

// nhảy biểu chiều dài
--length;
returntrue;
}

Hoàn chỉnh số hiệu

Dưới đây số hiệu là dùng nhảy biểu thực hiện map. Chưa kinh đứng đắn thí nghiệm, chỉ cung tham khảo.

Tham khảo số hiệu

#include&LTbits/stdc++.h>
usingnamespacestd;

templatetypenameK,typenameV>
structSkipListNode{
intlevel;
Kkey;
Vvalue;
SkipListNode**forward;

SkipListNode(){}

SkipListNode(Kk,Vv,intl,SkipListNode*nxt=NULL){
key=k;
value=v;
level=l;
forward=newSkipListNode*[l+1];
for(inti=0;il;++i)forward[i]=nxt;
}

~SkipListNode(){
if(forward!=NULL)delete[]forward;
}
};

templatetypenameK,typenameV>
structSkipList{
staticconstintMAXL=32;
staticconstintP=4;
staticconstintS=0xFFFF;
staticconstintPS=S/P;
staticconstintINVALID=INT_MAX;

SkipListNodeK,V>*head,*tail;
intlength;
intlevel;

SkipList(){
srand(time(0));

level=length=0;
tail=newSkipListNodeK,V>(INVALID,0,0);
head=newSkipListNodeK,V>(INVALID,0,MAXL,tail);
}

~SkipList(){
deletehead;
deletetail;
}

intrandomLevel(){
intlv=1;
while((rand()&S)PS)++lv;
returnMAXL>lv?lv:MAXL;
}

voidinsert(constK&key,constV&value){
SkipListNodeK,V>*update[MAXL+1];

SkipListNodeK,V>*p=head;
for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
update[i]=p;
}
p=p->forward[0];

if(p->key==key){
p->value=value;
return;
}

intlv=randomLevel();
if(lv>level){
lv=++level;
update[lv]=head;
}

SkipListNodeK,V>*newNode=newSkipListNodeK,V>(key,value,lv);
for(inti=lv;i>=0;--i){
p=update[i];
newNode->forward[i]=p->forward[i];
p->forward[i]=newNode;
}

++length;
}

boolerase(constK&key){
SkipListNodeK,V>*update[MAXL+1];
SkipListNodeK,V>*p=head;

for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
update[i]=p;
}
p=p->forward[0];

if(p->key!=key)returnfalse;

for(inti=0;ilevel;++i){
if(update[i]->forward[i]!=p){
break;
}
update[i]->forward[i]=p->forward[i];
}

deletep;

while(level>0&&head->forward[level]==tail)--level;
--length;
returntrue;
}

V&operator[](constK&key){
Vv=find(key);
if(v==tail->value)insert(key,0);
returnfind(key);
}

V&find(constK&key){
SkipListNodeK,V>*p=head;
for(inti=level;i>=0;--i){
while(p->forward[i]->keykey){
p=p->forward[i];
}
}
p=p->forward[0];
if(p->key==key)returnp->value;
returntail->value;
}

boolcount(constK&key){returnfind(key)!=tail->value;}
};

intmain(){
SkipListint,int>L;
mapint,int>M;

clock_ts=clock();

for(inti=0;i1e5;++i){
intkey=rand(),value=rand();
L[key]=value;
M[key]=value;
}

for(inti=0;i1e5;++i){
intkey=rand();
if(i&1){
L.erase(key);
M.erase(key);
}else{
intr1=L.count(key)?L[key]:0;
intr2=M.count(key)?M[key]:0;
assert(r1==r2);
}
}

clock_te=clock();
cout"Time elapsed:"(double)(e-s)/CLOCKS_PER_SECendl;
// about 0.2s

return0;
}

Nhảy biểu tùy cơ phỏng vấn ưu hoá

Phỏng vấn nhảy biểu trung đệCái tiết điểm, tương đương với phỏng vấn mới bắt đầu có tự liên biểu trung đệCái tiết điểm, thực rõ ràng cái này thao tác thời gian phức tạp độ là,Cũng không cũng đủ ưu tú.

Nhảy biểu tùy cơ phỏng vấn ưu hoá chính là đối mỗi một cái trước hướng kim đồng hồ, lại nhiều giữ gìn cái này trước hướng kim đồng hồ chiều dài. Giả thiếtCùngĐều là nhảy biểu trung tiết điểm, trong đóVì nhảy biểu đệCái tiết điểm,Vì nhảy biểu đệCái tiết điểm,Thả ở nhảy biểu mỗ một tầng trungTrước hướng kim đồng hồ chỉ hướng,Như vậy cái này trước hướng kim đồng hồ chiều dài vì.

Hiện tại phỏng vấn nhảy biểu trung đệCái tiết điểm, liền có thể từ đỉnh tầng bắt đầu, trình độ mà biến lịch nên tầng liên biểu, thẳng đến trước mặt tiết điểm vị trí hơn nữa trước mặt tiết điểm ở nên tầng trước hướng kim đồng hồ chiều dài lớn hơn hoặc bằng,Sau đó di động đến tiếp theo tầng. Lặp lại cái này quá trình cho đến tới tầng thứ nhất thả vô pháp tiếp tục hành thao tác. Lúc này, trước mặt tiết điểm chính là nhảy biểu trung đệCái tiết điểm.

Như vậy, liền có thể nhanh chóng mà phỏng vấn đến nhảy biểu đệCái nguyên tố. Có thể chứng minh, cái này thao tác thời gian phức tạp độ vì $O(\log n)$ .

Tham khảo tư liệu

Bổn giao diện gần nhất đổi mới:2023/5/6 19:22:00,Đổi mới lịch sử
Phát hiện sai lầm? Tưởng cùng nhau hoàn thiện?Ở GitHub thượng biên tập này trang!
Bổn giao diện cống hiến giả:Backl1ght,CookiePieWw,Enter-tainer,ksyx,Tiphereth-A,Xeonacid
Bổn giao diện toàn bộ nội dung ởCC BY-SA 4.0CùngSATAHiệp nghị chi điều khoản hạ cung cấp, phụ gia điều khoản cũng khả năng ứng dụng