نحوه پیمایش درخت دودویی

این درخت پیمایش‌های گوناگونی دارد ولی سه تای آن‌ها اصلی‌تر و مهمتر هستند:

In-order یا LVR (چپ، ریشه، راست): در این حالت ابتدا گره‌های سمت چپ ملاقات (چاپ) می‌شوند و سپس ریشه و بعد گره‌های سمت راست.

Pre-Order یا VLR (ریشه، چپ، راست) : در این حالت ابتدا گره‌های ریشه ملاقات می‌شوند. بعد گره‌های سمت چپ و بعد گره‌های سمت راست.

Post_Order یا LRV (چپ، راست، ریشه ): در این حالت ابتدا گره‌های سمت چپ، بعد راست و نهایتا ریشه، ملاقات می‌شوند.

حتما متوجه شده‌اید که منظور از v در اینجا ریشه است و با تغییر و جابجایی مکان این سه حرف RLV میتوانید به ترکیب‌های مختلفی از پیمایش دست پیدا کنید.

اجازه دهید روی شکل بالا پیمایش LVR را انجام دهیم: همانطور که گفتیم باید اول گره‌های سمت چپ را خواند، پس از 17 به سمت 9 حرکت می‌کنیم و می‌بینیم که 9، خود والد است. پس به سمت 6 حرکت می‌کنیم و می‌بینیم که فرزند چپی ندارد؛ پس خود 6 را ملاقات می‌کنیم، سپس فرزند راست را هم بررسی می‌کنیم که فرزند راستی ندارد پس کار ما اینجا تمام است و به سمت بالا حرکت می‌کنیم. 9 را ملاقات می‌کنیم و بعد عدد 5 را و به 17 بر می‌گردیم. 17 را ملاقات کرده و سپس به سمت 15 می‌رویم و الی آخر ...

6-9-5-17-8-15-10

VLR:

17-9-6-5-15-8-10

LRV:

6-5-9-8-10-15-17

نحوه پیاده سازی درخت دودویی:

public class BinaryTree<T>
{
    /// <summary>مقدار داخل گره</summary>
    public T Value { get; set; }
 
    /// <summary>فرزند چپ گره</summary>
    public BinaryTree<T> LeftChild { get; private set; }
 
    /// <summary>فرزند راست گره</summary>
    public BinaryTree<T> RightChild { get; private set; }
   
    /// <summary>سازنده کلاس</summary>
    /// <param name="value">مقدار گره</param>
    /// <param name="leftChild">فرزند چپ</param>
    /// <param name="rightChild">فرزند راست
    /// </param>
    public BinaryTree(T value,
        BinaryTree<T> leftChild, BinaryTree<T> rightChild)
    {
        this.Value = value;
        this.LeftChild = leftChild;
        this.RightChild = rightChild;
    }
 
    /// <summary>سازنده بدون فرزند
    /// </summary>
    /// <param name="value">the value of the tree node</param>
    public BinaryTree(T value) : this(value, null, null)
    {
    }
 
    /// <summary>‏‏‎LVR پیمایش</summary>
    public void PrintInOrder()
    {
        // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }
    }
}
 
/// <summary>
/// نحوه استفاده از کلاس بالا
/// </summary>
public class BinaryTreeExample
{
    static void Main()
    {
        BinaryTree<int> binaryTree =
            new BinaryTree<int>(14,
                    new BinaryTree<int>(19,
                          new BinaryTree<int>(23),
                          new BinaryTree<int>(6,
                                  new BinaryTree<int>(10),
                                  new BinaryTree<int>(21))),
                    new BinaryTree<int>(15,
                          new BinaryTree<int>(3),
                          null));
 
        binaryTree.PrintInOrder();
        Console.WriteLine();
 
        // خروجی
        // 23 19 10 6 21 14 3 15
    }
}

تفاوتی که این کد با کد قبلی که برای یک درخت معمولی داشتیم، در این است که قبلا لیستی از فرزندان را داشتیم که با خاصیت Children شناخته می‌شدند، ولی در اینجا در نهایت دو فرزند چپ و راست برای هر گره وجود دارند. برای جست و جو هم از الگوریتم In_Order استفاده کردیم که از همان الگوریتم DFS آمده‌است. در آنجا هم ابتدا گره‌های سمت چپ به صورت بازگشتی صدا زده می‌شدند. بعد خود گره و سپس گره‌های سمت راست به صورت بازگشتی صدا زده می‌شدند.

برای باقی روش‌های پیمایش تنها نیاز است که این سه خط را جابجا کنید:

  // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }

درخت دودویی مرتب شده Ordered Binary Search Tree

