درخت جستجوی باینری دیگه چه کوفتیه؟

binary search tree چیست؟

درخت دودویی نوعی ساختار داده است که معمولاً برای نمایش داده های سلسله مراتبی استفاده می شود. این یک روش کارآمد برای ذخیره و سازماندهی داده ها است که در گره های مادر و گره های فرزند رتبه بندی می شود.

در اصل ، درخت دوتایی مجموعه ای از داده ها است که گره ها نامیده می شوند و به منظور شبیه سازی سلسله مراتب به هم متصل می شوند و در مقایسه با ساختارهای داده خطی مانند یک لیست پیوندی یا یک آرایه ، آن را به یک ساختار داده غیر خطی تبدیل می کند.

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

به عنوان مثال ، در تصویر بالا ، می توان نتیجه گرفت که این یک درخت جستجوی دودویی است زیرا چون 3 کمتر از 8 است ، به زیر درخت چپ می رود و از آنجا که 10 بزرگتر از 8 است ، به زیر درخت راست می رود. علاوه بر این ، می توان فرض کرد که هیچ گره ای نمی تواند از زیر درختان عبور کند ، اطمینان حاصل شود که همه گره های کمتر از ریشه همیشه در زیر درخت چپ قرار دارند و برعکس. به خاطر داشته باشید که تغییر مقدار یک گره که آن را کمتر یا بیشتر از گره می کند ، مانع درخت می شود. اگر مقدار گره کودک راست 3 ، که 6 است ، به 9 تغییر کند ، این دیگر یک درخت دوتایی نخواهد بود ، زیرا اگرچه 9 بزرگتر از 3 است و در سمت راست 3 قرار دارد ، 9 نیز بزرگتر از ریشه 8 ، بنابراین نمی تواند در سمت چپ باقی بماند.

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

سه نوع مختلف درختان دوتایی وجود دارد. اگر همه گره ها دو فرزند داشته باشند ، یک درخت دوتایی پر است ، به جز برگها ، که دارای صفر فرزند خواهند بود. یک درخت دوتایی کامل است اگر تمام سطوح سلسله مراتبی با گره ها پر شود ، با این تفاوت که پایین ترین سطح دارای صفر فرزند و سطح قبل از آخرین دارای 0 یا 1 یا 2 گره فرزند خواهد بود. درخت دوتایی اگر همه گره ها دو فرزند داشته باشند و تمام برگها در یک سطح ختم شوند ، عالی است. برای بررسی اینکه آیا درخت دوتایی متعادل است یا نه ، تفاوت بین ارتفاع درخت فرعی چپ و راست بیشتر از 1 نیست.

برای انجام عملیات جستجو در یک درخت دوتایی ، از یک جستجوی دودویی استفاده می کنیم. یک جستجوی دودویی ابتدا نقطه وسط یک فضای جستجوی از پیش تعیین شده را پیدا می کند. سپس ، بررسی می کند که آیا تعداد هدف کمتر یا بیشتر از نقطه میانی است ، حرکت به چپ کمتر یا راست تر در صورت بیشتر شدن است ، و همزمان فضای جستجو را به نصف می رساند. این باعث می شود که پیچیدگی زمانی جستجوی دودویی همیشه O (log n) باشد.

بیایید نگاهی به این مثال بیندازیم تا یک جستجوی دودویی از یک درخت دوتایی نامتعادل را انجام دهیم.

در اینجا نمونه ای از کد عملیات جستجوی درخت دودویی به صورت زیر است:

def _find_node_iterative(self, item):
        node = self.root
        # Loop until we descend past the closest leaf node
        while node is not None:
            if item == node.data:
                return node
            elif item < node.data:
                node = node.left
            elif item > node.data:
                node = node.right
        # Not found
        return None

در مثال زیر ، گره ای با مقدار 64 را جستجو می کنیم. از آنجا که می دانیم 64 بزرگتر از ریشه ، 60 است ، در حالی که گره فرزند را با مقدار مورد نظر مقایسه می کنیم ، به زیر درخت راست نگاه می کنیم. به فضای جستجوی فعلی ما n/2 می شود. در ادامه ، ما به پایین رفتن درخت از طریق گره با مقدار 74 ادامه می دهیم. از آنجا که هدف ما کمتر است و والدین فقط یک فرزند دارند ، ما این کار را ادامه می دهیم. فضای جستجوی به روز شده ما: n/4. بعد ، 64 کمتر از 65 است که ما به سمت چپ نگاه می کنیم. فضای جستجو: n/8. در نهایت ، ما می بینیم که 64 بزرگتر از گره والدین 63 است ، ما به سمت راست نگاه می کنیم و گره را پیدا می کنیم. فضای نهایی جستجوی ما n/16 می شود زیرا 4 جستجوی دودویی برای یافتن گره مورد نظر ما طول کشید.

اکنون بیایید نگاهی به درج گره در یک درخت جستجوی دودویی بیندازیم.

در مثال زیر ، گره ای با مقدار 18 وارد می کنیم. از ریشه شروع می کنیم ، 18 بزرگتر از 10 است ، بنابراین آن را در زیر درخت سمت راست قرار می دهیم. با حرکت رو به جلو ، می بینیم که 18 کمتر از 19 است ، بنابراین به سمت کودک چپ می رویم. از آنجا که 18 بزرگتر از 17 است ، اما هیچ گره فرزند وجود ندارد ، ما یک گره جدید ایجاد (وارد) می کنیم و روند کامل می شود. درخت دوتایی جدید ما شبیه این خواهد بود.

در اینجا نمونه ای از کد درج درخت جستجوی دودویی به نظر می رسد:

def insert(self, item):
        if self.is_empty():
            self.root = BinaryTreeNode(item)
            self.size += 1
            return
        parent = self._find_parent_node_recursive(item, self.root)
        if parent == None:
            self.root.left = BinaryTreeNode(item)
        elif parent.data > item:
            parent.left = BinaryTreeNode(item)
        elif parent.data < item:
            parent.right = BinaryTreeNode(item)
        self.size += 1

اگر تا اینجا خوانده اید ، اکنون درک اولیه ای از نحوه عملکرد ، درج و حذف درخت دوتایی دارید..