Fizika-matematika fakulteti

Amalga oshirish. Balanslash operatsiyalari daraxtni kiritish joyidan boshlab bajarilishi kerak, ularni bajarish bizning standart rekursiv amaliyotda rekursiv chaqiruvlardan keyin qilamiz. Oldingi xatboshida sanab o'tilgan uchta operatsiyani daraxtdagi ikkita tugunning ranglarini sinab ko'radigan bitta ifoda bilan bajarish mumkin. U oz miqdordagi kodni o'z ichiga olsa ham, uni amalga oshirish uchun biz ishlab chiqqan abstraktsiyaning ikki qatlamini (2-3 daraxt va qizil-qora BST) bilmasdan turib, uni amalga oshirishni tushunish juda qiyin bo'ladi. Uchdan beshgacha tugun ranglarini sinash uchun (va sinov muvaffaqiyatli bo'lganida aylanish yoki ikkita yoki ranglarni o'zgartirish) deyarli mukammal muvozanatga ega BSTlarni olamiz. Bizning standart indeksatsiyalash mijozimiz va ortib borayotgan tartibda kiritilgan xuddi shu kalitlar uchun izlar 24-rasmda keltirilgan.

public class RedBlackBST, Value>

{

private Node root;

private class Node //Rangli bitli BST tugun

private Boolean isRed(Node h)

private Node rotateLeft(Node h)

private Node rotateRight(Node h)

private void flipColors(Node h)

private int size()

public void put(Key key, Value val)

{ // kalitni qidirish. agar topilsa yangilanish qiymati;

root=put(root, key, val);

root.color=BLACK;

}

private Node put(Node h, Key key, Value val)

{

if(h==nul) //

return new Node (key, val, 1, RED);

int cmp=key.compareTo(h.key);

if(cmp<0) h.left=put(h.left, key, val);

else if(cmp>0) h.right=put(h.right, key, val)

else h.val=val;

if(isRed(h.right) && ! isRed(h.left)) h=rotateLeft(h);

if(isRed(h.left) && isRed(h.left.left)) h=rotateRight(h);

if(isRed(h.left) && isRed(h.right)) flipColors(h);

h.N=size(h.left)+size(h.right)+1;

return h;

}

}

Agar rekursiv chaqiruvlardan so'ng, daraxtda mukammal muvozanatni ta'minlaydigan 1-1 muvofiqlik saqlanib qolsa, qizil-qora BSTlar uchun rekursiv put() kodi elementar BSTlarda put() bilan bir xil.

24-rasm. Qizil-qora BST qurilish izlari.