تا این لحظه ما با ساخت درخت‌های پایه آشنا شدیم: درخت عادی یا کلاسیک و درخت دو دویی. ولی در بیشتر موارد در پروژه‌های بزرگ از این‌ها استفاده نمی‌کنیم چرا که استفاده از آن‌ها در پروژه‌های بزرگ بسیار مشکل است و باید به جای آن‌ها از ساختارهای متنوع دیگری از قبیل درخت‌های مرتب شده، کم عمق و متوازن و کامل و پر و .. استفاده کرد. پس اجازه دهید که مهمترین درخت‌هایی را که در برنامه نویسی استفاده می‌شوند، بررسی کنیم.

همان طور که می‌دانید برای مقایسه اعداد ما از علامتهای <>= استفاده می‌کنیم و اعداد صحیح بهترین اعداد برای مقایسه هستند. در درخت‌های جست و جوی دو دویی یک خصوصیت اضافه به اسم کلید هویت یکتا Unique identification  Key داریم که یک کلید قابل مقایسه است. در تصویر زیر ما دو گره با مقدارهای متفاوتی داریم که با مقایسه‌ی آنان می‌توانیم کوچک و بزرگ بودن یک گره را محاسبه کنیم. ولی به این نکته دقت داشته باشید که این اعداد داخل دایره‌ها، دیگر برای ما حکم مقدار ندارند و کلید‌های یکتا و شاخص هر گره محسوب می‌شوند.

خلاصه‌ی صحبت‌های بالا: در هر درخت دودویی مرتب شده، گره‌های بزرگتر در زیر درخت راست قرار دارند و گره‌های کوچکتر در زیر درخت چپ قرار دارند که این کوچکی و بزرگی بر اساس یک کلید یکتا که قابل مقایسه است استفاده می‌شود.

این درخت دو دویی مرتب شده در جست و جو به ما کمک فراوانی می‌کند و از آنجا که می‌دانیم زیر درخت‌های چپ مقدار کمتری دارند و زیر درخت‌های راست مقدار بیشتر، عمل جست و جو، مقایسه‌های کمتری خواهد داشت، چرا که هر بار مقایسه یک زیر درخت کنار گذاشته می‌شود.

برای مثال فکر کنید می‌خواهید عدد 13 را در درخت بالا پیدا کنید. ابتدا گره والد 19 را مقایسه کرده و از آنجا که 19 بزرگتر از 13 است می‌دانیم که 13 را در زیر درخت راست پیدا نمی‌کنیم. پس زیر درخت چپ را مقایسه می‌کنیم (بنابراین به راحتی یک زیر درخت از مقایسه و عمل جست و جو کنار گذاشته شد). سپس گره 11 را مقایسه می‌کنیم و از آنجا که 11 کوچکتر از 13 هست، زیر درخت سمت راست را ادامه می‌دهیم و چون 16 بزرگتر از 13 هست، زیر درخت سمت چپ را در ادامه مقایسه می‌کنیم که به 13 رسیدیم.

مقایسه گره‌هایی که برای جست و جو انجام دادیم:

19-11-16-13

درخت هر چه بزرگتر باشد این روش کارآیی خود را بیشتر نشان می‌دهد.

یعنی اگر شما دارید نوع جدیدی را در یک زبان ایجاد می‌کنید که قصد دارید در یک زبان دیگر استفاده شود، نباید از امتیازات ویژه‌ای که آن زبان در اختیار شما می‌گذارد و به بیان بهتر CLS آن‌ها را پشتیبانی نمی‌کند، استفاده کنید؛ چرا که کد شما ممکن است در زبان دیگر مورد استفاده قرار نگیرد.

using System;

// Tell compiler to check for CLS compliance
[assembly: CLSCompliant(true)]

namespace SomeLibrary {

// Warnings appear because the class is public
public sealed class SomeLibraryType {

// Warning: Return type of 'SomeLibrary.SomeLibraryType.Abc()'
// is not CLS­compliant
public UInt32 Abc() { return 0; }

// Warning: Identifier 'SomeLibrary.SomeLibraryType.abc()'
// differing only in case is not CLS­compliant
public void abc() { }

// No warning: this method is private
private UInt32 ABC() { return 0; }
}
}

در مقاله‌ی قبل توانستیم یک سری از مدل‌های مربوط به وبلاگ را آماده کنیم. در ادامه به تکمیل آن و همچین آغاز تهیه‌ی مدل‌های مربوط به اخبار و پیغام خصوصی می‌پردازیم.
همکاران این قسمت:
سلمان معروفی

مدل گزارش دهی

