Fizika-matematika fakulteti

C# dagi dastur:

using System; 
using System.Collections.Generic;  
//Ch # balanssiz BST ni muvozanatli BSTga aylantirish uchun C # dasturi  
/* Ikkilik daraxti tugunida ma'lumotlar, chap bolaga ko'rsatgich va o'ng bolaga ko'rsatgich mavjud*/
public class Node 
{ 
    public int data; 
    public Node left, right; 
    public Node(int data) 
    { 
        this.data = data; 
        left = right = null; 
    } 
}
public class BinaryTree 
{ 
    public Node root; 
    public virtual void storeBSTNodes(Node root, List nodes) 
    { 
        if (root == null) 
        { 
            return; 
        } 
        storeBSTNodes(root.left, nodes); 
        nodes.Add(root); 
        storeBSTNodes(root.right, nodes); 
    } 
    /*Ikkilik daraxtni qurish uchun rekursiv funktsiya*/
    public virtual Node buildTreeUtil(List nodes, int start, int end) 
    { 
        if (start > end) 
        { 
            return null; 
        } 
        /*O'rta elementni ildiz qilib olish */
        int mid = (start + end) / 2; 
        Node node = nodes[mid]; 
          node.left = buildTreeUtil(nodes, start, mid - 1); 
        node.right = buildTreeUtil(nodes, mid + 1, end); 
        return node; 
    } 
    // Ushbu funktsiyalar muvozanatsiz BSTni muvozanatli BST ga o'zgartiradi  
    public virtual Node buildTree(Node root) 
    { 
        // Berilgan BST tugunlarini saralangan tartibda saqlash  
        List nodes = new List(); 
        storeBSTNodes(root, nodes); 
        //  BST uchun nodes[]  strukturasi
        int n = nodes.Count; 
        return buildTreeUtil(nodes, 0, n - 1); 
    }
    /* Daraxtni oldindan buyurtib o'tishni amalga oshirish funktsiyasi */
    public virtual void preOrder(Node node) 
    { 
        if (node == null) 
        { 
            return; 
        } 
        Console.Write(node.data + " "); 
        preOrder(node.left); 
        preOrder(node.right); 
    } 
    // Yuqoridagi funktsiyalarni sinab ko'rish dasturi  
    public static void Main(string[] args) 
    { 
         /* Qurilgan  ikkilik daraxti  
                10  
               /  
              8  
             /  
            7  
           /  
          6  
         /  
        5   */
        BinaryTree tree = new BinaryTree(); 
        tree.root = new Node(10); 
        tree.root.left = new Node(8); 
        tree.root.left.left = new Node(7); 
        tree.root.left.left.left = new Node(6); 
        tree.root.left.left.left.left = new Node(5);
        tree.root = tree.buildTree(tree.root); 
        Console.WriteLine("Muvozanatlashgan BST oldindan e'lon qilish:"); 
        tree.preOrder(tree.root);
        Console.ReadKey();
    } 
} 

Natija:

2-§. Qizil-qora muvozanatlashgan daraxtlar.

Qizil-qora BSTlar, yuqorida tavsiflangan 2-3 daraxt uchun kiritish algoritmini tushunish qiyin emas; Endi buni amalga oshirish qiyin emasligini ko'ramiz. Tabiiy amalga oshirishga olib keladigan qizil-qora BST deb nomlanadigan oddiy tasvirni ko'rib chiqamiz: ko'p kod talab qilinmaydi, lekin kodni qanday va nima uchun bajarilishini tushunish diqqat bilan qarashni talab qiladi.

3-tugunlarni kodlash. Qizil-qora BSTlarning asosiy g'oyasi: odatiy BSTlardan (2 tugundan iborat) boshlab va 3-tugunlarni kodlash uchun qo'shimcha ma'lumot kiritish orqali 2-3 daraxtni kodlashdir. Bog'lanishlar ikki xil bo'lishi mumkin, deb o'ylaymiz: uchta tugunni ifodalash uchun ikkita 2 tugunni bir-biriga bog'laydigan qizil ulanishlar va 2-3 daraxtni bir-biriga bog'laydigan qora ulanishlar. Xususan, 3 ta tugunni chap tomonga suyanadigan bitta qizil ulanish orqali bog'langan ikkita 2 tugun sifatida ifodalaymiz (2 tugunning biri ikkinchisining chap bolasi). Bunday vakolatxonadan foydalanishning bir afzalligi shundaki, u bizning get () kodini BST-ning standart qidiruvida o'zgartirishlarsiz ishlatishga imkon beradi. Har qanday 2-3 daraxtni hisobga olsak, har bir tugunni belgilangan tartibda o'zgartirib, darhol tegishli BSTni olishimiz mumkin. Bu tarzda 2-3 ta daraxtni qizil-qora BST deb tasvirlaydigan BSTlarga murojaat qilamiz.

13-rasm. Chap tomonga burilgan qizil ulanish orqali ulangan ikkita 2 tugunli 3 tugunni kodlash.