OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Вторник, 10 Декабрь, 2024 01:17

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
СообщениеДобавлено: Четверг, 09 Март, 2023 19:21 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
несмотря на то, что товарищ Андерссон описал этот алгоритм ещё в 1993-м году, пипл по каким-то загадочным причинам в основном не в курсе, что есть такая прикольная штука.

что такое AAtree: это автобалансирующееся дерево наподобие AVL или Red-Black, но намного, намного проще в реализации: чтобы сделать из простого двоичного дерева AA, надо буквально добавить четыре простых процедуры (и когда я говорю «простых» — я имею в виду одно условие и простенький swap), и вызвать их в процедурах работы с обычным бинарным деревом. никаких сложных условий вращения, всё просто как топором по черепу.

поскольку AAtree — это не фейк, а честное balanced tree, то максимальная глубина у него log(N). по скорости AA примерно такое же, как Red-Black: делает чуть-чуть больше работы при изменениях, но зато проверяет намного меньше условий. на поиске даже немного выигрывает у Red-Black за счёт того, что в среднем AA более «плоское». на практике можно считать, что по производительности как минимум не хуже остальных.

ниже код модуля с более-менее оптимизированой реализацией. реализация — в силу простоты — предназначена для копипасты в свои проекты, поэтому к ноде дерева прибиты данные типа INTEGER. они очевидным и лёгким движением руки заменяются на то, что надо вам в конкретном случае. также в модуле есть простенький тестер, и ещё огромная куча комментариев.

