tree - هياكل - كيف يتم بناء الأشجار الثنائية الكبيرة؟




هياكل البيانات الشجرية (2)

هناك. نوث يعطي خوارزمية لبناء ثنائي متوازن بشكل معقول من المدخلات فرزها ، في حجم أكب الثالث أعتقد.

هذا هو السؤال الذي يزعجني لسنوات. أريد أن أعرف كيف بنيت الأشجار الثنائية الكبيرة، والطريقة الوحيدة التي أعرفها هو إنشاء وظيفة لدفع عنصر واحد على شجرة (وظيفة تسمى إدراج ()؛). إذا كان لدي شجرة عنصر 3 وتريد إضافة 5 عناصر، وانا ذاهب الى استدعاء وظيفة إدراج 5 مرات. هذا يبدو طريقة سيئة جدا، ماذا لو أردت إضافة 50 عنصرا؟ يجب أن يكون هناك طريقة أفضل من مجرد استدعاء وظيفة إدراج () خمسين مرة.


إذا تم فرز البيانات مسبقا يمكنك بناء عليه بشكل متكرر.

أساسا لبناء شجرة لبعض المدخلات:

  1. إنشاء عقدة جديدة
  2. إذا كان الإدخال إدخال واحد فقط، فإن قيمة العقدة هي هذا الإدخال
  3. غير ذلك:
    1. في الشجرة الفرعية اليسرى للعقدة، ضع الشجرة التي بنيت من النصف الأول من الإدخال
    2. في الشجرة الفرعية اليمنى للعقدة، ضع الشجرة المبنية من النصف الثاني من الإدخال

الخطوة الثالثة سوف تطبق بشكل متكرر نفسها على أجزاء من المدخلات.

إليك بعض الرموز الزائفة:

FUNCTION TREE (input -> node)
    IF input IS 1 ENTRY
        VALUE OF node IS entry OF input
    ELSE
        SPLIT input IN 2
        LEFT SUB-TREE OF node IS TREE(FIRST HALF OF input)
        RIGHT SUB-TREE OF node IS TREE(SECOND HALF OF input)

وإليك بعض لينباد C # رمز يمكنك تجربة مع:

// Add the following two using-directives to LINQPad:
// System.Drawing
// System.Drawing.Imaging

static Bitmap _Dummy = new Bitmap(16, 16, PixelFormat.Format24bppRgb);
static Font _Font = new Font("Arial", 12);

void Main()
{
    var sorted = Enumerable.Range(1, 16).ToArray();
    var tree = BuildTree(sorted);
    Visualize(tree);
}

public Node<T> BuildTree<T>(T[] input)
{
    return BuildTree<T>(input, 0, input.Length);
}

public Node<T> BuildTree<T>(T[] input, int left, int right)
{
    if (right <= left)
        return null;

    if (right == left + 1)
        return new Node<T> { Value = input[left] };

    int middle = (left + right) / 2;
    return new Node<T>
    {
        Left = BuildTree<T>(input, left, middle),
        Right = BuildTree<T>(input, middle, right)
    };
}

public class Node<T>
{
    public T Value;
    public Node<T> Left;
    public Node<T> Right;

    public Bitmap ToBitmap()
    {
        Size valueSize;
        using (Graphics g = Graphics.FromImage(_Dummy))
        {
            var tempSize = g.MeasureString(Value.ToString(), _Font);
            valueSize = new Size((int)tempSize.Width + 4, (int)tempSize.Height + 4);
        }

        Bitmap bitmap;
        Color valueColor = Color.LightPink;
        if (Left == null && Right == null)
        {
            bitmap = new Bitmap(valueSize.Width, valueSize.Height);
            using (var g = Graphics.FromImage(bitmap))
                g.Clear(Color.White);
            valueColor = Color.LightGreen;
        }
        else
        {
            using (var leftBitmap = Left.ToBitmap())
            using (var rightBitmap = Right.ToBitmap())
            {
                int subNodeHeight = Math.Max(leftBitmap.Height, rightBitmap.Height);
                bitmap = new Bitmap(
                    leftBitmap.Width + rightBitmap.Width + valueSize.Width,
                    valueSize.Height + 32 + subNodeHeight);

                using (var g = Graphics.FromImage(bitmap))
                {
                    g.Clear(Color.White);
                    int baseY  = valueSize.Height + 32;

                    int leftTop = baseY; // + (subNodeHeight - leftBitmap.Height) / 2;
                    g.DrawImage(leftBitmap, 0, leftTop);

                    int rightTop = baseY; // + (subNodeHeight - rightBitmap.Height) / 2;
                    g.DrawImage(rightBitmap, bitmap.Width - rightBitmap.Width, rightTop);

                    g.DrawLine(Pens.Black, bitmap.Width / 2 - 4, valueSize.Height, leftBitmap.Width / 2, leftTop);
                    g.DrawLine(Pens.Black, bitmap.Width / 2 + 4, valueSize.Height, bitmap.Width - rightBitmap.Width / 2, rightTop);
                }
            }
        }

        using (var g = Graphics.FromImage(bitmap))
        {
            float x = (bitmap.Width - valueSize.Width) / 2;
            using (var b = new SolidBrush(valueColor))
                g.FillRectangle(b, x, 0, valueSize.Width - 1, valueSize.Height - 1);
            g.DrawRectangle(Pens.Black, x, 0, valueSize.Width - 1, valueSize.Height - 1);
            if (Left == null && Right == null)
                g.DrawString(Value.ToString(), _Font, Brushes.Black, x + 1, 2);
        }

        return bitmap;
    }
}

void Visualize<T>(Node<T> node)
{
    node.ToBitmap().Dump();
}

وإليك الإخراج: