رایگان: همین الان رتبه‌ ارشدت رو تخمین بزن! کافیه عضو این بات تلگرامی رایگان بشین و دقیق‌ترین تخمین از رتبه‌تون رو دریافت کنین.
عضویت در بات تخمین رتبه
کنکور کامپیوتر
0
ورود | ثبت نام
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 

درخت بی B-Tree، آموزش درخت b tree

این صفحه عالی به معرفی و آموزش درخت بی یا همان B-Tree پرداخته و ویژگی‌های B-Tree، عملیات‌های درخت B، پیاده‌سازی درخت B و کاربردهای درخت بی را معرفی کرده

درخت B یا B-tree یک ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است درخت جستجوی باینری است که برای عملیات جستجو و حذف سریع بهینه شده است. در پایگاه‌های داده، سیستم‌های فایل و سایر برنامه‌ها که در آن داده‌های گسترده باید به طور مؤثر جستجو شوند، استفاده می‌شود. B-treeها می‌توانند کلیدها و مقادیر زیادی را در یک فضای فشرده ذخیره کنند و از عملیات‌های درج و حذف سریع پشتیبانی کنند. در این مقاله به بررسی این نوع درختان می‌پردازیم.

ویژگی‌های درخت B

درخت B از مرتبه n شامل تمام ویژگی‌های درخت است، علاوه بر این شامل خواص زیر نیز می‌باشد:

عملیات‌های درخت B

در ادامه عملیات‌های جستجو، حذف و درج در درخت B را بررسی خواهیم کرد.

عملیات جستجو در درخت B

جستجو در درختان B شبیه به جستجوی درخت جستجوی باینری است؛ به عنوان مثال، اگر عنصر 49 را در B Tree زیر جستجو کنیم، روند چیزی شبیه به زیر خواهد بود:

نمونه ای از درخت B

  1. عنصر 49 را با گره ریشه 78 مقایسه کنید. چون 49 < 78 است، به زیر درخت سمت چپ آن بروید.
  2. از آنجایی که 40 < 49 < 56، از زیر درخت 40 به سمت راست عبور کنید.
  3. 49 > 45، به سمت راست حرکت کنید. عنصر 49 را با 49 مقایسه کنید.
  4. عنصر مورد نظر پیدا شد، آن را برمی‌گردانیم.

عملیات درج در درخت B

درج در سطح گره برگ انجام می‌شود. برای درج یک آیتم در B Tree باید الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراوانالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد زیر را دنبال کنید:

برای مثال فرض کنید می‌خواهید عنصر 8 را در درخت B با مرتبه 5 زیر درج کنید:

نمونه ای از درخت B

8 در سمت راست 5 درج می شود، بنابراین 8 را درج کنید.

درج عدد 8 در سمت راست 5 در درخت B

گره جدید، اکنون حاوی 5 کلید است که بزرگتر از حد مجاز است (5 - 1 = 4) است بنابراین گره را از عنصر میانی یعنی 8 جدا کنید و آن را به سمت گره والد خود که به شکل زیر نشان داده شده است، منتقل کنید:

درخت B نهایی به همین شکل خواهد بود.

عملیات حذف از درخت B

حذف نیز در گره‌های برگ انجام می‌شود. گره‌ای که باید حذف شود می‌تواند یک گره برگ یا یک گره داخلی باشد. برای حذف یک گره از درخت B، الگوریتم زیر باید دنبال شود:

  1. محل گره برگ را پیدا کنید.
  2. اگر بیش از m/2 کلید در گره برگ وجود دارد، کلید مورد نظر را از گره حذف کنید.
  3. اگر گره برگ کمتر از m/2 کلید دارد ، با گرفتن عنصر از سمت راست یا چپ، کلیدها را تکمیل کنید.
    • اگر گره سمت چپ حاوی بیش از m/2 عناصر است، بزرگترین عنصر آن را به سمت والدش منتقل کنید و عنصر وسط را به سمت پایین به سمت گره‌ای که کلیدش حذف شده است، ببرید.
    • اگر گره سمت راست حاوی بیش از m/2 عناصر است، کوچکترین عنصر آن را به سمت والد منتقل کنید و عنصر وسط را به سمت پایین به سمت گره‌ای که کلیدش حذف شده است ببرید.
  4. اگر هیچ یک از گره‌های کناری بیش از m/2 عنصر ندارند، با پیوند دادن دو گره برگ و عنصر میانی گره والد، یک گره برگ جدید ایجاد کنید.
  5. اگر گره‌های والد کمتر از m/2 است، فرآیند بالا را برای والد نیز اعمال کنید.

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

برای مثال فرض کنید می‌خواهید گره 10 را از درخت B مرتبه 5 که در شکل زیر نشان داده شده است حذف کنید:

نمونه ای از درخت B

10 در فرزند سمت راست عنصر 8 وجود دارد، آن را حذف کنید.

حذف عنصر 10 از درخت B

در حال حاضر، 23 تنها عنصر باقی مانده در گره است، و از حداقل تعداد عناصری که باید در درخت B درجه 5 وجود داشته باشد، یعنی 2 کمتر است. عناصر موجود در زیردرخت چپ و راست آن نیز کافی نیستند بنابراین آن را با گره‌های چپ و راست و عنصر میانی والد، یعنی 8 ادغام کنید.

درخت B نهایی به صورت زیر است:

درخت B نهایی پس از حذف عنصر 10 از آن

پیچیدگی زمانی عملیات‌های درخت B

پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده  درخت B برای عملیات‌های جستجو، درج و حذف از مرتبه Θ(log n) است.

پیاده‌سازی درخت B

در ادامه به پیاده سازی درخت B در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده می‌پردازیم:

Python

# Searching a key on a B-tree in Python

# Create a node
class BTreeNode:
    def __init__(self, leaf=False):
        self.leaf = leaf
        self.keys = []
        self.child = []

# Tree
class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t

        # Insert node

    def insert(self, k):
        root = self.root
        if len(root.keys) == (2 * self.t) - 1:
            temp = BTreeNode()
            self.root = temp
            temp.child.insert(0, root)
            self.split_child(temp, 0)
            self.insert_non_full(temp, k)
        else:
            self.insert_non_full(root, k)

        # Insert nonfull

    def insert_non_full(self, x, k):
        i = len(x.keys) - 1
        if x.leaf:
            x.keys.append((None, None))
            while i >= 0 and k[0] < x.keys[i][0]:
                x.keys[i + 1] = x.keys[i]
                i -= 1
            x.keys[i + 1] = k
        else:
            while i >= 0 and k[0] < x.keys[i][0]:
                i -= 1
            i += 1
            if len(x.child[i].keys) == (2 * self.t) - 1:
                self.split_child(x, i)
                if k[0] > x.keys[i][0]:
                    i += 1
            self.insert_non_full(x.child[i], k)

        # Split the child

    def split_child(self, x, i):
        t = self.t
        y = x.child[i]
        z = BTreeNode(y.leaf)
        x.child.insert(i + 1, z)
        x.keys.insert(i, y.keys[t - 1])
        z.keys = y.keys[t : (2 * t) - 1]
        y.keys = y.keys[0 : t - 1]
        if not y.leaf:
            z.child = y.child[t : 2 * t]
            y.child = y.child[0 : t - 1]

    # Print the tree
    def print_tree(self, x, l=0):
        print("Level ", l, " ", len(x.keys), end=":")
        for i in x.keys:
            print(i, end=" ")
        print()
        l += 1
        if len(x.child) > 0:
            for i in x.child:
                self.print_tree(i, l)

    # Search key in the tree
    def search_key(self, k, x=None):
        if x is not None:
            i = 0
            while i < len(x.keys) and k > x.keys[i][0]:
                i += 1
            if i < len(x.keys) and k == x.keys[i][0]:
                return (x, i)
            elif x.leaf:
                return None
            else:
                return self.search_key(k, x.child[i])

        else:
            return self.search_key(k, self.root)

def main():
    B = BTree(3)

    for i in range(10):
        B.insert((i, 2 * i))

    B.print_tree(B.root)

    if B.search_key(8) is not None:
        print("\nFound")
    else:
        print("\nNot Found")

if __name__ == "__main__":
    main()

C++

// Searching a key on a B-tree in C++

#include <iostream>
using namespace std;

class TreeNode
{
    int *keys;
    int t;
    TreeNode **C;
    int n;
    bool leaf;

public:
    TreeNode(int temp, bool bool_leaf);

    void insertNonFull(int k);
    void splitChild(int i, TreeNode *y);
    void traverse();

    TreeNode *search(int k);

    friend class BTree;
};

class BTree
{
    TreeNode *root;
    int t;

public:
    BTree(int temp)
    {
        root = NULL;
        t = temp;
    }

    void traverse()
    {
        if (root != NULL)
            root->traverse();
    }

    TreeNode *search(int k)
    {
        return (root == NULL) ? NULL : root->search(k);
    }

    void insert(int k);
};

TreeNode::TreeNode(int t1, bool leaf1)
{
    t = t1;
    leaf = leaf1;

    keys = new int[2 * t - 1];
    C = new TreeNode *[2 * t];

    n = 0;
}

void TreeNode::traverse()
{
    int i;
    for (i = 0; i  n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout  " "  keys[i];
    }

    if (leaf == false)
        C[i]->traverse();
}

TreeNode *TreeNode::search(int k)
{
    int i = 0;
    while (i  n && k > keys[i])
        i++;

    if (keys[i] == k)
        return this;

    if (leaf == true)
        return NULL;

    return C[i]->search(k);
}

void BTree::insert(int k)
{
    if (root == NULL)
    {
        root = new TreeNode(t, true);
        root->keys[0] = k;
        root->n = 1;
    }
    else
    {
        if (root->n == 2 * t - 1)
        {
            TreeNode *s = new TreeNode(t, false);

            s->C[0] = root;

            s->splitChild(0, root);

            int i = 0;
            if (s->keys[0]  k)
                i++;
            s->C[i]->insertNonFull(k);

            root = s;
        }
        else
            root->insertNonFull(k);
    }
}

void TreeNode::insertNonFull(int k)
{
    int i = n - 1;

    if (leaf == true)
    {
        while (i >= 0 && keys[i] > k)
        {
            keys[i + 1] = keys[i];
            i--;
        }

        keys[i + 1] = k;
        n = n + 1;
    }
    else
    {
        while (i >= 0 && keys[i] > k)
            i--;

        if (C[i + 1]->n == 2 * t - 1)
        {
            splitChild(i + 1, C[i + 1]);

            if (keys[i + 1]  k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

void TreeNode::splitChild(int i, TreeNode *y)
{
    TreeNode *z = new TreeNode(y->t, y->leaf);
    z->n = t - 1;

    for (int j = 0; j  t - 1; j++)
        z->keys[j] = y->keys[j + t];

    if (y->leaf == false)
    {
        for (int j = 0; j  t; j++)
            z->C[j] = y->C[j + t];
    }

    y->n = t - 1;
    for (int j = n; j >= i + 1; j--)
        C[j + 1] = C[j];

    C[i + 1] = z;

    for (int j = n - 1; j >= i; j--)
        keys[j + 1] = keys[j];

    keys[i] = y->keys[t - 1];
    n = n + 1;
}

int main()
{
    BTree t(3);
    t.insert(8);
    t.insert(9);
    t.insert(10);
    t.insert(11);
    t.insert(15);
    t.insert(16);
    t.insert(17);
    t.insert(18);
    t.insert(20);
    t.insert(23);

    cout  "The B-tree is: ";
    t.traverse();

    int k = 10;
    (t.search(k) != NULL) ? cout  endl
                                  k  " is found"
                          : cout  endl
                                  k  " is not Found";

    k = 2;
    (t.search(k) != NULL) ? cout  endl
                                  k  " is found"
                          : cout  endl
                                  k  " is not Found\n";
}

مقایسه با درخت B+

برجسته‌ترین نقاط مقایسه بین B-tree و B+tree شامل موارد زیر است:

کاربردهای درخت B

از کاربردهای درخت B می‌توان به موارد زیر اشاره کرد:

جمع‌بندی

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

درخت B چیست؟

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

مزیت اصلی استفاده از B-Trees چیست؟

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

پیچیدگی زمانی B-tree چقدر است؟

اگر n را تعداد کل عناصر یک درخت B در نظر بگیریم، پیچیدگی زمانی برای هر عملیات رایج، یعنی جستجو، درج و حذف، O(log n) خواهد بود.

درخت B بهتر است یا درخت B+؟

در B-tree، جستجو ناکارآمد است زیرا رکوردها در برگ یا گره‌های داخلی ذخیره می‌شوند. در درخت B+، جستجو بسیار کارآمد یا سریعتر است زیرا تمام رکوردها در گره‌های برگ ذخیره می‌شوند.

مزیت B-tree نسبت به درخت AVL چیست؟

AVL خود متعادل کننده است و تضمین می‌کند که همه عملیات‌ها در حالت متوسط و بدترین حالت O(log n) هستند. علاوه بر این، B-tree با اطمینان از پر بودن گره های داخلی حداقل ضایعات را به حداقل می‌رساند. یک B-tree می‌تواند تعداد دلخواه درج و حذف را مدیریت کند.

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (1 امتیاز)
اشتراک
بارگذاری نظرات
تلگرام اینستاگرام تماس با پشتیبانی: 09378555200 تماس با پشتیبانی: 09378555200