Код:
StdCoder.Decode ..,, ..HO2...3Qwb8R79FTvMfPP9fPdvQR7FTvMf1GomCrlAy2xhXhCsQ.
 6FU1xhiZiVBhihgmRiioedhgrZcZRiXFfaqmSrtuGfa4700zdGrr8rmCLLCJuyKtYcZRiX7.2.
 s,64B00k,5zdGLm.sQCJuGqayKmKKqGomC5XzId9N.kayKmK4U1xB.gdj,UBxhYhAbf9P0G2sI
 yKtQC98P9PP7ONbXmb.2.gc3l2kSK2,6.,U08J99SdfJHPNjvQCJuoedhA704TeKKw.bHfEWUm
 L.6.oy2l1kiH20U18J99SqorG4bndMHEWUl1UnNHEWUmz.2U.kn92T.ziE2.,U,Ia8U00.bnUG
 Lu8ro8quGrmCLWKqtE06.,.D,,6.I12U.U,2.I3tfj1.0E65.I0AU0KyCU.2.C12.e,2.AU.Ue
 .4.072U5.,.tRA5EJ9K,IklT8moouqpCLLmoouqpGomC5C.2.u22.KI.E.AUxU2BhVZhjxgiwd
 khgihcsZiZJiiBgg3Zb2hoZikRiuwZjggipZrBhfBhkhgYBhVpZjJibxZrBhfBhjAc,xfoJiZh
 gbA33cUZj1E.sAE.c4E.szE.e0c.2UE0,M7E.ES,cwT.0.3F.2U.E2E..AU7.,.t3E,,0.71,.
 J00U,I6Y6....MRbPNZf9H9RRNRff9bPNTdT1fQRPN1v91fMbv9bPOP9QR7OdPPNv7HF,e00E.
 ES,.6.oF6.2,2..16VEzzzzzz.m1.e54.skM.Ua.UtV,.S6.e6.eE,E0U3U.g.AU2U.Y.AUgV.
 Y.AUOV1Ikmr,2U.kSF.0.7,,.4E.kVyqu8roKKt0GbKqvYjyC.,U.2Gkak,uzzzzzDkek.8V.E
 0k.W10k0UVV..1MC6.7.1c2k0k.W10E0k.O,g.s9s.VW.QUy1N8.AUgV.Y.AURU.g.AU2U.QU.
 k.q10EFE08Mtv.0E.c51.0UO.,.16.c8.2UwK.M,kFE0K.I.YU4U.Q,AUoX.w0s16.1,7M06.F
 .1sBE00.1MNEPk.S4Y.AUb.5.1M0.s66.L.1656.x0S10Eik.K2Q9AUMU.Y,YU3.L,7c,6.d.1
 Mhk0F0.T116qs.N0uDg8AU1V.w5Y.kcU.E.KlW9UeKg0cUX5BuPN9Nbf9BuPN9N7ONbvM.,6.Y
 Z,E4E24.,E..5gwN.,.k5EpV..L1,cUZj1E.s7E.c4E.k.Ue.4.072UM2.4E,,0..I16.M.,.J
 ,2.0E6,v0zT1HM0H68J76VPMVPNZ96TfQHvNHfP19P,d8HN1HM0HsQ1fR996pND,dQTvPdvCPM
 0HEtyqrGLEenS00oZghgaZivgV7ktELmqmOaUIbx.IidxgcZivgV7Et.EEenSQiVpiZhV7A,16
 M6.r01s.6.,.f.Um502.Q8Y,A02U.M.,.,Y..I2,k.0p.s.b8.Q.EbUF,,W.Y.6.l016.0UJ.c
 UE.0.qm.61M01U.6.U1KS6..y.iC0E.Uf,326.w26.I16.M.EJ.1.V20EAk.86E..UO.,.16.c
 8U.E.07cLszEI....b1,,Z1r,8500Ui.i1QCoZmBhbFE.6PsCEt.66sQsCPM0Hk.U.Q9AU1U.2
 .g0..,.Tf.Y,A06.4E.E.7..j,1c40U.Y,YU5U.ACYU4.BE.AUD.,V.AUJU.Y4AUIU.g4AUNW.
 Q1Y.k9.EGk.ul.EPk.8V.6.56.AUHV.29AUL.9116R6.Va.AUv0x21s8EXUJ.d,1c46.N.7s,E
 TE0O.0kJE0.p016Y2U.2BAUF,f,1MP1.z,1M9,U.w1606.76.AU7.7.1606.9.1MY6.v,16O6.
 f37M06.h.7c,6.T,7.g4Y.kY.kIk.i,0E00.O.22AUIU.YU.U4.D,1M36.l,7.Y0Y.kK0.7M06
 .h,7c,6.941cBku5.7c,k4E0.hD.AUbU.YIYUAU.IY0k.0,,6.j11M36.9.7c,Ejk.C,0EXF0U
 .Ic,E0.1O..gz,.Eek.a10EgE.UWjs0cecUXDF9fR5uPPPP1fP7PNZvQRtIdHf.2UlbcZpC.c9
 h0E.8D6..E1U.M3,UKUzjdDZcJZd33Y9ZicBc,ZemhArN1Fd8,tQ9PN,d.F9Rd9Qkm.0rm..y0
 U0gV72iV3iZdC,d.F9R.f1...sQ.IUBgV,BcUYimhgZ3YdRiUIahQaUIgVZhVphXhgY3YoJiZ7
 9,NORfR9fPdPN7963PS,NEZXUAciZgZltyKrum4qEeWqm0GsKKtOqr8rq4KrCqm0mrOKE4Kr0m
 U4IEG500KqsKroOrkmqmuKu0GuyKEGLoKKE..UUIiZZgH2oWZhVRgf3YoJiZd9,tJFPONPN,NM
 R96.0mq4qpKqt0mqyKtKKE8rrGrkGroyKrCLEGLo4Kr0mk00..mWo3hZtQHPPV9P9fQ,NMNvNT
 fQH9RFPPb96dPNR9N,7RTHlKKEOqkCLuKKtmGE4KrGKE4KqmKEyKn0GuWqoCLE84kt0mrKLu0G
 ucQ9vQf9Pd96HfP,tQHPPH9P1fQ,7Q9fQ.oZUAcUIiZ,.66HXh,5vPRvQHvQdPNR9RaKrAhoRi
 U2iZJC.0GuWqkErAc,,mWWhio3YVphU.66dPNRnt0GuyKE84B9P19RdPNZ99SLoaqlWKE8rmC5
 CLEaKr0mtmqoSKoGLqaLEOqkEt0mtKqk8rlWKEGroqqmCLLqk4G3OqrmKqyqvaKrSKEaKrOrk8
 ro4KrGrt0GoyKqGKEOqr8LE4oU.bfCPM137c,7JFPN,7P9fR99P,tPBnmOrm8rw0GqKqkOKEuq
 rGqm0moCbjphZpZBIYU42Uq7P.85ogotMFPON9N,NOb9699S1vMd9Pn96TfP996NPNbvQ,7RF1
 d9O19R,tPBnoG5VPMZPNR9R,783PN5PMfvQ9969PM59O,7P9fN.UV3YqhgmZidRgVZhUYhdpBH
 d9Pc6.oCN1K4ZXmBhb3B,tMF1km4bVZBdvPyKt0mruqmkt.R1G5AB.koummuGEaaUAhnloGLoK
 Kt0mkuacxhmBhuxhiZiVZhg2YjJiUAgUoC...Uq7PkmcQ.wgmBgiZgX3hd,QioJidRgoZBmqmC
 5cPG5d1aantNZPM2iVJCEl.YirxhU2hjJC.,7PsQ,NOR96196ZvPj961fQ996BvPZfMH9N7PNR
 P8RN13V3piZJCuqrG4TfNmqmObgtNZPN19R9fQ,7RFHrwhiFo4qt0GuSrrQgcBB8rmuKEWGlKq
 l.jPN,NMMNPPRNPMdPORvN,NM,dAPtAGLtM8RN1PME,7PHfP0mvWqm8rm0GuWqmQgcBBSmt0Gq
 KKvkoCbZBC11YCG5AB2CoBaqtQgVZhghgY3YV3Ycxhm,.oZUAdiZgdpidZgpBgg3YmBhbVcxhm
 ,.QC1fQ99619PNvPjPN799,dMfXXxhiNN5PRdPOhPN,tPRnt0mk85B1H1iHE4KqmKEmqmEoy4.
 .MNUd,RN1Pkr0mq4qouKu4qo2YWBgg,aKr0WiNER9N9ntEEGLtKagMSTPR,dP9PN796dvPggnZ
 iUYicFqoCCLE4KrGahBgf76bPRZPN,7R44RvPRPN,tPBHugAZPRNPNb961nmIgmxhfhgipZUIc
 ZRgV,d9O9fQ9nk85TfPNPS,7Rj11vQ9vQGrr.O4N76d9OaLECqkuKE8qmIAEEaKrGrr0GuS5T9
 Q9fQ19RHvPsM19PktiqmSLE4KrsQV9PH9RR76186bvO9Xmhghxhqhgn3Yghga,.UiVWBjUIijZ
 CUmBhbVVZiUYic76VPMZHroZUodj3YX3hVphbhgn3YVFEuqmMN796d1FPNm4UaZiZJiUAgUQif
 VWhgX,Uj3iZ,2YnBBVnw0GuKLtuqt0mk0GqKKn...,NOR9RAgUIid,F1.UugVB2YU2YU226NNd
 A,76,76,,UWZZmgVU2YU66s9,76,7L,76,76.y0gVU2YU663XU220mmmmM0GE8tE1GE4KK4HE2
 2,7NgVUUj.,VU..Uj.PkkmmMUUQggAaU2200.51669XBgVJphaxhmZipphVZiZZhtZZUAgUQCs
 MTPRN9N,tMZPN1XUYirllyKrC5.ZPO...CLL0mU0WkZBd96ZPNP1Qgj,.FvP.UiFE..mqmkkuK
 mAhiRgmhgVRidphb7RFXgdR2Yj,2CoBA6EuohZhAb96dXX3B66d1N1UVlouqnmqm0Gry48qmC4
 MOB96196i4aqt0mq4KmKKEOqo8rtGLK0mk0Wk,jPON9P,dP9vN19R996W45nkktgBcMn967vPH
 fPD96kouKvKKtCrm0mr.LXi2YI3hZJCBvPZPNN761Hs8rr0rm8LECLsm4.BvPCqm0GuErKqv0G
 s442Yolk2hdxgchA,7P91pN1P66663166..YAbN1,76,lLUUEE..w3M1.2YYdA,,,dY1ZU6631
 669HNqEEEEkLUUEE.T,qUUEEC4EEK4,764KK.,tMgVBocjJiUAgiBjUIiZJgVZhVlou4T9QAAk
 ouKE66.66d1.TfPcP9PN00Oqrm40GuW4ZPOEs4KuWKEyKnYCYimFE4KrGanRBmGEGLoohUYgj3
 YoFECrkqqm0GuWqouqnAA6Qc9Pc8HN1PM0Fd8Oqr8LEGrmMORvNr76d9OYCsMT9N996H9RbPNN
 fN,7NTPNbfPD7R,dP9PNAgiBjo3hdpB,d8HN1aoa0pb8Je0GW4KuKag2YHZiYZdjxgvgVBgV7Y
 eN3e3hV7cHT9N9f8,ND,7ITOGR8J9eI,7JT8698KdOFRuIHeENOF,dI9uETeI7O1HM0H6P9fNd
 P9N76Z1qGR0GbyKmKqRqk268ohjFEm4gV7A,HMSTPR,dPkruKq68NvPD96NvPDHraGE8qoGrtm
 GECrrmGEOqrMNlPMP9QNHK0GQ0Gla4,NMZHEqqr85dnkuaZphjhib3hUogjlkmKq2imBgXZidR
 gVFsKLt0rrCrmCr4ak2AVo3BbnoCbVRgohiVZhgBjUAgUI4cQY31fP7HuEqUUABGLocR91EoKq
 oSKoGr4ak2AVjphgBDZPO6699NDPNb961fQAggtPKaUUW76F1p1c8M0H6POrmIbUAdCZe3xc3J
 evgV7A,F,Em4Ku4KEemIq.GqkGrkeHEaIb.PM0HMFR8FrN1PM0hOEZO1HktKKrGrouqmmqKeHE
 UvAVcIZUYicBhntQFvPf9P7HlKKEKrtKKmAgn3YZhhkZit3YoJC0mouqtGrm4Km0mrOaCBdABY
 UI3qk4aEI.2imxhXhgYhimhgUQgV,.dXm7RffQR96RvP2YoxhUYCohjVkxhjZhg2YaVZ,oZBAV
 7ogmhgZ3YixBYA2YchgmN6,d8Hl20JdyoVKIWKJdKIE8pmmqm4qtKKbyKm68RfC,dHTXdQbUgc
 CZcUIeZZB.in4qk2W0..MObnuCrm.PvPhPN,dPTXUYAMOR965PMbHEaKu0moCbixho3YoJidpi
 dBggZBCqr0rw4Klmqmum4MSsQFvPEtKKqK40GmKqtGLEGqkGbg2YVVm7QNPM5PN,NOwCd9O,7R
 FXXxB0mrOanJiX3YYBAum4aUnJiX3266b9OUWltKKu0GryKE8mmqKsGbWYZUQij3YGhgg,R0Sr
 om4RvPd1n96dvPOKtKqmAhopZUIZdg,.kayKvKKbyKmYcVZiV78bfQ599,7N9vQeHEuorM8qk2
 8oWSoYuIEGqmCbiYgVZiVdCvVmRgiYgVl4akWuYUgdjpCEWkRqk4UXJiZ7RohZxCRvP7nR0mq4
 qw0Gu4qpKKEuqr66BfQTPP,7RFPNuqrEsEEemI..uomSLbyKmKacYgVZCp,UdIbUo7QbBAVKB6
 cPp76R0cEk4ak2uoWSJIuqIin4ak2uKLmqmOrm2Yug5XtC,78J76jPN,,y4AgYZgdpBmaV,Qig
 MMRXghgV,2YVZhrBgtRiU2hVRCNHvkM0GJk2u4OaUI5CrmuKuUv2YipZmBhbVu..qk2Em4Ku22
 YgVlRA,ZOFdOJZeH,dPPM09eHodZxCsCqk4q.IiZZC.0mr8LEuoY2YeUE,U4BhiZge2YcIijxh
 oJbU.r767PMI5..M1HcEEE4odCpW8JeWGty4,t6,dHH8HN76Z7AHtCPM0H68YC9fQ0moUUYcdJ
 hfRioJiV3Ygxhj3iUAhi3Y13eBAV7we6BdAhcU2ZmxBuGqoCQYU2ad2Ya2YcIC6N66t767PMAZ
 UYcD3Ymxhj76pVmtPuGta4q.98HbOGB86FdQEq...G40GT0Gm4KuA3.00UiYBBn4ak2o7rl2IZ
 dgV7AVL,.cR..EmEECGEGqkM8M1HM0HMGB867PM2YycQTvP.GJYKIb0Gty4,,EL852Y3ZdHhcU
 IC22.R7POaUgcCZcBA,.4odCpWEI8rr.h1v76VN8,tHZ86FdQEmUx2YYBAamIin4MGIijVg,EE
 GJYK2EEEbaIa0mWuYvUG,Iijl4akWuYUocdpBrN1PM1HUBAV,3YnRB0GtKqqktYBBXc,.NHr.8
 rrG5H1ZPOkkG52YkBgmdPum4aEbyKEC4.2YihgZNNsPG5m4QCO4AAi48aX,G5yKsKKt.PM0bPO
 P9QabohCRvQ6PO4..66.856O..I5aEE0GE22YAEE00.3XBAVU2200T,0GE0GE.w3M1H66,VWFE
 EEKal22Z2110WUYAqk2kLUUEE..kLUBMMNNA,VU2YXFEEE.sM.,NNg,HcIf9P9fC,NM,7PklUU
 ghVBDRvPdHo4KvKKEG5CrkEqKKv661vQaKuCLE05u4IZdEc.kdiqmSbcIijFR.HdC,dHsCo8kt
 44p76R0cE..Z1,t6u2N,i1HMG23c9.5FMc7.cNuGqKKvkSIijxB.H76d8Guo4ak2aE,WGJ0mr8
 roSai7P0rk05,tMT9NAhnNOR96d1BvPN9Nr76d9OUglokoMNlnlGLqEosQ69,dMsQNPOYigFn.
 emIM0HsQ66pVm,oAr,HcQ.2Yukt4Kvo3kRUn,UUI585i1IC2YuktkRU0gV7AV3lRq.Z0.q.2YH
 RhZtCPM1H.Es6R,dQq4sMQiZ,6OcS.oBb16R.N144PM0HfP5fQQC6R6PEEy4d1V166.dHrK4b1
 C466Eq.gV7AgUQidFqUY763PN.HfNsQ66HXh7Nogd,sQV1SbgVZxA6RFn4aklWqku4bnqUWBD7
 1000mouKv.MMQBuGEG3oAY3196VXkFEC5gV7widZhgdNQgZ7RcP9vR0rkUUUV7OHXZFqKKvcCP
 k2UW,22..YAbl20GEw36622..y0g,.,767HN000WGWU6631669HNqk2UUkLUUEE.y0g,,,51,V
 UgA0044EEC4P.UoxijdQH1C4ICwidZCUnNP00661vQG505kk8rm0WjZC19PNXZd9PM0Ec.UkZh
 d76FdQTXu.a0kRcJUnVu.EV.Cpd.665Fb.U7A7.RVqVX6A.EtUiIid,NPNkSkr6PkIUCV768Ub
 Vg7QUXxBAhnNO.BvPGaU.6PABABK4UoVnVg..d9PoAUeU7sQ66pVm,Z1i1aEt.EEe1bHvoZgVv
 .b1UUI585i1IC2YuktkRU0g,AdCRccIijxBR7PUBAV7g6in4cI.k4UU6QNXvg,HUUICEEggrdQ
 TXUYC9XeA303.aIrCrm8LueGEW0I5UUUVJ5..M182g,aIX.0mFo7aGEO0EL.,t601dWCV7Um,7
 1,,EeEE8pWGpe.AVcIZUYgp3igBhXBgohAJN8AV7gcA,Z1R,Y5UIV72Ze2YpRiZ3YmBBsMEEem
 IU7ICcQUukYu42ZmxB.mGEGqkM8PM0HkWMFH68J,YhZpAC4.M0Z1maaFR...mGEG4.9eHi1aEI
 cQ0rkaKt0GuW4dfQIbBAV7M0jPN,tM1XpRCuaihZmhgXhCbPOhPN,dQ99QsQ,7O9fQmGE8qmC4
 sRSGtKKEGqr.dP1ak2aEnwhh,8qrGLuyqq0mu0LEGrrYCIijFK0mtyaX3hdFtkk8rmAAUqBggB
 hY3YeA3cQ66pVHRBWGty4HtCPk2I8UH3igFI8rrk4aU3Z7qk2ak2.odZ,WGm4Ku.9eHq.2Y7ph
 nVvgVBg,Fl4wdihgUcNG5qqrCLu0moqKsyaoBgiZiU6NJPRb9RPPNR9RYicBgodPK4wB3HEqqk
 G4HXoxhBAVYhgXJiZBA996d1NHvkr2YVdPT9N002hZJC,NOAgUIgmhgVRhUAhi,,dR19PfPNbf
 9ocjJCMP69aKn00UcBA4ag,EO0GuWaiNOB96H9RQgcVU2Bb1yqvKKt0GqoCmm4aEuWqkGbgdR2
 YhhinZiUIA,tAR76dWiNM,dQ9vMf1sQLXUAA0mt050mo6Q9fQMP99NRN1UE,U2hgghgohgGhgk
 BA0GIUu.a0kRcE.H680GrKqm2YmhgkVdphbxbBAV7cPT96RPN9XoxB5nmCqp0GnyKt0GuWaUQi
 Z,YZUIgZRAkoGLES5ohjlt4KuaqtOqw0GuW4DPR1fQ7961nwSrkaLEemIM0HWc.R,u0h1t76Zv
 PT1Uh2YlAZUwdG,cQEL.m1Eq.P,GJYM1AVcEt.,dPTXUYBEJU7Yc3RccIij,kIin4A,HWm,Z1.
 0GT0GtUg,GJY66Z185.cCIC6PU3p7Uc.UoVo,k2S5knKKu0mkSrkabrBho76b76bvO9nt0mku4
 Z76b9QsQWGryKr.UdgV7k2GbZ3YjJiYhgm3YdRiUAhh3C.FPNZXeA3cQ66sI68kIi1.RdQEE..
 .amRq..UiIC66...R,A3.226Q68kI.EL.,,..kIU3lREd.85q.2Y2hgg,UvgVBA,YCH1bnu6NS
 LoKKr0mvK46N99P9nou41HEaKrGrm8Lr66RvP7XcAhiggi2YVdPkvEEGrvyaXNOICaGLA,jXfp
 hjxiUogjltKLtKaoNMwiZ3YcBgqFuyarBggRhUIidVUwCH9P9nvKKEC4N761HmICEEMNPk2GLt
 Kqm0mruKEyqu8LESrkaLE8qkCqp0GJa0V0.UZBdiZiZ,WGtER.H,sCo8EoKqo8LR0Gb.82U7,o
 3ELm4s62YIVBk2.UUI5Gom..WGty4.HN1HkWm2M0FVjRhg2YoNOABG5,dPTXUUn3BEtgB2YeU7
 6O66pND,dQEqoArl2AVGhgghAo72ZmxhjN8M08500WqmaKtqk2akWuYvUcEt.G5G5I3cI90YcZ
 ZBI8EI8rryadg,9WU.A7.rN1PM0Uo,wCEEGLt.2eG,.EJ2ZmVucHsC,,e1..g,h02BI5.8222b
 uIEtEECWCFKkIk2a2ELcRMD0XIVUI8UmVUgcC,EmEEqXmViYgVVIVBk2W40GRcQEqoAk2a2FPN
 HHLmqmO5..aEIcPT96NPN2YXVYZZUYgmxhk3Yo3BohjZANFtKKuUo3B8roEEC42YVRCohZltKL
 lGLtKqmICM1HM0aUo3hdlkmqtyKEwhqhgmRiUYCQgVRCy41HqKqk68RvP,tMEt66GLE4KqAZUI
 Zdk2ak2W400.Z1i1AVGhA.23M8r,aEtEEe1F1P.98Ha2EL.RVq,.U723Eta40069.UiVg..YBB
 1EEUU...,d8U7I8.68kI.HcQ66p,.K290aEI6O1vQ8qrGLo0mlW485N76RvPj96H9R,dM9nrqq
 mCLEqqr855vPP9QNPOMN7f9P.HEnaKrGKEGbZ7QZPNhPOTPRb96PPMlPOPPRP96H9R9PPp76jP
 NqqrObY3YoFuEqEKQCPM0Hk2Aho3YdlnKrkAgiZiZhgY32FPMUUAhohAb961fQYBb14KrYCwhi
 hgUAgo3YoNN8rrsCk2oBj96jPN,7O.S5Yij3YoNNABMRR9RH9P,tR9XdZiUAgUohjpBHfPdPNZ
 1,dPGaBA,aUcAgUoB7HEAByquGbVdQH1C4AZg2YVpBqqrObUAhoRC7PM6RTHty4,7NsCk2YCHX
 rBhglq4qoMMuaoVjJC9Xe.akfA72hZFL8roEL.CWk6FT86FPNHHE.o3EEKIb.aEIeWrFnyquuK
 m0mnyqrGKEGqk69qqr.,7RTHuEty4,d8U7gdjpiZp7Y6dHIWqmaag2YmxBaW723qqrObU2B2YY
 BA00850GmUe.aEI6O9fQwiZtMuKE8rmKrtK4fXYhggVUQgjZANFlK5jPOdHEyqu8bihA85.r,a
 UWhiolmQBcN.Yic7RS5jPONXVZhrltwgj3Ym,Nlt2YpRC,tQHPPVnoKKt0mly4,d8U7ICoZgdN
 0GR6FU7,68.M8PM0HkWuYBM098Hg,23Gqk66HvQuao3YaNRMS99RN767PNCqmuKmum4k2GqmCr
 lkou4PPMnnlW42YoNNUUwha7RsQffMEKQijdNH9S,7RFXgBB0GJa0A785uGmUw.Y82Ym,Z10GR
 .68Z1.NFm44H,K20WjVgVU...69G4.u2UvUGh6EW.Z085M8PkW66.rN1PUE,UKBggBB19R9f8W
 0I5R0HtCI6.b0UUQ2R0.akf.ZvPo3O56AM1ak24290.Uy6AHtCP.H0.BHLcRs66JM1M010.En6
 N1XUY5ZvP6NM8kWsCkY.ICc9oC..AV,,..Gqk66xVjVYVd.90EIsMFPN6R66HfP44UeA3ME.Ug
 dNYBh1Iij,kI2Ycktiqm2Ydphq,2YeA3..cQUm,m422.N1a0EsEEaKrO5.UKBggBB68.OadQbB
 UmVUI585uGtUB.U,,.maqFEq1HtC..2Yx2YnhAoBNP8P.0Gf4Kq.rV728.gdV3j2hgkZCJ76Fd
 Pp,cCa2kRcJUhBgsZgZ3iodC,NG.cE..R96576R0.A7uKLmqm.0HEUUghV3jY,,dCvFMqk2aUA
 l4kq..POEl88X79,NAiGEqokW568Rf9NHnM8rN1A,.00UhBgs,mGE4HE.UcEtUdAZBA,9eHi18
 3kq44k4akW66POMl1QbBgVB68eGEGrkiai3YaJijFc8rreqmCKu0Gc8qrWLE8qwIdi2YHZiVph
 ghgt3YLBgmpgj7N,d8HVE,U1xhh3ipZiZpdZ3joReZhgY3Ycoe,JeUQiZhgYJbUA7UdQbBsETe
 Hb8JPM0qqumKuaKsmqokS0GOWHNSnMin4AVhxhYhighin3Yx2YmAaowao2bnoaowavgV7AVlhi
 jZidhgiZiUgbUghjZgp,7OGh86PPRN9R.rN1HM0ZPNPPMHfP7PNZnSgB.PuH786PPRN1.O3PUg
 xhrZZU2hdxAp76H0sCI6M1UUIbx2YnhgZ76PuH7msKrrG5QbBEoaqnWKEenS.GoYOZlhij,Unh
 gZZApVhhig,66J76NvPj96P76ZPNPPM.JFoaqnQbBA,HWnhAYbx2Yk.AdCRccQiZhAN76PvP71
 aGEKIbGo4g6QcjhBf1.in4qk2.I88JrGqYuKu0GIO3C5e1G38ZUohu2Y7p7kIeX7,QbBsE..2Y
 x..UnFmmooqqoGLEqHE.QbBAV0,,,EM0GS0GrmGE8HM661uIb0uaw2YnhgZ,YZUIalAZvg,Cor
 qKsK5.9HICrmKadQ5I8UH3dDJeI3Z3pdIBd3JecQiZhA,t9,NPG42Ye2YiBZdgV7g6IeiZAQ5P
 .UGVVphYxhhBhuhgU2ZDheI3YnhAe1UGBZvEf.7PMIbUYcVZiZRiiYcVZiZR5HM0dPOPPNp767
 0bHeaqqKqRqk2Ahu22.rV0,PU2BgohASomGLW4KuYedhhZ3ZYBAmGEGroM8rN123,NFNPMVvQ9
 9N,7RHXUYCHXthgVJiUAhi3YnhgXxhiZgn3YeM1akt6N,dC2bqYak2aUIZUYcVltY6n987PMAZ
 UQZUQaq2ak2Ye6RHPPuGoyqu8bf2Yq2aUIZU.qqouquGrm0mJ0GuaqqsQ9vMTXvgV7cFTeI,NO
 ,dCvFM0GeyIESHEGob0mVyqq.UZ78kI0mWu2.1fP.rN1PM103Ed6J9vQdvF9fPjOOVPNJtCPM0
 50A,4a7ZiZhBqXsAatIaUI3XtA,7FOZnQbBg,h0AggZhihihRiu6ITOGcIkU8Jd4og0mbOIEaI
 bsF83aErKrqCruCrmGKR00.qU72eG,kXKKrKKt4KuKKEWmIeHEuYYtCcJ10aEnmGEuKR00.aU7
 2jYhAWKKohYhgkFR..IijFR.UnFme1UGl4M0V0.cHfPP,78HV7,k2cE90,dI.ZeP7Hr2ZnhAmW
 BBcMNGR8JkI0mK0mMOnIqk2MFsF9fPsCPM1HEVUBUGBgi,2ZnhgZN8r,CJuGKac9b8RZPORvNF
 d6DPNK4aKrIYdQbUQeoZAMGR9RFNP19SH0amRqk2.kd.2YixhYtQr76bPN9HR8mIiHE.A7QCA3
 ,tI.NePrN1HUCVVZhgpBCLK0mq4Kw..R1f1,dCsC,7S7PNVXU.qk2cQ66pVndPUv2YcI39PPV9
 Rn968rmc8k2O2OKEenS2aUUhBgs,0mK0mM0GWy2AVGhcEhc,ZeUohUIbxsF9Hb68H76feHdOGN
 86BOO2ZmVgcPH76v76ROGNuCPM0AVmVUU7lm8bc.N,r,aEIcR19PHnoGrw0mlWqmsQ,d8H,akU
 .Ooou4.2YX2YClIin4k2Opkkk68kIin4k244sQrePfPPbPRML,dCvFrin4k2aIbcPfPPUdQbBU
 7230LtwgmhgnRiUYgphhk3YeA3M0R9N99Q.POM.FdQ.M0HeFuKmK40GT0GwGqmYCGJYM1M0W5E
 RcP7PNsCa.Hkd.a2uquq4b100UH,.69EEGqm05,NObf6HtC.A72jYhAAZv22.Nm4a.HMFQ5.U,
 ,ohp,2Yx2219SH0a0sI.b0knMNkr2YXxhh7P99R9fC3N8rN1.kYEr.A3.Q8.,,.0066..a2qok
 W568UdQbUQ8UAtCEdY8cQM1HM09WU.MNrl46I.sJH9Q996FdQcCUdQ5oe,,C57fC,FbUGR5Hk2
 W569Wrq4KwG4ErG4I5..R99,NO79Sp76H0.822Y,,IC2YXcH.aEd44.kIg,Q8UH,sRH9QHnniX
 nVuI2r76.a2C5aWU.6H.l12Yuka.23M8r76lPP11666S7PNsCkf.wBR7PUX6AG2M0HWGpB.Y3Z
 N8,ND01F0M0uKEenSIei,.q2.A3cBk2akWm2A,HkU.u4UUQYUM8r,aUdZgs3Yug5..uquq4M8A
 6UdZgs3Yw22f1UBU7cPkkmKqUPBhY3jRRbBA,aU2h6uquMR.M0a2FdPf166EEO0H9NQ2RPRP1A
 ZUY8.HUV,Q966pVV,cPQipVRhV7A,HkWuYBk2akWsCk2a2BOOR169A3UUYe6,A,Z1,dCY6N1F,
 m0i1A,hOM.UdM1M0uKm2C00q2Uc..HkYcP2C0GS0GwGqmUI,M02DUuEr.r,a.b0MGcPktM8r76
 b0sI.00QCEE.,NO..H0l1A3.Y7P.HkWM1M09Wv..Q8UH,sRUUQAP1oZWAZv.EaQ5ME.Z1,NDC5
 Udk2K2,tJH9Q9vCPU0h6g,Spo0rmWmXKKr.FN8HN1UIhgnZCw8KqRM13OFD0WGJQiZpBEEWqk6
 PO50HK0mku459OcQ2YkxhdphoRCdXdZinhAIZdEbK2bPNR1AZvsQ9fPUiYhZpA,,b1kRQiZ,oZ
 mBB22.k4KIbGY9ZicVmNNRN1PM13sGd9O106J9vQd1k48ssHpmsETfPdfQT9PNPNZvQRtIGqVG
 LtmKWKqtCK.4TeKKw..umVyKrG5EWKqt2.501PORPNZvQR,85...CLL.U2V.Iy2E.0.G,0.aE.
 0E.0E..k.8ssH38pumqm8rtumdcIf9PY62Ulb8.CLL8pumqmY62UmT.2U.kJl12U.QI,E.0U1C
 SW5ktumdsIdPSNPN7ONbvM,Mw.ELMSN12Um5V.2U.2..F6.0Eh0E.2U.E,5D.oZ,ZioJC3HuKq
 tGomCrl0U2U...G00k.0U.6.665hK2.,c,HT.eRs2U,.6.,U0KS2.,..e,2.A.c8mb,6.2UEC.
 6..ONj1E.ONj7bPAM,68hAU0E.7.U0CyHZiYZcjNRPPNQiiQcj,.k8U...F.,.mU.2U.2cPRCa
 NF3kwL,,Az2sS3B,Abj2Xb....
 --- end of encoding ---


