Fizika-matematika fakulteti

private static final boolean RED=true;
        private static final boolean BLACK = true;
        private class Node
        {
            Key key;
            Value val;
            Node left, right;
            int N; 
            Boolean color;
            Node(Key key, Value val, int N, Boolean color)
            {
                this.key=key;
                this.val=val;
                this.N=N;
                this.color=color;
            }
        }
        private Boolean isRed(Node x)
        {
            if (x==null) return false;
            return x.color==RED; 
        }

Burilishlar. Ko'rib chiqadigan amalga oshirish operatsiya davomida qizil yo'nalishlarga yoki ketma-ket ikkita qizil havolalarga ega bo'lishiga imkon berishi mumkin, ammo u qizil shartli yo'nalishlarni o'zgartiradigan aylanish deb nomlangan operatsiyadan oqilona foydalanish orqali bajarilishidan oldin har doim ushbu shartlarni tuzatadi. Birinchidan, chap tomonga egilish uchun burilish kerak bo'lgan o'ngga egilgan qizil ulanish bor deylik (chapdagi diagramaga qarang). Ushbu operatsiya chap burilish deb ataladi. Biz hisoblashni qizil-qora BST bilan bog'lanishni argument sifatida qabul qiladigan usul sifatida tashkil qilamiz va ushbu ulanishni h tugun bilan bog'lanishini h deb hisoblaymiz, agar u to'g'ri ulanishi qizil bo'lsa, kerakli sozlashlarni amalga oshiradi va tugunga havolani qaytaradi. Chap havola qizil bo'lgan bir xil tugmalar to'plami uchun qizil-qora BSTning ildizi. Agar diagrammadagi chizmalardan kodlarning har bir satrini tekshirsak, ushbu operatsiyani oson ekanligini tushunamiz: ildizda ikkita tugmachaning kichigi bo'lishidan ikkitasining kattaligiga o'tish. Chap tomonga burilgan qizil ulanishni o'ng tomonga burilib, chapga va o'ngga bir-biriga almashtirilgan bir xil kodni tashkil qiladi (quyida joylashgan diagramaga qarang).

18-rasm.

Chapga burilish (h ning o'ng tomoni) O'ngga burilish (h ning chap burchagi)