Tema: Izbe-izlikler, oplamlar, terekler, grafikalar hám basqalardı kórsetiw Jobası

Terekti ekranda shıǵarıw funksiyası
void avltree_print_dfs(struct avltree *tree, int level)
{ int i;
if (tree == NULL) return;
for (i = 0; i < level; i++) printf(" ");
printf("%d\n", tree->key);
avltree_print_dfs(tree->left, level + 1);
avltree_print_dfs(tree->right, level + 1);
}
int main()
{ struct avltree *tree = NULL;
tree = avltree_add(tree, 5, "5");
tree = avltree_add(tree, 3, "3"); /* Code */ avltree_free(tree); return 0;
}
B tereki (anglichan B-tree) - izlew, qosıw hám óshiriw imkaniyatın beretuǵın, júdá kópshoxli teń salmaqlılıqlasqan qıdırıw tereki. Túyinleri n bolǵan B tereki O (logn) biyiklikke iye bo‗ladi. Túyin shaqları sanı birden bir neshe mıńǵasha bolıwı múmkin (ádetde, B-terekiniń shoxlanish dárejesi terek isleytuǵın qurılma (disklar ) qásiyetleri menen belgilenedi).
B-terekler O (logn) kóp dinamikalıq jıynaq ámellerin waqıtında orınlaw ushın da isletiliwi múmkin. B tereki birinshi ret 1970-jılda R. Bayer hám E. Makkreyt tárepinen usınıs etilgen. B terek strukturası. B tereki jetilisken teń salmaqlılıqlasqan, yaǵnıy onıń barlıq japıraqlarınıń tereńligi birdey. B tereki tómendegi ayrıqshalıqlarǵa iye ( t - bul terek parametrleri, B terekiniń minimal dárejesi dep ataladı, 2 den kem emes ):
• Túbirden tısqarı hár bir túyin hesh bolmaǵanda t-1 giltni óz ishine aladı hám hár bir ishki túyin keminde áwladlı t túyinlerge iye. Eger terek bos bolmasa, túbirde keminde bir gilt bolıwı kerek.
• Hár bir túyin, túbirden tısqarı, ishki túyinlerde kópi menen 2 t - 1 giltni hám kópi menen 2 t áwladtı óz ishine aladı
• Túbirde terek bos bolmasa birden 2 t-1 ge shekem gilt hám biyikligi 0 den úlken bolsa 2 den 2 t ge shekem áwladtı óz ishine aladı.
• Terektiń hár bir túyininde k1,.. ., kn giltleri bolǵan japıraqlardan tısqarı n + 1 áwladları bar. i-áwladta [ki-1; ki], k0 = -∞, kn+1 =∞ kesindiniń giltleri bar.
• Hár bir túyindiń giltleri kamaymaydigan tártipte tártiplengen.
• Barlıq japıraqlar birdey dárejede. B terekler disklarda (fayl sistemalarında ) yamasa basqa tuwrıdan-tuwrı kiretuǵın bolmaǵan saqlaw ortalıqlarında, sonıń menen birge, maǵlıwmatlar bazalarında paydalanıw ushın mólsherlengen. B terekler qızıl -qara tereklerge uqsaydı, lekin olar disktı oqıw/yozish ámellerin minimallastırıwda jaqsılaw esaplanadı.
Terekler - bul dinamikalıq jıynaq ámellerdi atqaratuǵın maǵlıwmatlar strukturaları. Bunday ámeller retinde elementti qıdırıw, minimal (maksimal ) elementti qıdırıw, kirgiziw, óshiriw, áwlad -ájdadga ótiw, áwladqa ótiw sıyaqlılardı keltiriw múmkin. Sonday etip, terek ápiwayı sózlik retinde de, ústivor gezek retinde de isletiliwi múmkin. Terekler degi tiykarǵı ámeller onıń biyikligine proporcional waqıtta atqarıladı. Teń salmaqlılıqlasqan terekler olardıń biyikligin azaytadı (mısalı, túyinleri bolǵan ekilik teń salmaqlılıqlı terektiń biyikligi logn). Bul standart qıdırıw tereklerinde qanday mashqala bar? Aldınǵı temalarda aytıp ótilgen tereklerden biri suwretlengen úlken maǵlıwmatlar bazasın kórip shıǵayıq. Shubhasız, bul tereklerdiń barlıǵın operativ yadta saqlay almaymız - maǵlıwmatlardıń tek bir bólegin saqlaymiz, qalǵanları úshinshi tárep jardeminde saqlanadı (mısalı, kirisiw tezligi talay tómen bolǵan qattı diskta ). Qızıl -qara yamasa Dekart sıyaqlı terekler úshinshi tárep qurallarına kirisiwdi talap etedi. Úlken n lar ushın bul júdá kóp. Áyne mine sol mashqala B terekler sheshiw imkaniyatın beredi. B terekleri de teń salmaqlılıqlasqan terekler bolıp tabıladı, sol sebepli standart ámellerdi orınlaw ushın waqıt biyiklikke proporcional. Biraq, basqa tereklerden ayrıqsha bolıp esaplanıw, olar arnawlı disk yadı menen islew ushın jaratılǵan (aldınǵı mısalda - úshinshi tárep taratıwshı ), anıqrog'i olar kirisiw -shıǵıw túrindegi shaqırıwlardı azaytadı. 10. 2. B terekte ámeller B terekte izlew algoritmı. Joqarıda aytıp ótilgeni sıyaqlı, B tereki barlıq standart qıdırıw, qosıw, óshiriw hám taǵı basqa ámellerdi atqaradı. B terekinde izlew binar terekti qıdırıwǵa júdá uqsaydı, tek bul jerde biz áwladqa joldı 2 varianttan emes, bálki bir neshe varianttan tańlawımız kerek. Keri jaǵdayda, parqı bolmay qaladı. Tómendegi 46 -suwretde 27-giltni qıdırıw kórsetilgen. Suwretti kórip shıǵayıq (hám soǵan uyqas túrde standart qıdırıw algoritmı ):
• Biz túbir giltlerin kerek bolaman degenge shekem ótemiz. Bul halda 31 ge jettik.
• Bul giltning shep tárepindegi áwladqa tushamiz.
• 27 den kishi bo'lgunga shekem jańa túyindi gilt boyınsha izleymiz. Bunday halda, biz 27 ni taptık hám tóqtadık.
B tereklerde element qosıw. Izlewden ayrıqsha bolıp esaplanıw, qosıw usılı ekilik terekke qaraǵanda talay quramalı, sebebi jańa japıraq jaratıw hám oǵan gilt qoyıw múmkin emes, sebebi B terekiniń qásiyetleri buz'ladı. Giltni qashannan berli toldırılǵan bargga kirgiziw múmkin emes. Túyindi ekige bolıw ámeli kerek, eger japıraq toldırılǵan bolsa, ol jaǵdayda 2 t-1 gilt bar edi. 2 ge t-1 ge bólemiz odan kem giltler hám aqırǵı t-1 ájdad túyinine ótkeriledi. Soǵan kóre, eger áwlad -ájdad túyini de tolǵan bolsa, taǵı bolıwımız kerek hám soǵan uqsas túbirge shekem (eger túbir bóleklengen bolsa, ol jaǵdayda jańa túbir payda boladı hám terek tereńligi asadı ). Ápiwayı ekilik terekler sıyaqlı, jaylastırıw da túbirden barggacha bir ótiwde ámelge asıriladı. Hár bir iteratsiyada (jańa gilt ushın poziciyanı qıdırıwda - túbirden barggacha) ótetuǵın barlıq toldırılǵan túyinlerdi ajratamız (bargni da óz ishine alǵan halda ). Sonday etip, eger nátiyjede túyindi ajıratıw zárúr bolsa, onıń áwlad -ájdadi toldırilmaganligiga kóriwimiz múmkin.
Element óshiriw. Giltni B tereginen alıp taslaw, oǵan element qosıwdan da quramalı esaplanadı. Óytkeni sonda, ishki túyindi alıp taslaw terekti ulıwma qayta qayta tiklewdi talap etedi. Element qosıwǵa uqsap, biz B terektiń qásiyetlerin saqlaganligimizni tekseriwimiz kerek, tek bul halda biz giltlerdiń t-1 bolıwın baqlawımız kerek (yaǵnıy, eger bul túyinnen gilt óshirilse, túyin ámeldegi bola almaydı ). Óshiriw algoritmın kórip shıǵamız : 135 1) Eger bargdan óshiriw júz bolsa, ol jaǵdayda qansha gilt bar ekenin tekseriw kerek. Eger t-1 den kóp bolsa, biz jaysha óshirip taslaymiz hám basqa hesh nárse etiwimiz shárt emes. Keri jaǵdayda, egerde t-1 den artıq giltlerdi óz ishine alıwshı qońsılas japıraq bolsa (onıń janında jaylasqan hám áwlad -ájdadi birdey bolsa ), biz qońsılas túyindiń qalǵan giltleri arasındaǵı ajıratıwshı bolǵan bul qońsılastan giltni tańlaymiz. Bul gilt k1 bolsın. Aldın túyindi jáne onıń qońsılassın ajıratıwshı tiykarǵı túyinnen k2 giltini tańlaymiz. Kerekli giltni derek túyinnen alıp taslaylik (óshiriliwi kerek edi), bul túyinge k2 ni túsiriń hám ájdad túyinindegi k2 ornına k1 qoyıng. Túsinikli bolıwı ushın tómende " 9" tuymesi óshirilgen súwret (48-su'wret) kórsetilgen. Eger biziń túyindiń barlıq qońsılaslarında t-1 giltleri bolsa. Keyin biz onı qońsılassı menen birlestiremiz, kerekli giltni óshirip taslaymiz jáne bul eki " burınǵı" qońsılaslar ushın ajıratıwshı bolǵan áwlad -ájdad túyininiń gilti, jańa islengen túyinimizga ótemiz (bul, álbette, odaǵı mediana boladı ).
2) Endi x ishki túyininen k giltini alıp taslawdı kórip shıǵayıq. Eger k giltidan aldınǵı áwlad túyininde t -1 den artıq giltler bolsa, biz k1 ni tabamız - bul túyindiń tómengi terekinde k. Onı óshirip taslaymiz (Algoritmdı rekursiv tárzde jumısqa túsiremiz). Derek túyin degi k ni k1 menen almastıramız. Eger k giltidan keyingi áwlad túyininde t-1 den artıq gilt bolsa, biz da tap sonday jumıstı atqaramız. Eger ekewinde de (keyingi hám aldınǵı áwlad túyinlerinde) t-1 giltleri bolsa, biz bul áwladlardı birlestiremiz, k-ni olarǵa ótkeremiz, keyininen k-ni jańa túyinnen alıp taslaymiz (biz algoritmimizni rekursiv tárzde jumısqa 136 túsiremiz). Eger túbirdiń aqırǵı 2 áwladı birlesse, olar túbirge aylanadı hám aldınǵı túbir alıp taslanadı. Súwret tómende kórsetilgen (49 - súwret), bul jerde " 11" túbirden shiǵarıladı (keyingi túyinde t-1 áwladları kóp bolǵan jaǵday ). Óshiriw procesi O (t logt n) qosılıwı menen birdey waqtın aladı hám disk operatsiyaları tek O (h) talap etiledi, bul jerde h - terek biyikligi.
Esaplaw geometriyasi - geometriyalıq máselelerdi sheshiw algoritmları menen shuǵıllanatuǵın informatika bólimi. Bul úshmúyeshlik, qabarıq betlerdi qurıw, bir obiekttiń basqasına tiyisliligin anıqlaw, olardıń kesesiwin tabıw hám basqalar sıyaqlı wazıypalar menen shuǵıllanadı, olar geometriyalıq obiektler menen isleydi: noqat, segment, kópburchak, sheńber hám taǵı basqalar. Esaplaw geometriyasi kompyuter grafikalarında, injenerlik dizaynida hám basqa kóplegen geometriya tarawlarında qollanıladı.
X kompleksiniń qabarıq qabıǵı - X ni óz ishine alǵan eń kishi qabarıq kompleksi. " Eń kishi jıynaq" bul jerde jıynaqlardı jaylastırıwǵa salıstırǵanda eń kishi elementti, yaǵnıy berilgen nomerdi óz ishine alǵan sonday qabarıq jıynaqtı ańlatadıki, ol berilgen figurani óz ishine alǵan basqa hár qanday qabarıq jıynaqta bar. X kompleksiniń qabarıq denesi ádetde ConvX menen belgilenedi.