Public Class User
{
        public string Id { get; set; }
        public string PhoneNumber { get; set; }
        public Dictionary<string, App> Apps { get; set; }
}
public class App
{
        public string FirstName { get; set; }
        public string LastName { get; set; }
        public string UserName { get; set; }
        public List<string> Roles { get; set; }
        public List<String> Messages { get; set; }
        public String AdressId { get; set; }
        public bool IsActive { get; set; } = true;
        [JsonIgnore]
        public string DisplayName => $"{FirstName} {LastName}";
}

services.AddSingleton<IDocumentStore>(serviceProvider =>
{
      var store = new DocumentStore()
      {
            Urls = new[] { "http://192.168.1.10:8080" },
            Database = "AccountingSystem",
      }.Initialize();
      return store;
});

services.AddScoped<IAsyncDocumentSession>(serviceProvider =>
{
      var store = serviceProvider.GetRequiredService<IDocumentStore>();
      return store.OpenAsyncSession();
});

_documentSession.Advanced.Patch<User, string>("Users/131-A",
      u => u.Apps["59"].RolesId
      , r => r.Add("Admin"));

var $table = $('#browsers-grid');
$table.dataTable({
      "bServerSide": true,
      "sAjaxSource": "/Home/GetBrowsers"
 });

^[1-5]$

/// <summary>
/// Class that encapsulates most common parameters sent by DataTables plugin
/// </summary>
public class jQueryDataTableParamModel
{
    /// <summary>
    /// Request sequence number sent by DataTable,
    /// same value must be returned in response
    /// </summary>
    public string sEcho { get; set; }
    /// <summary>
    /// Text used for filtering
    /// </summary>
    public string sSearch { get; set; }
    /// <summary>
    /// Number of records that should be shown in table
    /// </summary>
    public int iDisplayLength { get; set; }
    /// <summary>
    /// First record that should be shown(used for paging)
    /// </summary>
    public int iDisplayStart { get; set; }
    /// <summary>
    /// Number of columns in table
    /// </summary>
    public int iColumns { get; set; }
    /// <summary>
    /// Number of columns that are used in sorting
    /// /// </summary>
    public int iSortingCols { get; set; }
    /// <summary>
    /// Comma separated list of column names
    /// </summary>
    public string sColumns { get; set; }
}

public JsonResult GetBrowsers(jQueryDataTableParamModel param)
{
        IQueryable<Browser> allBrowsers = new Browsers().CreateInMemoryDataSource().AsQueryable();

        IEnumerable<Browser> filteredBrowsers;

        // Apply Filtering
        if (!string.IsNullOrEmpty(param.sSearch))
        {
                filteredBrowsers = new Browsers().CreateInMemoryDataSource()
                    .Where(x => x.Engine.Contains(param.sSearch)
                                       || x.Grade.Contains(param.sSearch)
                                       || x.Name.Contains(param.sSearch)
                                       || x.Platform.Contains(param.sSearch)
                    ).ToList();
                float f;
                if (float.TryParse(param.sSearch, out f))
                {
                    filteredBrowsers = filteredBrowsers.Where(x => x.Version.Equals(f));
                }
        }
        else
        {
                filteredBrowsers = allBrowsers;
        }

        // Apply Sorting
        var sortColumnIndex = Convert.ToInt32(Request["iSortCol_0"]);
        Func<Browser, string> orderingFunction = (x => sortColumnIndex == 0 ? x.Engine :
                                                            sortColumnIndex == 1 ? x.Name :
                                                            sortColumnIndex == 2 ? x.Platform :
                                                            sortColumnIndex == 3 ? x.Version.ToString() :
                                                            sortColumnIndex == 4 ? x.Grade :
                                                                x.Name);

        var sortDirection = Request["sSortDir_0"]; // asc or desc
        filteredBrowsers = sortDirection == "asc" ? filteredBrowsers.OrderBy(orderingFunction) : filteredBrowsers.OrderByDescending(orderingFunction);

        // Apply Paging
        var enumerable = filteredBrowsers.ToArray();
        IEnumerable<Browser> displayedBrowsers = enumerable.Skip(param.iDisplayStart).
                Take(param.iDisplayLength).ToList();

        return Json(new
        {
                sEcho = param.sEcho,
                iTotalRecords = allBrowsers.Count(),
                iTotalDisplayRecords = enumerable.Count(),
                aaData = displayedBrowsers
        }, JsonRequestBehavior.AllowGet);
}

