国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質(zhì)的職業(yè)教育機構(gòu)

手機站
千鋒教育

千鋒學(xué)習(xí)站 | 隨時隨地免費學(xué)

千鋒教育

掃一掃進入千鋒手機站

領(lǐng)取全套視頻
千鋒教育

關(guān)注千鋒學(xué)習(xí)站小程序
隨時隨地免費學(xué)習(xí)課程

當(dāng)前位置:首頁  >  技術(shù)干貨  > 寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別是什么?

寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別是什么?

來源:千鋒教育
發(fā)布人:xqq
時間: 2023-10-11 07:43:10 1696981390

一、寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別

寫時拷貝與可持久化數(shù)據(jù)結(jié)構(gòu)的區(qū)別是可持久化:將數(shù)據(jù)結(jié)構(gòu)的所有歷史版本記錄下來,稱為可持久化。不是所有的數(shù)據(jù)結(jié)構(gòu)都是可以持久化的,可持久化的數(shù)據(jù)結(jié)構(gòu)要求其結(jié)構(gòu)穩(wěn)定,比如堆(是一顆滿二叉樹,結(jié)構(gòu)穩(wěn)定)、樹狀數(shù)組、trie(字典樹)、線段樹等。平衡樹就不可以進行持久化操作,因為其存在左旋、右旋的操作。

存下來所有的歷史版本有兩種方式,一種是每改動一次則全部備份下來;另一種是增量備份。名列前茅種方式時空復(fù)雜度都比較高,不使用這種方式,我們這里只講解增量備份的方式(類似于git)。

增量備份的核心思想是:只記錄每個版本與前一個版本不同的部分。

可持久化Trie的用途:

正常的Trie樹可以解決字符串的一些問題,特殊的Trie樹(比如0/1Trie)可以解決最大異或和的相關(guān)問題,但是如果每次的詢問是針對區(qū)間的,Trie樹就不好解決,因為你不能對每個區(qū)間都建一棵Trie樹,那樣空間就會爆炸,于是,我們的可持久化Trie就登場了。

延伸閱讀:

二、可持久化Trie的構(gòu)造

設(shè)trie[x][ch],表示從x號節(jié)點連向的字符為ch的點的編號(與普通Trie的含義相同),root[i]表示第i次插入的字符串的根節(jié)點,tot代表總節(jié)點數(shù)

可持久化Trie插入第i個字符串的構(gòu)造流程如下:

1:首先新建第i個字符串的根節(jié)點,并定義兩個變量p,q代表當(dāng)前串的節(jié)點和上一個版本與之對應(yīng)的節(jié)點,初始化p=root[i-1],q=root[i]

2:若當(dāng)前字符串的下一個字符是ch,那么就讓trie[q][ch]=++tot;

然后對于不是ch的字符CH,trie[q][CH]=trie[p][CH];

3:讓p=trie[p][ch],q=trie[q][ch],并重復(fù)2,3,步直到建樹完成。

聲明:本站稿件版權(quán)均屬千鋒教育所有,未經(jīng)許可不得擅自轉(zhuǎn)載。
10年以上業(yè)內(nèi)強師集結(jié),手把手帶你蛻變精英
請您保持通訊暢通,專屬學(xué)習(xí)老師24小時內(nèi)將與您1V1溝通
免費領(lǐng)取
今日已有369人領(lǐng)取成功
劉同學(xué) 138****2860 剛剛成功領(lǐng)取
王同學(xué) 131****2015 剛剛成功領(lǐng)取
張同學(xué) 133****4652 剛剛成功領(lǐng)取
李同學(xué) 135****8607 剛剛成功領(lǐng)取
楊同學(xué) 132****5667 剛剛成功領(lǐng)取
岳同學(xué) 134****6652 剛剛成功領(lǐng)取
梁同學(xué) 157****2950 剛剛成功領(lǐng)取
劉同學(xué) 189****1015 剛剛成功領(lǐng)取
張同學(xué) 155****4678 剛剛成功領(lǐng)取
鄒同學(xué) 139****2907 剛剛成功領(lǐng)取
董同學(xué) 138****2867 剛剛成功領(lǐng)取
周同學(xué) 136****3602 剛剛成功領(lǐng)取
相關(guān)推薦HOT
什么是樹的特殊類問題?

一、什么是樹的特殊類問題1、二叉樹的特殊類問題二叉樹是一種特殊的樹結(jié)構(gòu),每個節(jié)點非常多只能有兩個子節(jié)點。二叉樹的特殊類問題包括二叉樹的...詳情>>

2023-10-11 09:24:55
數(shù)據(jù)結(jié)構(gòu)里的間界疊加是什么意思?

一、數(shù)據(jù)結(jié)構(gòu)里的間界疊加數(shù)據(jù)結(jié)構(gòu)里的間界疊加是間界疊加:從一端到另一端沿各部分分界來回折疊后,最后一位對齊相加。如:key=2534635870三位...詳情>>

2023-10-11 09:22:37
軟件架構(gòu)如何能夠滿足ASPICE流程?

一、軟件架構(gòu)如何能夠滿足ASPICE流程架構(gòu)的用途是把整個產(chǎn)品劃分為更為細節(jié)的板塊:軟件、硬件、通信等。在這個基礎(chǔ)上軟件整體將按照用途、功能...詳情>>

2023-10-11 08:47:00
紅黑樹為什么叫紅黑樹?

一、紅黑樹叫紅黑樹的原因紅黑樹(Red-Black Tree)是一種自平衡的二叉搜索樹(Binary Search Tree),其在插入和刪除操作時能夠自動調(diào)整樹的結(jié)...詳情>>

2023-10-11 08:42:41
為什么數(shù)組索引數(shù)據(jù)那么快速、有效?

一、數(shù)組索引數(shù)據(jù)快速、有效的原因1、連續(xù)內(nèi)存存儲數(shù)組在內(nèi)存中是連續(xù)存儲的,數(shù)組的元素在內(nèi)存中按照一定的順序排列,相鄰元素之間沒有間隔。...詳情>>

2023-10-11 08:36:19
快速通道