а чтобы показать, что это реально ОЧЕНЬ ПРОСТОЕ ДЕРЕВО, вот вам ещё код: он сделан буквально из классических — по учебнику — алгоритмов для обычных двоичных деревьев добавлением вызовов очень простых функций балансирования в стратегические места. то есть буквально: берём обычное двоичное дерево, пишем четыре процедуры размером в несколько строк каждая, втыкаем вызовы в классику — ура, наше двоичное дерево теперь сбалансированое. в ноду дерева надо добавить ровно одно поле: `level: INTEGER`, и у новых нод инитить его единицей. (на самом деле для деревьев размером до пары миллиардов элементов хватит и `level: BYTE`.)

Код:
StdCoder.Decode ..,, ..3r1...3Qwb8R79FTvMfPP9fPdvQR7FTvMf1GomCrlAy2xhXhCsQ.
 6FU1xhiZiVBhihgmRiioedhgrZcZRiXFfaqmSrtuGfa4700zdGrr8rmCLLCJuyKtYcZRiX7.2.
 s,cGv,0k,5zdGLm.sQCJuGqayKmKKqGomC5XzId9N.kayKmK4U1xB.gdj,UBxhYhAbf9P0G2sI
 yKtQC98P9PP7ONbXmb.2.wiwk2krm1,6.cUGpmWLuOpoKqvCbHZChOO9HWUlbeZ3Dkto8Y6cw3
 .0.F7Dw.wVwU.sUGpmWbBxhYltQ8q2Y6Mw.sQq2Y6cwD.,6.AXuk5k6e1,E.M.,i,cU.ktAcoZ
 imBhWhiohgnZcZRCY.2.w22U.EBE.0.4E.6.JFyuv.U.2m,.l.1cUZj1E.sAE.c4E.k.0.e0M.
 6YE.S.2.YrlQ.JhM3E,5zd6HHfPLvQR7HHfPL9F9vQs.E.cHE.MF,.,k.q1Goo4Kqyqnumb0rm
 uqWWLuKKtuqkmKISGoGLu0rtenLymmuKLSroiqo0rmGqo4KLyKtSqLSroiqoymU4ojGLtKqmSm
 IIU0KyC.,Un.,UO.,Uz1,c8U0E.072UZ.,.t3Umz,6.I2,E.0.F.,.k.aE.E.ES,IEU.EmE.EZ
 0.0U,I6Y6....MRbPNZf9H9RRNRff9bPNTdT1fQRPN1v91fMbv9bPOP9QR7OdPPNv7HF,e00E.
 ES,.6.oF6.2,2..16VEzzzzzz.m1.e54.skM.Ua.UtV,.S6.e6.eE,E0U3U.g.AU2U.Y.AUgF.
 0E0k.e3CE,9T5E.0.v3,6.Y22.M.,.5uPffQHPNZ96RONjHyuv.2.0E6,P05czzzzzz.f01c20
 .7.16C6.9.440.AUtU.Y.AUG.9.16C6.7.1c3k0UjU1280k,uDYd.k.m40E0k.q,0k0k.G.0k,
 0.1MD6.3,7cUZj16.,UGQ.2U.c4E.k.0.e0.,6j3.K.Q2YU3.3.7c,6.L.16x6.j.y.0kEE0a.
 0E2k.S1YU.k.K4o4AUb3.Y.AUb.5.1M0EjUrU.Y9AU3,r0164,U.Y,YU3.L,7c,6.d.1Mhk0F0
 .T9.AUMX1Y7czkek.C20EVE0U.AU,2.16I1U1Qe.k,.R01MI6.58.Y.6.VO.YU4.911c40.N.7
 s,6.V51M36.5,1M.2.D.0,0EuE0O.IRAUOU.Y,YU5U.o5YU4U.oDAUF0P11MI6.n,1cQ1.1W.A
 UhU.220k.W.0E00.1M0E0k.W.0Eok.a42JAUq.7.1s6EME0a.o0YU4U.w3Y.kOE0.H0.H,1s46
 .76.c,EEk.G,0E00.O.w2AUJU.25Y.E8E0.P,7M06.h,7c,6.941cBku5.7.g,,E0.h51s76.7
 37616.3d.AUEE.0kvk.K,0k02.7c,Ejk.C,0EXF0U.Ic,E0.1O..gz,.Eek.a10EjU.UWjs0ce
 3f.8ssHomOrVyqqqqkuKmKKtCLLCJuo8.,Mw7ONh1.uGf.2Um10..o.,U.M365szPuH7OJNOF,
 tGd9O1OEdeQ9ndaqqYhZRbB2Ze2YnhgZ3Y02hoZik,916Q91.s9.8k4aEs4KsKKteHE8EoG5ku
 ....Ui.3M1PME186dfQ9PN,NOb96ZN9b763PMNPMRvM99N,7RZPNmGEaKrOrmuKuKKm0GlaLE4
 It661eP7PNQijphigVBYechgU2iZJiaxhmhhVphXhgUwha3YVphUAc,3YoVUUZBipBhqBgghgi
 ZiUYij3Yo3hZ32..66ZPN7v2,hMNPM5vO,7RZPNuGESJoaKqKKE4Kr00UUghVRhZRiUghjJiZ3
 YmxhoBgoBhjphn3Yo3hVphUAgU..Ug6RFPNCroqKsmam3YVZhbxhmBho3hhRiUYiZphY3YoxB3
 PN,dN1vQdPNZ99,NMR9N,NMN9P,tPB96d9OHvQ,dM.b96TPRd96dXmhgnhigZiUAhi3YnBhhBh
 gBgm3Ykhgm,EL0mU0GtK4.UUABq4QgjphnBhnZiZphoNORnoGrt0GsKKt.66d9O11RnU42698q
 uGLE4Kr00UUYiZpBb96dvP,dMoggBgoZiZJigsRFPO59O,dQ9vQsQ,NOR96b9PHvNF9RNPS,dN
 11Z96bPN1fQ59O,7RHPP9vQRN1P6JcNT9PNvPjPORvN,NORfR1fQHPMR9Rb96FvPN9N,dNTfQ,
 NE10QiugVBIYU4YI3hZ3Yghgqhgg3YjpA9fR9fQn96NPN1fN,dPT9N996HvQyKrKKLqEF0OE.O
 bg,cQEnGLECKoaKqGKEaqt0mmWrkCKumqw0mruqm0GqKqtCLEGLoEuWqkGLEyKnAhoFs4KtKKr
 GLEWGlKql4quCrm0mm4qlWKEmqmO4.MM,dR9fQdPO5PMN96NPORnIum480.hHqUZFtcQHvNF9R
 ,tMF1km4bVZBdvPyKt0mruqmkt.R1G5AB.koummuGEaaUAhnloGLoKKt0mkuacxhmBhuxhiZiV
 Zhg2YjJiUAgUoC...Uq7PkmcQ.wgmBgiZgX3hd,QioJidRgoZBmqmC5cPG5d1aantNZPM2iVJC
 El.YirxhU2hjJC.,7PsQ,NOR96196ZvPj961fQ996BvPZfMH9N7PNRP8RN13V3piZJCuqrG4Tf
 NmqmObgtNZPN19R9fQ,7RFHrwhiFo4qt0GuSrrQgcBB8rmuKEWGlKql.jPN,NMMNPPRNPMdPOR
 vN,NM,dAPtAGLtM8RN1PME,7PHfP0mvWqm8rm0GuWqmQgcBBSmt0GqKKvkoCbZBC11YCG5AB2C
 oBaqtQgVZhghgY3YV3Ycxhm,.oZUAdiZgdpidZgpBgg3YmBhbVcxhm,.QC1fQ99619PNvPjPN7
 99,dMfXXxhiNN5PRdPOhPN,tPRnt0mk85B1H1iHE4KqmKEmqmEoy4..MNUd,RN1Pkr0mq4qouK
 u4qo2YWBgg,aKr0WiNER9N9ntEEGLtKagMSTPR,dP9PN796dvPggnZiUYicFqoCCLE4KrGahBg
 f76bPRZPN,7R44RvPRPN,tPBHugAZPRNPNb961nmIgmxhfhgipZUIcZRgV,d9O9fQ9nk85TfPN
 PS,7Rj11vQ9vQGrr.O4N76d9OaLECqkuKE8qmIAEEaKrGrr0GuS5T9Q9fQ19RHvPsM19Pktiqm
 SLE4KrsQV9PH9RR76186bvO9Xmhghxhqhgn3Yghga,.UiVWBjUIijZCUmBhbVVZiUYic76VPMZ
 HroZUodj3YX3hVphbhgn3YVFEuqmMN796d1FPNm4UaZiZJiUAgUQifVWhgX,Uj3iZ,2YnBBVnw
 0GuKLtuqt0mk0GqKKn...,NOR9RAgUIid,F1.UugVB2YU2YU226NNdA,76,76,,UWZZmgVU2YU
 66s9,76,7L,76,76.y0gVU2YU663XU220mmmmM0GE8tE1GE4KK4HE22,7NgVUUj.,VU..Uj.Pk
 kmmMUUQggAaU2200.51669XBgVJphaxhmZipphVZiZZhtZZUAgUQCsMTPRN9N,tMZPN1XUYirl
 lyKrC5.ZPO...CLL0mU0WkZBd96ZPNP1Qgj,.FvP.UiFE..mqmkkuKmAhiRgmhgVRidphb7RFX
 gdR2Yj,2CoBA6EuohZhAb96dXX3B66d1N1UVlouqnmqm0Gry48qmC4MOB96196i4aqt0mq4KmK
 KEOqo8rtGLK0mk0Wk,jPON9P,dP9vN19R996W45nkktgBcMn967vPHfPD96kouKvKKtCrm0mr.
 LXi2YI3hZJCBvPZPNN761Hs8rr0rm8LECLsm4.BvPCqm0GuErKqv0Gs442Yolk2hdxgchA,7P9
 1pN1P66663166..YAbN1,76,lLUUEE..w3M1.2YYdA,,,dY1ZU6631669HNqEEEEkLUUEE.T,q
 UUEEC4EEK4,764KK.,tMgVBocjJiUAgiBjUIiZJgVZhVlou4T9QAAkouKE66.66d1.TfPcP9PN
 00Oqrm40GuW4ZPOEs4KuWKEyKnYCYimFE4KrGanRBmGEGLoohUYgj3YoFECrkqqm0GuWqouqnA
 A6Qc9Pc8HN1PM0Fd8,dNTfQ,7R9XdphbRbUYicFuUXxhYhgUAhoRiZZha3YYxhZRiixYo3Yihg
 ZlkuqwGLoaKr2YeAZBAV7hdExdGZeUYcVZiZRig2YHZiYZdjxgvgVBgV7YeN3e3hV7AVCxhYhg
 e2Yx2YExd7pdIhcG3YIxdUgcMZe3pdHBd0Zd33YGhc1xdGZcBAV7AVghgaZihYZUICM9p76RuP
 7PNrN1HM0H68JFry4,7Pk4ak2AVtxhp3Yi,TfPNXcYhjxgUYhjxARP8,dMH9Rb99,tQT99,dNT
 XZ3jVhhkZBN76l763PO2YVJC,NPTfQYC1fPKKryquSKo0Gny419PNHs8rkCKuaql44VPRZ9QTv
 Q9vQPM0Hk2GLoQCHvQ4qlGru4Kqmqw0mk0GNUmFKAgiZAd1N10mo6RFXqhA.FPNHvNF9RPM0Hk
 2yKrmqwIidVUggYxgZRiUAgmlkmajNN008aU2BIDUeAZBM0H6POrmIbUAdCZe3xc3JevgV7A,F
 ,Em4Ku4KEemIq.GqkGrkeHEaIb.PM0HMFR8FrN1PM0hOEZO1HktKKrGrouqmmqKeHEUvAVcIZU
 YicBhntQFvPf9P7HlKKEKrtKKmAgn3YZhhkZit3YoJC0mouqtGrm4Km0mrOaCBdABYUI3qk4aE
 I.2imxhXhgYhimhgUQgV,.dXm7RffQR96RvP2YoxhUYCohjVkxhjZhg2YaVZ,oZBAV7ogmhgZ3
 YixBYA2YchgmN6,d8Hl20JdyoVKIWKJdKIE8pmmqm4qtKKbyKm68RfC,dHTXdQbUgcCZcUIeZZ
 B.in4qk2W0..MObnuCrm.5vPVPS,dPTXUYAMOR965PMbHEaKu0moCbixho3YoJidpidBggZBCq
 r0bVJgghgig,a5CLoy4IiZZhZVUYgZRio3YYBgo79,NMcQ0Lq4qlKKEa4jHuWKEGLosMTXUwha
 tQZvM,7N1Xi2YeAZB..Cor0rwuorGa2BgoBgU2ZnJiXZZUYgZRCp76RuPA3PM03OFDOGR867PN
 bHLGqkGrkIbx2YnJiXpZYBAqk2KIb2Y1xhk,G2in4q.QgmhAdXihgrdPT9NiHEqqkaLEGrkiqm
 0Gry4,dNZvPP96d9O9Hry4050GJa0.EbKqvuorGqm2ZYBgodC.AZu2YCVvgV7oe,,RfC,dH.30
 qk2aEbKofWGramRqk2aEruGqKKvKaUIbx2YlQbU2Ze2YrhgU.T14KmGqou4Nnk.CLKAgiFqKqk
 .0mkmqv4qwCLEWqkCbgdRMA,d8M0R1B9R,dCvltKKrG5QbUohiIidxgcFRq1.gV7A,GqkGbUUY
 BAiX7cI98JfeIR86Rn2KIbcH9vRkRgVBg,cQ99R.2YjJiUod776J,V0.BOOR9NJ76FdQTvPdfC
 ,,iHEGqkcC..k4aEVUUAcHRe3JeI3ZmxB0mF0GbaIamGE8HMamRqk2aEI6RKKt2Yd,,7FHfOLv
 QdfQ196NvPT9Q,NOR9658IPM0HsJFOGNOF,78ZvPoZghgqVX2YkAZUoYU2Zm,71,7D,7N1Xd2Y
 2xdUIijxB,dCvFtyqroZmBhbl4MFNuIHeF,78Z1m4..EmEEuHEGqkGbd.EE.oZgdNqk2aUCtCa
 UeAZBAV7w8..h1..G40mF0Gm44H,PM0HM0HeF,7N1XUo5ZvPT1EeWoWuIE8rr66.uGtUUgcARe
 33YmVU.c9NHn2Y3pd2hV7.kUCpdK2WGty4cRMD,7AH76TeI,78Z1G4gbUYgVlIamRq.HWmxBYB
 .0GeWoW.00uoYmIEKIbQ5I8UmxBqk2KIb2Y4BhitCPM1PM0gV7AcUQifFE8rmq46PO4F1.mai,
 IijZCa48roUVZC66VPMZHroZBAVCxhUQA.66RnmgAwBd1N1C5B144ElQAEukr0rm85M1HsQHPP
 VnwYipdPb1NHn...,,Et.F1.Uuk20GE0WUUY,0GE.cMgV72YUEEs9EE0GE00Uj.PM0,76IA000
 mmAaUcYMMEE2YYl4a.y02200..y0g,199X762YUQA0000.51669XBM0ZORNPNp76196N1C42Yh
 BgtdPT9RWqkOrm0Gukt44mqmO5,NMbnoGrt0GsErUeA303.CppKqv8pmCKEWGty4p,AZu2YCVv
 Ef.bPMhPNp76R0cE..Z1,t6u2N,i1HMG.R,s60HEG3RO1HM0H..OaiYhZpCg5ZvPT1UI37U7QC
 2Yug5Z1rN1AV7Iijxho3Yu.o3OavgV7k2C5uGqKKn2Yu.cQkRqk2M0Z1.,dCQiVpiZhV7M09Wv
 .Z1.kdi468ZvPT1kIqk2akW.83.g,66buO91in4qk2.2CGLE8bh,CaiRiZ,6O..Rnt.G5EqUVl
 4akouql85b1G5m4sPYC2CUU.YCR1b1CKoUU.N1k4akk0mta4N1GaUIgZ,AhaVnVUABqaYFna4U
 n3CsRm4RnnUo3BPM059O1fPQCP18qwYA6666HfPhXn,44LXi2YI,B1NVU2C05,tQk4akvaKqma
 allKaoVihgr7Q11004acBBEqKKvcCPk2UW,22..YAbl20GEw36622..y0g,.,767HN000WGWU6
 631669HNqk2UUkLUUEE.y0g,,,51,VUgA0044EEC4P.UoxijdQH1,tMEtkvaKu.Cbh,661vQG5
 05kk8rm0WjZC19PN1um4a...0LqaaGhgX32ER.H,sCo8ktER.cE..EECWC,.HMG.R7PO5CWk.R
 0HMG.85oZmBB6P91q1y4N1Y8.HsQ66pVmVvU7AVmVUI5UiICsCk2C5uGtaqn66p,EqoAr,aEt.
 66pVndRin4a.HMGRuEFdQT1oCamRq.aEtUm,kd05EI.UdU7g6qU7UvUG,.PkW660Lq.r,V0.ZO
 NVPMHfQZON596Uu.a0kRcE..EECWC,.HcQERkpcI9HIUdQbB.226Q.F,a0I8.M1UG7Q.r,FFE8
 boVUMNjHty4,7RK4JN8..HePbPNZ9RJ76F,e1EEkke1..g,30q.HeFW02YX.H76B,c9N10mF2a
 d6JFGbk2a2Z1G40mF.G3U7A7.Uw.Y82Ym,ZPO66MGR1WGty4.N767PMAZBAV7M098HK2EqoA..
 .YZUYA.akWuYvU7AVc.VPM2Yo3BGLt.A,HcQ66pVGhAcICKIUdgV7kWM1aUAl2WGJggh3ioBD8
 5.8500uom.F7N19RU3p7r,Z0.qU3FEaIrC5in4q.V0.7ONNPNdPNZONVPMUU.e1M8.r,EE..,t
 6u2N,k2a2POGR88ZvPTHLUiEv69,dQTvPICc9Ud2Yw2YmxBYB66P76X76d8Gg,Yc3RccIij,kI
 i1aEtUm,.,dCgd7p7..EK.m4A3.2YuEd.68kI.i183.g,667ONN1.sC.ZHu..0Gu.6I..c8WGt
 ERo766ER..UBcJUchgdJiu2YC,I6..665,.M0HWmVi.0mF2aU.M0HWYVUg5Z1GqkEe.AVcVUIb
 x2Ym,NHnQ5Hk2akY6O9POZf9NPNh1vFMY8.HEIcP0GqK4,tMEK0Gm8rr0LEGLoa4RvP7HKIiZZ
 C6RFXmBB2YX,,NMbnk0GrK4bPR39RZPN9HtUBAV7M0YCHXVZhnxhUQAhPNZvQ,7RsM1vQwB6P4
 4FdPT965nocQMMd9619PaGEemIM0HM0W400.Z1i1A,ZONNPNcH68ZvPTnIi1A,Z1,dC2hZBBPM
 0Hk2KIaA785u0c9oC..A,F,IidVU.m0.cP69..NHn.2266..EEemIU7cI.EIUd.aUmVUI5.M09
 W3hV7A,HEI6O1vQ8qrGLo0mlW485N76RvPj96H9R,dM9vMTPP9vQ,NPT15vPP9QNPO5PMdPN7f
 9P.HUaBhiZgUYC9Hs8rmOroyquCLEqqkWroqquqKEaKuKqqeHESrmghjpiZZgUYCG5m4mWnxhB
 AV7M0Aho3YdlnKrk8rkuKuKqmGKEGLo4KuUUAhohAb961fQYBb14KrYCwhihgUAgo3YoNN8rrs
 Ck2cPTvR,tR996FPMhXoxBjPMNvO,7RTHugAa4giiZidZhUwiZ32H9R,NM,dPTfPPNOR9R9fQR
 XUohjZAPM0Hk268196RHm2YrBhotPf9R4am,C4AZg2YVpB,tM0bUAhoRC7PM6RTHty4,7NsCk2
 6Ra4jPONXhBgdlkoBd1TfQ7PNZ96JN8k2w8EoK4RdQH1R,s66FT86FPNHHE.o3EEKIb.aUcI3j
 XaxhpphY3YbxhjZgUYgVFKQgj,0GuyaoVmxB0GJ.HkVyKsaLbEWEIWqmaag2YmxBaW723Cqr0b
 U2hZFEGqk66cQ6671e0M085uGqoA,dCYcZ,FdQ.Y3Z1G4amRq.aUmVUI5.83UX33M8P.HMFRm4
 AV76H.H68YgVFEaqtoBd96BnukwKKumGEGqmQgZphYpZBU76N9vQ51HfPghVBD59OEE.66TfN,
 7RsQffMEKQij3YaBhs3Yo3Bmqo66JN8k2a2Z1R,Y571G300cQUu.EI.UgkkM8P.HMF66y4m400
 ..Ug6N.AV3p7r,aEtEEe1.Z085.H,K2P.FVrFrKqm22TXZ3C2YoJC0mruKqsRFPNR96H9R,tR1
 vQ,NPT9NHfNHPN796JN8.8rr66..cI.aGEe0g6i18pW.k4g600kRqk4..OpkmqoGqkGrmeWc.p
 FbkIi130..0mFo7.M0j0IijFLcRUkUBk24290.Uy2YkAZvg,A7.oARVqVXUIVBU7A6..BXYBA0
 GSIijVYVdU7g6i1A7.Z1u0h1..HME..UYBA0GTsP6NM8kW.23CKoKqliKE.HXV,c8H,42.6PO4
 NHv.ZvP.A3,78QifhA,FrO5EEemI..Um,856PEE.YBM8.V1,NORfR..OpkmqoUc.cNamRq.850
 GRcQc9Z1qk2g6U,,.maqFEq1HtC..2Yx2YnhAoBNP8PM09WUoeVZBkRM0V0.POMl9F99QdHJ0G
 IuKR.eX7,Q5O3MP19S7PNV9ReHEa2.82.Er0mF0Gb..HWipZghAUk2266PPMl9NEEenS2aBAV7
 6Hg,gB.ka4IgWmMmWls8,NH19SUcohiYBBXdQbBk2.66.qqkW569,NA,,.W0Z1amIqk2gcCtCc
 I.PPM.PM09WUgdV3DkRqk468eGEGrkiai3YaJijFc8rreqmCKu0Gc8qrWLE8qwIdi2YHZiVphg
 hgt3YLBgmpgj7N,d8HVE,U1NPVPRdPNRONl9RbON99N,78hOEZ86bPN99Np76H0M8rN1Cobuod
 Gp4ak2qqumKuaKsmqoKKt0mS0GOWHNSnMin4AVhxhYhighin3Yx2YmAaowao2bnoaowavgV7AV
 lhijZidhgiZiUgbUghjZgp,7OGh86PPRN9R.rN1HM0ZPNPPMHfP7PNg5P1kayIW0mqKLq.UKl4
 6PTvRN76FPODHR0mY.i130q.66pND,tQ9PN0mayIWAipxho,rN12hdxgc3Yug5U2BdKNQfvP.s
 Q9PN7HRMPf9P.0GJ0Gqyqv0mK0GtKqq44EJ2hdxArN1HkYsQ91tND,7A.HeH588bPN9HK0mqyK
 mUd2Y3pd2h,kVgBf1.in4qk2.I88JrGqYuKu0GIO3C5e1G38ZUohu2Y7p7kIeX7,QbBsE..2Yx
 ..UnFmmooqqoGLEqHE.QbBAV0,,,EM0GS0GrmGE8HM661uIb0uaw2YnhgZ,YZUIalAZvg,CYh3
 ip,km2ZnhgZN8rN1I8UH3dDJeI3Z3pdIBd3JecQiZhA,t9,NPT12Ye2YiBZdgV7g6IeiZAQ5P.
 UGVVphYxhhBhuhgU2ZDheI3YnhAe1UGBZvEf.7PMIbUYcVZiZRiiYcVZiZR5HM0dPOPPNp7670
 bHeaqqQbBA,HfC,,kRcEk46F19R9X5hgoZcVZCdOOPPNF7N1Xg2YoBBamRq.FFEKYV3inhgY32
 HXUYCHXthgVJiUAhitQ9vMTfP7vQ,d8qU7QCGKEe1ldBd7AV76J767OMQC7mwWGm44H76L76bd
 BV7A,d8Groqai2hjhim3Yf2Yq2aUIZU.qqouquGrm0mJ0GuaqqsQ9vMTXvgV7cFTeI,NO,dCvF
 M0GeyIESHEGob0mVyqq.UZ78kI0mWu2.1fP.rN1PM103Ed6J9vQdvF9fPjOOVPNJtCPM050A,4
 a7ZiZhBqXsAatIaUI3XtA,7FOZnQbBEf.19PNfPfPPbfC0pba283AcGJe,BfUwd43Y7p7SYGV7
 ohphhnhinhgYJbU.UBAV72eG,kXKKrKKt4KuKKEWmIeHEuYYtCcJ10aEnmGEuKR00.aU72jYhA
 WKKohYhgkFR..IijFR.UnFme1UGl4M0V0.cHfPP,78HV7,k2cE90,dI98Jf0ZeP7Hr2ZnhAmWB
 BcMNGR8JkI0mK0mMOnIqk2MFsF9fPsCPM1HEVUBUGBgi,2ZnhgZN8r,CJuG4umdGLtaKrSKI8m
 nKaZVdpB3N8r76b8R71aIrGLIqqkWrYUdQbBA,.Q8.,dPT9NCrR0mtKqmIbWAZv22.H0b1HFEC
 3EauqRqk2cHMMN9PRXnZZUghV3D.ErkuEEe1iHEWLmKKs66UBA,850GRsQu4sC,78Jlm2ioBDg
 Ae0AV4Va3Yug5V76MP19SUUgZUAaUYcD,HcI98I9OEd86R96pNDSomo7WmI0meuIeaIa0GXa4F
 dQTXg2YiBZUgbUod7ZdvgV7k28500a29fQW0Y3Q5M0FVqBggBBH9Rn9659O9Xn3YeA3M010cFH
 fP.EECGEu2HtCP.HcJ111Xc.HtCP.HMMUnRfihihRipVR3Yug5RvCP.HMGRWihih,amRq.aEI6
 QZnn8rmCrt0GmKrq0LEemIU7ohYhgk,gdV,2Zm,U7Ad4dP7PN66x76l9N9Hu6JFWBU76S.pViZ
 gZVvM0A,b0MGcPfPPQC66.C3.Ug.,7N99Q2YdRiWAZv.kYEwGqmkIiHE.Y7PM0AV3lR..42ErK
 5EEqHEAgsB7M8UH,Q8.DXZ,THECqrqaghgohguIYdQbB..H0R1kI.kd.22.66UU..MGMH19SUc
 .amR0md.mYv.ZGeUmVBAV7g600UZR5PUE,ULBhkhgU2ZmVu.amREf42sQYgu22R08pRA,H6SUg
 6SPPMl9N.R9NER..ohg2YdZgsJbUA7.cEEE42EtEECWC,M0ZOM..Hl4kd.C3UrBhkBBDvCC5eH
 FQbU.MGsQM800UA,2DEEe1P0EIUdQbU2jhBAUUUsZgZVv.j0kroZg,CWk6FU7A78Jr.EKIad2Y
 x6A27U7cP,dCvFdu4.MH.kIUq.HM098Hk2A,10cP.0mF0WdQ5M0aKmWLEenS..cPfPPUdkU.aK
 mWLEmHEgC.q.aUi,19PN1ipoGKwqpRqk2M0GoWcPfXp,U7MG2ZihCUU.,d7AhYlFohphBkI0Ge
 .A,44khUUI544UiltK5qp4ak2A,9eHq.HM09Wv.HMGocdpBUgkI.0GeW2k2IC2YuEWYB2369sC
 k2oeV,.aWBU7cP7Hs66MH.W0.A,HWiFs66t76l9N91G3U7Ew.e1R1Q5M0Q8U7Vi,bXdQbUQ8UH
 ,66kt.,,2Yd,.A72DkI.Eag,A,9WBU7g6i1.kd.C3Ur,0mlgBEL8mIi1.NmRU,,IC2YxsQ.a0H
 MF2YLBhkhgvg,8oWk4sJH9Q998DONR12ZdAZB.GpmCLukfMNrVBIc3x668JltKKr.,7O1vQmaq
 VkYZUAgillW485,7QTPOR9RbHuMOdvQ91JN8od3ltKKr.HtCCrmu4c9NPNBHEkt.Q5bPN.RdQH
 1,,.gV3pd2tGd9OcQKqd.Rl4qE,iIuWqU..GpmCLu.gV0CyIhACoruKu8rrmKqKKtCLLCZYRco
 JigZcZRiX3UlbeZ3D.UiQcjpho,YcZF.Q6AgdphZJinp3cQ...sQR,.G20EtH.,6.636.M00E.
 0E..k.8ssH38pumqm8rtumdcIf9PY62Ulb8.CLL8pumqmY62UmT.2U.kJl12U.QI,E.0U1CSW5
 ktumdsIdPSNPN7ONbvM,Mw.ELMSN12Um5V.2U.2..FU.If.E.0.3Qw.EL4IuIC3HuQi2hA59.G
 .0..676.16.0U.UUQoOF.2U4Ax,cqVH.4.U.2.8Mtv.,E..UO.,.1.eG.mb,6.2UEC.6..ONj1
 E.ONj7bPAM,68hAU0E.7.U0CyHZiYZcjNRPPNQiiQcj,.E80U.2..E2E.UA6.,6.,uKbXNKI,A
 zJE.nD,iLFH.nt9,vy1...
 --- end of encoding ---

enjoy, and happy hacking!

лицензия, если вам это зачем-то надо — WTFPL.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 09 Март, 2023 20:39 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
вообще, хочу заметить, что по простоте и мощи эта штука очень перекликается с обероном. так же, как и оберон — выдумать её было не очень тривиально, но уже готовую можно просто использовать. по факту, весь нужный код можно просто запомнить (как я и сделал), и потом по памяти вставлять в проекты.

то есть, нет никакой причины НЕ использовать сбалансированое двоичное дерево место обычного; даже простейшая рекурсивная реализация «по учебнику» в силу сбалансированости гарантирует мизерную максимальную глубину рекурсии. если мы уже втыкаем двоичное дерево для скорости, то имеет смысл добавить туда тривиальную защиту от вырожденых случаев: в коде сложно ошибиться, его — в силу объёма — можно просто вызубрить, как стишок. и не надо таскать с собой никаких библиотек для сбалансированых деревьев.

мне кажется, AAtree должно входить в джентльменский набор паттернов любого оберонщика: и как полезная на практике штука, и как ещё одна демонстрация того, что простота — залог здоровья, хорошего пищеварения и приятного цвета лица.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 09 Март, 2023 23:56 

Зарегистрирован: Четверг, 08 Май, 2008 19:13
Сообщения: 1462
Откуда: Киев
Спасибо, что обратили внимание.

