天天看點
傳回

資料結構(python) —— 【28: AVL樹】

AVL樹

上一篇部落格說到二叉搜尋樹的效率在最壞的情況下可能十分偏斜:

資料結構(python) —— 【27: 二叉搜尋樹】

而AVL樹是對二叉搜尋樹的優化，今天就來說說AVL樹！

1. 概念

AVL樹: AVL樹是一棵自平衡的二叉搜尋樹。

AVL樹具有以下性質:

  • 根的左右子樹的高度之差的絕對值不能超過1
  • 根的左右子樹都是平衡二叉樹
    資料結構(python) —— 【28: AVL樹】

其中高度之差我們用balance factor (平衡因子) 來進行解釋。平衡因子的正負号表示左右子樹哪邊的深度大，可以自己定義。這裡我定義了左子樹深度>右子樹深度，則該點的平衡因子為正，反之為負。數值為左右子樹的深度之差，比如key=23這個點，左子樹深度為3，右子樹深度為2，則左子樹深度>右子樹深度，是以符号為正，且深度之差為1，是以23的平衡因子為1。

2. 操作

AVL樹——插入

插入一個節點可能會破壞AVL樹的平衡，可以通過旋轉操作來進行修正。

插入一個節點後，隻有從插入節點到根節點的路徑上的節點的平衡可能被改變。我們需要找出第一個破壞了平衡條件的節點，稱之為K。K的兩顆子樹的高度差2。

不平衡的出現可能有4種情況:

  1. 不平衡是由于對K的右孩子的右子樹插入導緻的:左旋
  2. 不平衡是由于對K的左孩子的左子樹插入導緻的:右旋
  3. 不平衡是由于對K的右孩子的左子樹插入導緻的:右旋-左旋
  4. 不平衡是由于對K的左孩子的右子樹插入導緻的:左旋-右旋

具體操作的解釋較為複雜，這裡我就不單獨做GIF解釋了，有興趣的讀者可以上某站看一下清華博士的講解，還是比較清楚的。清華計算機博士講解的AVL旋轉

3. 代碼

代碼也較為複雜，我粘貼出來，大家稍微看一下就好，就興趣的可以研究一下，沒興趣的讀者可以跳過。

'''
TOPIC: AVL樹
author: Blue
time: 2020-08-17
QQ: 2458682080
'''

class BiTreeNode:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None
        self.parent = None

class BST:
    def __init__(self, li=None):
        self.root = None
        if li:
            for val in li:
                self.insert_no_rec(val)

    # 利用遞歸插入
    def insert(self, node, val):
        if not node:
            node = BiTreeNode(val)
        elif val < node.data:
            node.lchild = self.insert(node.lchild, val)
            node.lchild.parent = node
        elif val > node.data:
            node.rchild = self.insert(node.rchild, val)
            node.rchild.parent = node
        return node

    # 利用非遞歸插入
    def insert_no_rec(self, val):
        p = self.root
        if not p:  # 空樹
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:  # 如果p存在左孩子
                    p = p.lchild
                else:        # 如果p不存在左孩子
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    return
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    return
            else:
                return

    # 用遞歸查詢
    def query(self, node, val):
        if not node:
            return None
        if node.data < val:
            return self.query(node.rchild, val)
        elif node.data > val:
            return self.query(node.lchild, val)
        else:
            return node

    # 不用遞歸查詢
    def query_no_rec(self, val):
        p = self.root
        while p:
            if p.data < val:
                p = p.rchild
            elif p.data > val:
                p = p.lchild
            else:
                return p
        return None

    # 情況1: node是葉子節點
    def __remove_node_1(self, node):
        if not node.parent:  # 如果這個節點是根
            self.root = None
        if node == node.parent.lchild:  # 如果node是它父親的左孩子
            node.parent.lchild = None
        else:
            node.parent.rchild = None

    # 情況2.1: node隻有一個左孩子
    def __remove_node_21(self, node):
        if not node.parent:   # 根結點
            self.root = node.lchild
            node.lchild.parent = None
        elif node == node.parent.lchild:   # node是它父親的左孩子
            node.parent.lchild = node.lchild # node删掉，node的左孩子給node的父親作為左孩子
            node.lchild.parent = node.parent
        else:
            node.parent.rchild = node.lchild
            node.lchild.parent = node.parent

    # 情況2.2: node隻有一個右孩子
    def __remove_node_22(self, node):
        if not node.parent:
            self.root = node.rchild
        elif node == node.parent.lchild:  # node是它父親的左孩子
            node.parent.lchild = node.rchild
            node.rchild.parent = node.parent
        else:
            node.parent.rchild = node.rchild
            node.rchild.parent = node.parent

    # 删除
    def delete(self, val):
        if self.root:  # 不是空樹
            node = self.query_no_rec(val)
            if not node:  # node不存在
                return False
            # 情況1: node是葉結點
            if not node.lchild and not node.rchild:
                self.__remove_node_1(node)
            # 情況2.1: 隻有左孩子
            elif not node.rchild:
                self.__remove_node_21(node)
            # 情況2.2: 隻有右孩子
            elif not node.lchild:
                self.__remove_node_22(node)
            # 情況3: 兩個孩子都有
            else:
                min_node = node.rchild
                # 找到右子樹的最小節點
                while min_node.lchild:
                    min_node = min_node.lchild
                node.data = min_node.data
                # 删除min_node,這裡min)node隻有兩種情況，要麼是葉結點，要麼就是隻有右孩子
                if min_node.rchild:
                    self.__remove_node_22(min_node)
                else:
                    self.__remove_node_1(min_node)

    # 前序周遊(先遞歸左子樹，再遞歸右子樹)
    def pre_order(self, root):
        if root:
            print(root.data, end=",")
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    # 中序周遊(先遞歸左子樹，再通路自己，再遞歸右子樹)
    def in_order(self, root):
        if root:
            self.in_order(root.lchild)
            print(root.data, end=",")
            self.in_order(root.rchild)

    # 後續周遊(先遞歸左，後遞歸有，最後列印自己)
    def post_order(self, root):
        if root:
            self.post_order(root.lchild)
            self.post_order(root.rchild)
            print(root.data, end=",")