$(function () {
        var $table = $('#browsers-grid');
        $table.dataTable({
                "bProcessing": true,
                "bStateSave": true,
                "bServerSide": true,
                "bFilter": true,
                "sDom": 'T<"clear">lftipr',
                "aLengthMenu": [[5, 10, 25, 50, -1], [5, 10, 25, 50, "All"]],
                "bAutoWidth": false,
                "sAjaxSource": "/Home/GetBrowsers",
                "fnServerData": function (sSource, aoData, fnCallback) {
                    $.ajax({
                        "dataType": 'json',
                        "type": "POST",
                        "url": sSource,
                        "data": aoData,
                        "success": fnCallback
                    });
                },
                "aoColumns": [
                    { "mDataProp": "Engine" },
                    { "mDataProp": "Name" },
                    { "mDataProp": "Platform" },
                    { "mDataProp": "Version" },
                    { "mDataProp": "Grade" }
                ],
                "oLanguage": {
                        "sUrl": "/Content/dataTables.persian.txt"
                }
        });
});

/* 
 * Password Hashing With PBKDF2 (http://crackstation.net/hashing-security.htm).
 * Copyright (c) 2013, Taylor Hornby
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Text;
using System.Security.Cryptography;

namespace PasswordHash
{
    /// <summary>
    /// Salted password hashing with PBKDF2-SHA1.
    /// Author: havoc AT defuse.ca
    /// www: http://crackstation.net/hashing-security.htm
    /// Compatibility: .NET 3.0 and later.
    /// </summary>
    public class PasswordHash
    {
        // The following constants may be changed without breaking existing hashes.
        public const int SALT_BYTE_SIZE = 24;
        public const int HASH_BYTE_SIZE = 24;
        public const int PBKDF2_ITERATIONS = 1000;

        public const int ITERATION_INDEX = 0;
        public const int SALT_INDEX = 1;
        public const int PBKDF2_INDEX = 2;

        /// <summary>
        /// Creates a salted PBKDF2 hash of the password.
        /// </summary>
        /// <param name="password">The password to hash.</param>
        /// <returns>The hash of the password.</returns>
        public static string CreateHash(string password)
        {
            // Generate a random salt
            RNGCryptoServiceProvider csprng = new RNGCryptoServiceProvider();
            byte[] salt = new byte[SALT_BYTE_SIZE];
            csprng.GetBytes(salt);

            // Hash the password and encode the parameters
            byte[] hash = PBKDF2(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
            return PBKDF2_ITERATIONS + ":" +
                Convert.ToBase64String(salt) + ":" +
                Convert.ToBase64String(hash);
        }

        /// <summary>
        /// Validates a password given a hash of the correct one.
        /// </summary>
        /// <param name="password">The password to check.</param>
        /// <param name="correctHash">A hash of the correct password.</param>
        /// <returns>True if the password is correct. False otherwise.</returns>
        public static bool ValidatePassword(string password, string correctHash)
        {
            // Extract the parameters from the hash
            char[] delimiter = { ':' };
            string[] split = correctHash.Split(delimiter);
            int iterations = Int32.Parse(split[ITERATION_INDEX]);
            byte[] salt = Convert.FromBase64String(split[SALT_INDEX]);
            byte[] hash = Convert.FromBase64String(split[PBKDF2_INDEX]);

            byte[] testHash = PBKDF2(password, salt, iterations, hash.Length);
            return SlowEquals(hash, testHash);
        }

        /// <summary>
        /// Compares two byte arrays in length-constant time. This comparison
        /// method is used so that password hashes cannot be extracted from
        /// on-line systems using a timing attack and then attacked off-line.
        /// </summary>
        /// <param name="a">The first byte array.</param>
        /// <param name="b">The second byte array.</param>
        /// <returns>True if both byte arrays are equal. False otherwise.</returns>
        private static bool SlowEquals(byte[] a, byte[] b)
        {
            uint diff = (uint)a.Length ^ (uint)b.Length;
            for (int i = 0; i < a.Length && i < b.Length; i++)
                diff |= (uint)(a[i] ^ b[i]);
            return diff == 0;
        }

        /// <summary>
        /// Computes the PBKDF2-SHA1 hash of a password.
        /// </summary>
        /// <param name="password">The password to hash.</param>
        /// <param name="salt">The salt.</param>
        /// <param name="iterations">The PBKDF2 iteration count.</param>
        /// <param name="outputBytes">The length of the hash to generate, in bytes.</param>
        /// <returns>A hash of the password.</returns>
        private static byte[] PBKDF2(string password, byte[] salt, int iterations, int outputBytes)
        {
            Rfc2898DeriveBytes pbkdf2 = new Rfc2898DeriveBytes(password, salt);
            pbkdf2.IterationCount = iterations;
            return pbkdf2.GetBytes(outputBytes);
        }
    }
}