Файлы у меня почему-то не распаковываются.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 10 Март, 2023 00:39 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
Comdiv писал(а):
Файлы у меня почему-то не распаковываются.
это не подсистемы, а просто два документа, их надо через Tools -> Decode просто. я только что проверил — у меня распаковалось.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 10 Март, 2023 00:43 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
но на всякий случай вот аттачи с обоими документами.


Вложения:
AATree.odc [17.61 КБ]
Скачиваний: 236
AATreeSimple.odc [15.41 КБ]
Скачиваний: 212
Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 10 Март, 2023 00:54 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
хочу уточнить свой первый пост: в очень неудачных случаях «всё сортировано» высота иногда будет больше, чем log(N), потенциально до 2*log(N). это всё ещё лучше, чем N для простых бинарных. и при активном добавлении элементов дерево быстро «уплощается» обратно до примерно 1.5*log(N). плата за простоту реализации.

p.s.: и да, если добавить в ноды parent (указатель на ноду-родителя), то можно вообще без рекурсии обойтись. код, правда, усложнится рихтовкой парентов и взбиранием обратно по ним. вот это вы все точно напишете сами, если захотите: алгоритм тот же самый, что и у рекурсии, только чуть более грязный. хотя я, признаться, не вижу особого смысла заморачиваться: ну, максимальная глубина рекурсии в районе 64 вызовов для дерева с 2^32 элементов. кого реально это парит?

