Axborot texnologiyalari universiteti urganch filiali kompuyuter injineringi fakulteti kompyuter injieringi yo

Daraxtga qo'shilish
Endi yangi (a, b) kalit / qiymat juftligini qo'shish operatsiyasini bajarishga harakat qilaylik. Buni amalga oshirish uchun biz xuddi shu kalit bilan tepalik topgunimizcha yoki yo'qolgan o'g'ilga etib bormagunimizcha get funktsiyasidagi kabi daraxtdan pastga tushamiz. Agar biz bir xil tugmachali tepalikni topsak, unda biz shunchaki mos keladigan qiymatni o'zgartiramiz. Aks holda, tartibni buzmaslik uchun yangi vertikalni aynan shu joyda kiritish kerakligini tushunish oson. Oldingi rasmda daraxtga 42 kalitni kiritishni o'ylab ko'ring:

Kod:

add :: Ord key => BSTree key value -> key -> value -> BSTree key value

add Leaf k v = Branch k v Leaf Leaf

add (Branch key value left right) k v

| k < key = Branch key value (add left k v) right

| k > key = Branch key value left (add right k v)

| k == key = Branch key value left right

public void add(T1 k, T2 v) {

Node x = root, y = null;

while (x != null) {

int cmp = k.compareTo(x.key);

if (cmp == 0) {

x.value = v;

return;

} else {

y = x;

if (cmp < 0) {

x = x.left;

} else {

x = x.right;

}

}

}

Node newNode = new Node(k, v);

if (y == null) {

root = newNode;

} else {

if (k.compareTo(y.key) < 0) {

y.left = newNode;

} else {

y.right = newNode;

}

}

}

Funktsional yondashuvning ijobiy va salbiy tomonlariga lirik ekskursiya. Agar ikkala tilda keltirilgan misollarni sinchkovlik bilan ko'rib chiqsangiz, funktsional va majburiy dasturlarning xatti-harakatlarida bir oz farq borligini ko'rishingiz mumkin: agar java-da biz shunchaki mavjud tepalardagi ma'lumotlar va ma'lumotnomalarni o'zgartirsak, u holda haskell versiyasi rekursiya bosib o'tgan butun yo'l bo'ylab yangi tepaliklarni yaratadi. Bu buzg'unchi topshiriqlarni faqat funktsional tillarda bajarish mumkin emasligi bilan bog'liq. Shubhasiz, bu ish faoliyatini pasaytiradi va xotira sarfini oshiradi. Boshqa tomondan, ushbu yondashuvning ijobiy tomonlari mavjud: nojo'ya ta'sirlarning yo'qligi dasturning qanday ishlashini tushunishni ancha osonlashtiradi. Bu haqda ko'proq ma'lumotni deyarli har qanday darslikda yoki funktsional dasturlash bo'yicha kirish maqolasida o'qishingiz mumkin. Xuddi shu maqolada men funktsional yondashuvning yana bir natijasiga e'tibor qaratmoqchiman: daraxtga yangi element qo'shilgandan keyin ham eski versiya mavjud bo'lib qoladi! Ushbu ta'sir tufayli arqonlar ishlaydi, shu jumladan imperativ tillarda amalga oshiriladi, bu sizga an'anaviy yondashuvga qaraganda asimptotik tezroq operatsiyalar bilan satrlarni amalga oshirishga imkon beradi. Arqonlar haqida keyingi maqolalardan birida gaplashaman. Endi biz ushbu maqoladagi eng qiyin operatsiyani boshlaymiz - daraxtdan x kalitini olib tashlash. Avvalo, biz avvalgidek daraxtda o'z vertikalimizni topamiz. Endi ikkita holat yuzaga keladi. 1-holat (5-raqamni o'chirish):

Ko'rinib turibdiki, o'chirilgan tepalikning o'ng o'g'li yo'q. Keyin biz uni olib tashlaymiz va buyurtmani buzmasdan uning o'rniga chap pastki daraxtni qo'shib qo'yishimiz mumkin:

Agar o'ng o'g'il bo'lsa, bizda 2-holat bor (biz yana 5-vertexni o'chirib tashlaymiz, lekin biroz boshqacha daraxtdan):

Bu erda bu qadar oson ishlamaydi - chap o'g'il allaqachon o'ng o'g'il ko'rishi mumkin. Keling, boshqacha qilaylik: to'g'ri subtree-da minimalni toping. Agar o'ng o'g'lingizdan boshlasangiz va chap tomonga o'tsangiz, buni topish mumkinligi aniq. Topilgan minimal chap o'g'li bo'lmaganligi sababli, biz uni 1-holatga o'xshashlik bilan kesib, olib tashlangan tepalik o'rniga qo'shishimiz mumkin. To'g'ri subtree-da minimal bo'lganligi sababli, buyurtma mulki buzilmaydi:

O'chirishni amalga oshirish:

remove :: Ord key => BSTree key value -> key -> BSTree key value

remove Leaf _ = Leaf

remove (Branch key value left right) k

| k < key = Branch key value (remove left k) right

| k > key = Branch key value left (remove right k)

| k == key = if isLeaf right

then left

else Branch leftmostA leftmostB left right'

where

isLeaf Leaf = True

isLeaf _ = False

((leftmostA, leftmostB), right') = deleteLeftmost right

deleteLeftmost (Branch key value Leaf right) = ((key, value), right)

deleteLeftmost (Branch key value left right) = (pair, Branch key value left' right)

where (pair, left') = deleteLeftmost left

public void remove(T1 k) {

Node x = root, y = null;

while (x != null) {

int cmp = k.compareTo(x.key);

if (cmp == 0) {

break;

} else {

y = x;

if (cmp < 0) {

x = x.left;

} else {

x = x.right;

}

}

}

if (x == null) {

return;

}

if (x.right == null) {

if (y == null) {

root = x.left;

} else {

if (x == y.left) {

y.left = x.left;

} else {

y.right = x.left;

}

}

} else {

Node leftMost = x.right;

y = null;

while (leftMost.left != null) {

y = leftMost;

leftMost = leftMost.left;

}

if (y != null) {

y.left = leftMost.right;

} else {

x.right = leftMost.right;

}

x.key = leftMost.key;

x.value = leftMost.value;

}

}
Shirinlik uchun men sinash uchun foydalangan ikkita funktsiya:
fromList :: Ord key => [(key, value)] -> BSTree key value

fromList = foldr (\(key, value) tree -> add tree key value) Leaf

toList :: Ord key => BSTree key value -> [(key, value)]

toList tree = toList' tree []

where

toList' Leaf list = list

toList' (Branch key value left right) list = toList' left ((key, value):(toList' left list))

Nima uchun bularning barchasi foydali?

[(Key, value)] juftliklarining ro'yxatini shunchaki saqlashingiz mumkin bo'lsa, o'quvchi nima uchun bunday asoratlar zarur deb o'ylashi mumkin. Javob oddiy - daraxt operatsiyalari tezroq. Ro'yxat sifatida amalga oshirilganda barcha funktsiyalar O (n) amallarini talab qiladi, bu erda n - bu strukturaning kattaligi. (O (f (n)) yozuv "f (n) ga mutanosib" degan ma'noni anglatadi, aniqroq tavsif va tafsilotlarni bu erda o'qish mumkin). Daraxt bilan ishlash O (h) da ishlaydi, bu erda h - daraxtning maksimal chuqurligi (chuqurlik - ildizdan tepaga masofa). Optimal holatda, barcha barglarning chuqurligi bir xil bo'lganda, daraxt n = 2 ^ h tepaliklarga ega bo'ladi. Demak, eng maqbul darajaga yaqin daraxtlardagi operatsiyalarning murakkabligi O (log (n)) bo'ladi. Afsuski, eng yomon holatda, daraxt buzilib ketishi mumkin va operatsiyalarning murakkabligi ro'yxatdagidek bo'ladi, masalan, bunday daraxtda (agar siz 1..n raqamlarini tartibda qo'shsangiz chiqadi):

Yaxshiyamki, daraxtni amalga oshirishning yo'llari bor, shunda daraxtning optimal chuqurligi saqlanib qoladi. har qanday operatsiyalar ketma-ketligi. Bunday daraxtlar muvozanatli deb nomlanadi. Bularga, masalan, qizil-qora daraxtlar, AVL daraxtlari, splay daraxtlari va boshqalar kiradi. Keyingi bo'limlarning e'lonlari

Keyingi maqolada har xil muvozanatli daraxtlar, ularning ijobiy va salbiy tomonlari haqida qisqacha ma'lumot beraman. Keyingi maqolalarda men ba'zi (ehtimol bir nechta) haqida batafsilroq va amalga oshirish haqida gaplashaman. Shundan so'ng, men arqonlarni va boshqa muvozanatlashtirilgan daraxtlarni kengaytirish va ulardan foydalanishni ko'rib chiqaman.