什么是Python中的二叉排序樹(shù)和平衡二叉樹(shù)

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)什么是Python中的二叉排序樹(shù)和平衡二叉樹(shù)，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

創(chuàng)新互聯(lián)專注于合浦企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開(kāi)發(fā),商城網(wǎng)站定制開(kāi)發(fā)。合浦網(wǎng)站建設(shè)公司,為合浦等地區(qū)提供建站服務(wù)。全流程按需搭建網(wǎng)站，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

二叉排序樹(shù)

二叉排序樹(shù)又稱為二叉查找樹(shù)。它或者是一顆空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：

若它的左子樹(shù)不為空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根結(jié)構(gòu)的值；若它的右子樹(shù)不為空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根結(jié)構(gòu)的值；它的左、右子樹(shù)也分別為二叉排序樹(shù)。

構(gòu)造一顆二叉排序樹(shù)的目的，往往不是為了排序，而是為了提高查找和插入刪除關(guān)鍵字的速度。

二叉排序樹(shù)的操作：

查找：對(duì)比節(jié)點(diǎn)的值和關(guān)鍵字，相等則表明找到了；小了則往節(jié)點(diǎn)的左子樹(shù)去找，大了則往右子樹(shù)去找，這么遞歸下去，最后返回布爾值或找到的節(jié)點(diǎn)。插入：從根節(jié)點(diǎn)開(kāi)始逐個(gè)與關(guān)鍵字進(jìn)行對(duì)比，小了去左邊，大了去右邊，碰到子樹(shù)為空的情況就將新的節(jié)點(diǎn)鏈接。刪除：如果要?jiǎng)h除的節(jié)點(diǎn)是葉子，直接刪；如果只有左子樹(shù)或只有右子樹(shù)，則刪除節(jié)點(diǎn)后，將子樹(shù)鏈接到父節(jié)點(diǎn)即可；如果同時(shí)有左右子樹(shù)，則可以將二叉排序樹(shù)進(jìn)行中序遍歷，取將要被刪除的節(jié)點(diǎn)的前驅(qū)或者后繼節(jié)點(diǎn)替代這個(gè)被刪除的節(jié)點(diǎn)的位置。

      """
    定義一個(gè)二叉樹(shù)節(jié)點(diǎn)類。
    以討論算法為主，忽略了一些諸如對(duì)數(shù)據(jù)類型進(jìn)行判斷的問(wèn)題。
    """
    def __init__(self, data, left=None, right=None):
        """
        初始化
        :param data: 節(jié)點(diǎn)儲(chǔ)存的數(shù)據(jù)
        :param left: 節(jié)點(diǎn)左子樹(shù)
        :param right: 節(jié)點(diǎn)右子樹(shù)
        """
        self.data = data
        self.left = left
        self.right = rightclass BinarySortTree:
    """
    基于BSTNode類的二叉排序樹(shù)。維護(hù)一個(gè)根節(jié)點(diǎn)的指針。
    """
    def __init__(self):
        self._root = None
    def is_empty(self):
        return self._root is None
    def search(self, key):
        """
        關(guān)鍵碼檢索
        :param key: 關(guān)鍵碼
        :return: 查詢節(jié)點(diǎn)或None
        """
        bt = self._root        while bt:
            entry = bt.data            if key < entry:
                bt = bt.left            elif key > entry:
                bt = bt.right            else:                return entry        return None
    def insert(self, key):
        """
        插入操作
        :param key:關(guān)鍵碼 
        :return: 布爾值
        """
        bt = self._root        if not bt:
            self._root = BSTNode(key)            return
        while True:
            entry = bt.data            if key < entry:                if bt.left is None:
                    bt.left = BSTNode(key)                    return
                bt = bt.left            elif key > entry:                if bt.right is None:
                    bt.right = BSTNode(key)                    return
                bt = bt.right            else:
                bt.data = key                return
    def delete(self, key):
        """
        二叉排序樹(shù)最復(fù)雜的方法
        :param key: 關(guān)鍵碼
        :return: 布爾值
        """
        p, q = None, self._root     # 維持p為q的父節(jié)點(diǎn)，用于后面的鏈接操作
        if not q:
            print("空樹(shù)！")            return
        while q and q.data != key:
            p = q            if key < q.data:
                q = q.left            else:
                q = q.right            if not q:               # 當(dāng)樹(shù)中沒(méi)有關(guān)鍵碼key時(shí)，結(jié)束退出。
                return
        # 上面已將找到了要?jiǎng)h除的節(jié)點(diǎn)，用q引用。而p則是q的父節(jié)點(diǎn)或者None（q為根節(jié)點(diǎn)時(shí)）。
        if not q.left:            if p is None:
                self._root = q.right            elif q is p.left:
                p.left = q.right            else:
                p.right = q.right            return
        # 查找節(jié)點(diǎn)q的左子樹(shù)的最右節(jié)點(diǎn)，將q的右子樹(shù)鏈接為該節(jié)點(diǎn)的右子樹(shù)
        # 該方法可能會(huì)增大樹(shù)的深度，效率并不算高?？梢栽O(shè)計(jì)其它的方法。
        r = q.left        while r.right:
            r = r.right
        r.right = q.right        if p is None:
            self._root = q.left        elif p.left is q:
            p.left = q.left        else:
            p.right = q.left    def __iter__(self):
        """
        實(shí)現(xiàn)二叉樹(shù)的中序遍歷算法,
        展示我們創(chuàng)建的二叉排序樹(shù).
        直接使用python內(nèi)置的列表作為一個(gè)棧。
        :return: data
        """
        stack = []
        node = self._root        while node or stack:            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()            yield node.data
            node = node.rightif __name__ == '__main__':
    lis = [62, 58, 88, 48, 73, 99, 35, 51, 93, 29, 37, 49, 56, 36, 50]
    bs_tree = BinarySortTree()    for i in range(len(lis)):
        bs_tree.insert(lis[i])    # bs_tree.insert(100)
    bs_tree.delete(58)    for i in bs_tree:
        print(i, end=" ")    # print("\n", bs_tree.search(4))

二叉排序樹(shù)總結(jié)：

二叉排序樹(shù)以鏈?zhǔn)竭M(jìn)行存儲(chǔ)，保持了鏈接結(jié)構(gòu)在插入和刪除操作上的優(yōu)點(diǎn)。在極端情況下，查詢次數(shù)為1，但最大操作次數(shù)不會(huì)超過(guò)樹(shù)的深度。也就是說(shuō)，二叉排序樹(shù)的查找性能取決于二叉排序樹(shù)的形狀，也就引申出了后面的平衡二叉樹(shù)。給定一個(gè)元素集合，可以構(gòu)造不同的二叉排序樹(shù)，當(dāng)它同時(shí)是一個(gè)完全二叉樹(shù)的時(shí)候，查找的時(shí)間復(fù)雜度為O(log(n))，近似于二分查找。當(dāng)出現(xiàn)最極端的斜樹(shù)時(shí)，其時(shí)間復(fù)雜度為O(n)，等同于順序查找，效果最差。

平衡二叉樹(shù)

平衡二叉樹(shù)（AVL樹(shù)，發(fā)明者的姓名縮寫(xiě)）：一種高度平衡的排序二叉樹(shù)，其每一個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差最多等于1。

平衡二叉樹(shù)首先必須是一棵二叉排序樹(shù)！

平衡因子（Balance Factor）：將二叉樹(shù)上節(jié)點(diǎn)的左子樹(shù)深度減去右子樹(shù)深度的值。

對(duì)于平衡二叉樹(shù)所有包括分支節(jié)點(diǎn)和葉節(jié)點(diǎn)的平衡因子只可能是-1,0和1，只要有一個(gè)節(jié)點(diǎn)的因子不在這三個(gè)值之內(nèi)，該二叉樹(shù)就是不平衡的。

最小不平衡子樹(shù)：距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)為根的子樹(shù)。

平衡二叉樹(shù)的構(gòu)建思想：每當(dāng)插入一個(gè)新結(jié)點(diǎn)時(shí)，先檢查是否破壞了樹(shù)的平衡性，若有，找出最小不平衡子樹(shù)。在保持二叉排序樹(shù)特性的前提下，調(diào)整最小不平衡子樹(shù)中各結(jié)點(diǎn)之間的連接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)，成為新的平衡子樹(shù)。

下面是由[1,2,3,4,5,6,7,10,9]構(gòu)建平衡二叉樹(shù)

上述就是小編為大家分享的什么是Python中的二叉排序樹(shù)和平衡二叉樹(shù)了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

名稱欄目：什么是Python中的二叉排序樹(shù)和平衡二叉樹(shù)
分享URL：http://m.jiaotiyi.com/article/popech.html