class AVLNode(BiTreeNode):
    def __init__(self, data):
        BiTreeNode.__init__(self, data)
        self.bf = 0


class AVLTree(BST):
    def __init__(self, li=None):
        BST.__init__(self, li)

    # 左旋
    def rotate_left(self, p, c):
        s2 = c.lchild
        p.rchild = s2
        if s2:
            s2.parent = p
        c.lchild = p
        p.parent = c

        # update balance factor
        p.bf = 0
        c.bf = 0
        return c

    # 右旋
    def rotate_right(self, p, c):
        s2 = c.rchild
        p.lchild = s2
        if s2:
            s2.parent = p

        c.rchild = p
        p.parent = c

        p.bf = 0
        c.bf = 0
        return c

    # 右旋-左旋
    def rotate_right_left(self, p, c):
        g = c.lchild

        s3 = g.rchild
        c.lchild = s3
        if s3:
            s3.parent = c
        g.rchild = c
        c.parent = g

        s2 = g.lchild
        p.lchild = s2
        if s2:
            s2.parent = p
        g.lchild = p
        p.parent = g

        # update balance factor
        if g.bf > 0:   # 插入g的左邊
            p.bf = -1
            c.bf = 0
        elif g.bf < 0: # 插入g的右邊
            p.bf = 0
            c.bf = 1
        else:  # 插入的是g
            p.bf = 0
            c.bf = 0
        g.bf = 0
        return g

        # 左旋-右旋
    def rotate_left_right(self, p, c):
        g = c.rchild

        s2 = g.lchild
        c.rchild = s2
        if s2:
            s2.parent = c
        g.lchild = c
        c.parent = g

        s3 = g.rchild
        p.lchild = s3
        if s3:
            s3.parent = p
        g.rchild = p
        p.parent = g

        if g.bf < 0:
            p.bf = 1
            c.bf = 0
        elif g.bf > 0:
            p.bf = 0
            c.bf = -1
        else:
            p.bf = 0
            c.bf = 0
        g.bf = 0
        return g

    def insert_no_rec(self, val):
        # 步驟1: 和BST一樣，先插入
        p = self.root
        if not p:  # 空樹
            self.root = BiTreeNode(val)
            return
        while True:
            if val < p.data:
                if p.lchild:  # 如果p存在左孩子
                    p = p.lchild
                else:        # 如果p不存在左孩子
                    p.lchild = BiTreeNode(val)
                    p.lchild.parent = p
                    node = p.lchild  # node儲存的就是插入的節點
                    break
            elif val > p.data:
                if p.rchild:
                    p = p.rchild
                else:
                    p.rchild = BiTreeNode(val)
                    p.rchild.parent = p
                    node = p.rchild
                    break
            else:
                return

        # 步驟2: update balance factor
        while node.parent:
            # 傳遞是從左子樹來的，左子樹更沉了
            if node.parent.lchild == node:
                # 更新node.parent的bf -= 1
                if node.parent.bf < 0:  # 原來node.parent.bf == -1, 更新後變成-2
                    # 作旋轉
                    # 看node哪邊沉
                    g = node.parent.parent  # 為了連接配接旋轉之後的子樹
                    x = node.parent  # 旋轉前的子樹的根
                    if node.bf > 0:
                        n = self.rotate_left_right(node.parent, node)
                    else:
                        n = self.rotate_right(node.parent, node)
                    # 把n和g連起來
                elif node.parent.bf > 0:  # 原來node.parent.bf == -1, 更新後變成0
                    node.parent.bf = 0
                    break
                else:  # 原來node.parent.bf = 0, 更新後變成-1
                    node.parent.bf = -1
                    node = node.parent
                    continue

            # 傳遞是從右子樹來的，右子樹更沉了
            else:
                # 更新node.parent.bf += 1
                if node.parent.bf > 0:  # 原來node.parent.bf == 1, 更新後變成2
                    # 作旋轉
                    # 看node哪邊沉
                    g = node.parent.parent  # 為了連接配接旋轉之後的子樹
                    x = node.parent  # 旋轉前的子樹的根
                    if node.bf < 0:  # node.bf = 1
                        n = self.rotate_right_left(node.parent, node)
                    else:
                        n = self.rotate_left(node.parent, node)
                    # 記得連起來
                elif node.parent.bf < 0:  # 原來node.parent.bf == -1, 更新後變成0
                    node.parent.bf = 0
                    break
                else:  # 原來node.parent.bf = 0, 更新後變成1
                    node.parent.bf = 1
                    node = node.parent
                    continue

            # 連接配接旋轉後的子樹
            n.parent = g
            if g:
                if node.parent == g.lchild:
                    g.lchild = n
                else:
                    g.rchild = n
                break
            else:
                self.root = n
                break


tree = AVLTree([9, 8, 7, 6, 5, 4, 3, 2, 1])
tree.pre_order(tree.root)
print("")
tree.in_order(tree.root)
資料結構(Python) 資料結構 Python avl樹
上一篇: spring容器初始化過程中出現異常_spring容器什麼時候啟動
下一篇: 常用的算法和資料結構 面試_資料結構與算法面試題80道

繼續閱讀