впрочем, удобство parent в том, что можно делать обход дерева в любом направлении за O(1) без дополнительного стека. опять же, это есть в любом учебнике по структурам данных.

позже причешу и выложу реализацию ranges на этой штуке. фактически, это массивы с амортизированым временем O(log N) на добавление, удаление и поиск. то, на чём я хочу переписать TextModels. если хотите хинт, то: в ноде надо хранить размер левого поддерева, и рихтовать его в процессе балансировки. можно делать как классические массивы, так и массивы, где одна нода покрывает больше одного элемента (удобно для хранения attribute runs в редакторе, например). а классические, например, использовать для хранения начальных позиций строк — за счёт быстрой вставки и удаления, а также O(1) перебора это получается шустро и сердито.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 09 Январь, 2024 09:03 

Зарегистрирован: Воскресенье, 25 Декабрь, 2022 23:14
Сообщения: 1540
кстати, Сэджвик на основе идеи Андерссона сделал такое же упрощение для красно-чёрных деревьев. в принципе, red-black чуть-чуть лучше при активных мутациях (бают, что меньше вращений надо), и для буккипинга можно обойтись всего одним битом вместо байта. в оберонах это без толку, потому что использовать младший бит указателя для хранения цвета не выйдет, а вот для какой-нибудь сишечки может быть вполне удобно.

лично я пока остаюсь с AA, потому что во-первых, я к ним привык, во-вторых, они у меня уже написаны, а новое КЦ опять проверять надо. но вы бумажку всё равно почитайте, Сэджвик даже код для удаления там даёт (что, тащемта, весьма редкое явление для теоретических статей, гыг).


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB