什么是Python中的二叉排序樹和平衡二叉樹

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

二叉排序樹

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

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

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

二叉排序樹的操作：

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

      """
    定義一個(gè)二叉樹節(jié)點(diǎn)類。
    以討論算法為主，忽略了一些諸如對數(shù)據(jù)類型進(jìn)行判斷的問題。
    """
    def __init__(self, data, left=None, right=None):
        """
        初始化
        :param data: 節(jié)點(diǎn)儲存的數(shù)據(jù)
        :param left: 節(jié)點(diǎn)左子樹
        :param right: 節(jié)點(diǎn)右子樹
        """
        self.data = data
        self.left = left
        self.right = rightclass BinarySortTree:
    """
    基于BSTNode類的二叉排序樹。維護(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):
        """
        二叉排序樹最復(fù)雜的方法
        :param key: 關(guān)鍵碼
        :return: 布爾值
        """
        p, q = None, self._root     # 維持p為q的父節(jié)點(diǎn)，用于后面的鏈接操作
        if not q:
            print("空樹！")            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)樹中沒有關(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的左子樹的最右節(jié)點(diǎn)，將q的右子樹鏈接為該節(jié)點(diǎn)的右子樹
        # 該方法可能會增大樹的深度，效率并不算高?？梢栽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)二叉樹的中序遍歷算法,
        展示我們創(chuàng)建的二叉排序樹.
        直接使用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))

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

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

平衡二叉樹

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

平衡二叉樹首先必須是一棵二叉排序樹！

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

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

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

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

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

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