Кездейсоқ екілік іздеу ағаштары және треап құрылымдары
Treap
Кездейсоқ екілік ағаш құрылымдары: Treap және рандомизацияланған ағаштар туралы ақпарат. Іздеу, енгізу, жою операцияларының жылдамдығы, логарифмдік уақыт.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Кездейсоқ іздеу ағашы дерек құрылымы
Random search tree data structure
Компьютер ғылымында, treap және кездейсоқ бинарлық іздеу ағашы – реттелген кілттердің динамикалық жиынтығын сақтайтын және кілттер арасында бинарлық іздеулерді жүзеге асыруға мүмкіндік беретін екілік іздеу ағашы дерек құрылымдарының өте жақын түрлері. Кілттерді енгізу және жоюдың кез келген тізбегінен кейін, ағаш пішіні кездейсоқ бинарлық ағашқа ұқсас ықтималдық таралымына ие кездейсоқ айнымалы болып табылады; атап айтқанда, жоғары ықтималдықпен оның биіктігі кілттер санының логарифміне пропорционал, сондықтан әрбір іздеу, енгізу немесе жою операциясы логарифмдік уақытты қажет етеді.
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.
Сипаттама
Ағашқа алғаш рет Раймунд Зайдель мен Сесилия Р. Арагон 1989 жылы сипаттаған; оның атауы «ағаш» және «үйінді» сөздерінің қосындысынан жасалған. Бұл – әрбір кілтке (кездейсоқ таңдалған) сандық басымдық берілген Картезиан ағашы. Кез келген екілік іздеу ағашы сияқты, түйіндерді баптау реті кілттердің сұрыпталған ретімен сәйкес келеді. Ағаштың құрылымы үйінділік ретке келу талабымен анықталады: яғни, жапырақ емес түйіннің басымдық саны оның ұрпақтарының басымдығынан үлкен немесе тең болуы керек. Осылайша, жалпы Картезиан ағаштарындағыдай, түбір түйін – ең жоғары басымдыққа ие түйін, ал оның сол және оң тармақтары сол түйіннің сол және оң жағындағы сұрыпталған тізбектерден бірдей қалыптасады. Трепті сипаттаудың тағы бір жолы – оны қайта теңгерместен, ең жоғары басымдыққа ие түйіндерді біртіндеп екілік іздеу ағашына енгізу арқылы құруға болады. Сондықтан, егер басымдықтар тәуелсіз кездейсоқ сандар болса (екі түйіннің бірдей басымдыққа ие болу ықтималдығы өте төмен болуын қамтамасыз ететін, жеткілікті кең мүмкіндіктер кеңістігінен алынған үлестірімнен), онда трептің пішіні кездейсоқ екілік іздеу ағашының пішінімен бірдей ықтималдық үлестіріміне ие, яғни түйіндерді кездейсоқ енгізу ретімен теңгерместен құрылған іздеу ағашы. Кездейсоқ екілік іздеу ағаштарының жоғары ықтималдылықпен логарифмдік биіктігі бар екендігі белгілі болғандықтан, трептер үшін де осы жағдай орынды. Бұл, жылдам сұрыптаудың күтілетін уақытта жұмыс істейтін екілік іздеу ағашының аргументін көрсетеді. Егер екілік іздеу ағаштары сұрыптаудың динамикалық мәселесіне шешім болса, онда трептер динамикалық жылдам сұрыптауға сәйкес келеді, онда басымдықтар півотты таңдауды басшылыққа алады. Арагон мен Зайдель жиі қол жеткізілетін түйіндерге жоғары басымдықтарды беруді ұсынады, мысалы, әр қол жеткізілу кезінде кездейсоқ санды таңдап, егер ол бұрынғы басымдықтан жоғары болса, түйіннің басымдығын сол санмен ауыстыру арқылы. Бұл өзгерту ағаштың кездейсоқ пішінін жоғалтуына әкелуі мүмкін; керісінше, жиі қол жеткізілетін түйіндер ағаш түбіріне жақын орналасуы мүмкін, осылайша оларды іздеу жылдамырақ болады. Наор мен Ниссим ашық кілтті криптожүйелерде авторизациялық сертификаттарды сақтауға арналған қолданылуын сипаттайды.
The treap was first described by Raimund Seidel and Cecilia R. Aragon in 1989; its name is a portmanteau of tree and heap. It is a Cartesian tree in which each key is given a (randomly chosen) numeric priority. As with any binary search tree, the inorder traversal order of the nodes is the same as the sorted order of the keys. The structure of the tree is determined by the requirement that it be heap ordered: that is, the priority number for any non leaf node must be greater than or equal to the priority of its children. Thus, as with Cartesian trees more generally, the root node is the maximum priority node, and its left and right subtrees are formed in the same manner from the subsequences of the sorted order to the left and right of that node. An equivalent way of describing the treap is that it could be formed by inserting the nodes highest priority first into a binary search tree without doing any rebalancing. Therefore, if the priorities are independent random numbers (from a distribution over a large enough space of possible priorities to ensure that two nodes are very unlikely to have the same priority) then the shape of a treap has the same probability distribution as the shape of a random binary search tree, a search tree formed by inserting the nodes without rebalancing in a randomly chosen insertion order. Because random binary search trees are known to have logarithmic height with high probability, the same is true for treaps. This mirrors the binary search tree argument that quicksort runs in expected time. If binary search trees are solutions to the dynamic problem version of sorting, then Treaps correspond specifically to dynamic quicksort where priorities guide pivot choices. Aragon and Seidel also suggest assigning higher priorities to frequently accessed nodes, for instance by a process that, on each access, chooses a random number and replaces the priority of the node with that number if it is higher than the previous priority. This modification would cause the tree to lose its random shape; instead, frequently accessed nodes would be more likely to be near the root of the tree, causing searches for them to be faster. Naor and Nissim describe an application in maintaining authorization certificates in public key cryptosystems.
Сырғанақ салу
Треп құру үшін біз жай ғана n мәнді трепке енгізе аламыз, мұндағы әрқайсысы уақытты қажет етеді. Сондықтан, треп мәндер тізімінен уақыт ішінде құрылуы мүмкін.
To build a treap we can simply insert n values in the treap where each takes time. Therefore a treap can be built in time from a list values.
Кездейсоқ екілік іздеу ағашы
Мартинес пен Рура Арагон мен Сейделдің treaps жұмысынан кейін енгізген кездейсоқ екілік іздеу ағашы, ағаш пішінінің бірдей кездейсоқ таралымымен бірдей түйіндерді сақтайды, бірақ ағаштың кездейсоқ құрылымын сақтау үшін түйіндердің ішінде әртүрлі ақпаратты ұстайды. Әр түйінде кездейсоқ басымдықтарды сақтаудың орнына, кездейсоқ екілік іздеу ағашы әрбір түйінде кішкентай бүтін санды сақтайды – оның ұрпақтарының санын (өзін біреу ретінде санап); бұл сандар ағаш айналу операциялары кезінде әр айналымға тек тұрақты уақыт қосымша жұмсау арқылы сақталуы мүмкін. Егер ағашта n түйін болса және x кілті енгізілсе, енгізу алгоритмі x-ті ағаштың жаңа түбірі ретінде орналастыру ықтималдығын 1/(n + 1) деп таңдайды, әйтпесе x-ті сол немесе оң тармаққа енгізу үшін енгізу процедурасын рекурсивті шақырады (кілті түбірден кіші немесе үлкен болуына байланысты). Ұрпақтардың саны алгоритмге әр қадамда кездейсоқ таңдаулар үшін қажетті ықтималдықтарды есептеуге көмектеседі. x-ті тармақтың түбіне орналастыру, оны жапыраққа енгізіп, содан кейін жоғары айналдыру арқылы немесе Мартинес пен Рура сипаттаған, тармақты жаңа түйіннің сол және оң балалары ретінде пайдалану үшін екі бөлікке бөлетін балама алгоритммен орындалуы мүмкін. Кездейсоқ екілік іздеу ағашының жою процедурасы енгізу процедурасы сияқты түйіндегі бірдей ақпаратты пайдаланады, бірақ енгізу процедурасынан айырмашылығы, ол жойылған түйіннің сол және оң балаларынан түсетін екі тармақты бір ағашқа біріктіру үшін орташа есеппен O(1) кездейсоқ шешімді ғана қажет етеді. Бұл себебі біріктірілетін тармақтардың тереңдігі орташа есеппен Θ(log n) құрайды; n және m өлшемді екі ағашты біріктіру үшін орташа есеппен Θ(log(n+m)) кездейсоқ таңдау қажет. Егер жойылған түйіннің сол немесе оң тармағы бос болса, біріктіру операциясы тривиальды болады; әйтпесе, жойылған түйіннің сол немесе оң баласы ұрпақтарының санына пропорционалды ықтималдықпен жаңа тармақтың түбірі ретінде таңдалады, ал біріктіру рекурсивті жалғасады.
The randomized binary search tree, introduced by Martínez and Roura subsequently to the work of Aragon and Seidel on treaps, stores the same nodes with the same random distribution of tree shape, but maintains different information within the nodes of the tree in order to maintain its randomized structure. Rather than storing random priorities on each node, the randomized binary search tree stores a small integer at each node, the number of its descendants (counting itself as one); these numbers may be maintained during tree rotation operations at only a constant additional amount of time per rotation. When a key x is to be inserted into a tree that already has n nodes, the insertion algorithm chooses with probability 1/(n + 1) to place x as the new root of the tree, and otherwise, it calls the insertion procedure recursively to insert x within the left or right subtree (depending on whether its key is less than or greater than the root). The numbers of descendants are used by the algorithm to calculate the necessary probabilities for the random choices at each step. Placing x at the root of a subtree may be performed either as in the treap by inserting it at a leaf and then rotating it upwards, or by an alternative algorithm described by Martínez and Roura that splits the subtree into two pieces to be used as the left and right children of the new node. The deletion procedure for a randomized binary search tree uses the same information per node as the insertion procedure, but unlike the insertion procedure, it only needs on average O(1) random decisions to join the two subtrees descending from the left and right children of the deleted node into a single tree. That is because the subtrees to be joined are on average at depth Θ(log n); joining two trees of size n and m needs Θ(log(n+m)) random choices on average. If the left or right subtree of the node to be deleted is empty, the join operation is trivial; otherwise, the left or right child of the deleted node is selected as the new subtree root with probability proportional to its number of descendants, and the join proceeds recursively.
Салыстыру
Кездейсоқ екілік ағаштағы түйінге сақталатын ақпарат трепке қарағанда қарапайым (жоғары дәлдікті кездейсоқ санның орнына кішкентай бүтін сан), бірақ ол кездейсоқ сандар генераторына көбірек шақырулар жасайды (бір енгізу немесе жою операциясына O(log n) шақыру, бір шақырудың орнына) және түйінге ұрпақтар санын жаңарту қажеттілігіне байланысты енгізу процедурасы сәл күрделірек. Шағын техникалық айырмашылық – трепте соқтығысу ықтималдығы бар (екі кілт бірдей приоритетке ие болуы мүмкін), және екі жағдайда да нақты кездейсоқ сандар генераторы мен әдетте цифрлық компьютерлерде қолданылатын псевдо кездейсоқ сандар генераторы арасында статистикалық айырмашылықтар болады. Дегенмен, кез келген жағдайда алгоритмді жобалау үшін қолданылатын мінсіз кездейсоқ таңдаудың теориялық моделі мен нақты кездейсоқ сандар генераторларының мүмкіндіктері арасындағы айырмашылықтар ең аз болады. Трейп пен кездейсоқ екілік іздеу ағашының әрбір жаңартудан кейін ағаш пішіндерінің кездейсоқ таралуы бірдей болғанымен, осы екі дерек құрылымының енгізу және жою операциялары тізбегі бойынша ағаштарға енгізген өзгерістердің тарихы әртүрлі болуы мүмкін. Мысалы, егер 1, 2 және 3 сандары 1, 3, 2 ретімен енгізіліп, содан кейін 2 саны жойылса, қалған екі түйіннің ата-бала қатынасы ортаңғы сан енгізілгенге дейін болғандай болады. Кездейсоқ екілік іздеу ағашында жоюдан кейін қалған ағаш, ортаңғы сан енгізілгенге дейін ағаш қалай болғандығына қарамастан, екі түйіні бар екі мүмкін ағаштың бірі болуы мүмкін.
The information stored per node in the randomized binary tree is simpler than in a treap (a small integer rather than a high precision random number), but it makes a greater number of calls to the random number generator (O(log n) calls per insertion or deletion rather than one call per insertion) and the insertion procedure is slightly more complicated due to the need to update the numbers of descendants per node. A minor technical difference is that, in a treap, there is a small probability of a collision (two keys getting the same priority), and in both cases, there will be statistical differences between a true random number generator and the pseudo random number generator typically used on digital computers. However, in any case, the differences between the theoretical model of perfect random choices used to design the algorithm and the capabilities of actual random number generators are vanishingly small. Although the treap and the randomized binary search tree both have the same random distribution of tree shapes after each update, the history of modifications to the trees performed by these two data structures over a sequence of insertion and deletion operations may be different. For instance, in a treap, if the three numbers 1, 2, and 3 are inserted in the order 1, 3, 2, and then the number 2 is deleted, the remaining two nodes will have the same parent child relationship that they did prior to the insertion of the middle number. In a randomized binary search tree, the tree after the deletion is equally likely to be either of the two possible trees on its two nodes, independently of what the tree looked like prior to the insertion of the middle number.
Кіргізу элементі
Позицияға элемент енгізу үшін массивті екі бөлікке бөлеміз: [0 pos 1] және [pos sz]. Бұл үшін split функциясын шақырып, екі ағаш аламыз. Содан кейін join функциясын шақырып, жаңа түйінмен біріктіреміз. Ақырында, join функциясын тағы да шақырып, екі ағашты біріктіреміз.
To insert an element at position pos we divide the array into two subsections [0 pos 1] and [pos sz] by calling the split function and we get two trees and Then we merge with the new node by calling the join function. Finally we call the join function to merge and .
Элементті өшіру
Біз жойылатын элементті табамыз және оның L және R балаларын біріктіреміз. Содан кейін жойылатын элементті біріктіру операциясынан алынған ағашпен алмастырамыз.
We find the element to be deleted and perform a join on its children L and R. We then replace the element to be deleted with the tree that resulted from the join operation.
Берілген диапазонда кері
Берілген түйіннің кіші ағашын әр түйін үшін кері қайтару қажеттігін көрсету үшін, біз қосымша логикалық R өрісін жасап, оның мәнін `true` деп белгілейміз. Бұл өзгерісті тарату үшін түйіннің балаларын ауыстырып, олардың барлығына R-ді `true` деп қоямыз.
To show that the subtree of a given node needs to be reversed for each node we will create an extra boolean field R and set its value to true. To propagate this change we will swap the children of the node and set R to true for all of them.