AVL平衡因子旋转
创始人
2024-11-13 01:30:44
0

AVL树是自平衡二叉搜索树,通过旋转来保持树的平衡。平衡因子是左子树高度减去右子树高度的差,当平衡因子的绝对值大于1时,需要进行旋转操作来使树重新保持平衡。 以下是一个示例代码,实现了AVL树中的插入和删除操作,并通过旋转实现了平衡维护。

class AVLTree:
    class Node:
        def __init__(self, val):
            self.val = val
            self.height = 1
            self.left = None
            self.right = None
            
    def __init__(self):
        self.root = None
        
    def height(self, node):
        if node is None:
            return 0
        return node.height

    def balance_factor(self, node):
        if node is None:
            return 0
        return self.height(node.left) - self.height(node.right)

    def left_rotate(self, node):
        right_child = node.right
        node.right = right_child.left
        right_child.left = node

        node.height = 1 + max(self.height(node.left), self.height(node.right))
        right_child.height = 1 + max(self.height(right_child.left), self.height(right_child.right))

        return right_child

    def right_rotate(self, node):
        left_child = node.left
        node.left = left_child.right
        left_child.right = node

        node.height = 1 + max(self.height(node.left), self.height(node.right))
        left_child.height = 1 + max(self.height(left_child.left), self.height(left_child.right))

        return left_child

    def insert(self, node, val):
        if node is None:
            return self.Node(val)

        if val < node.val:
            node.left = self.insert(node.left, val)
        elif val > node.val:
            node.right = self.insert(node.right, val)

        node.height = 1 + max(self.height(node.left), self.height(node.right))
        balance_factor = self.balance_factor(node)

        if balance_factor > 1:

相关内容

热门资讯

最新通报!约局吧是否有挂(辅助... 最新通报!约局吧是否有挂(辅助挂)好像有挂(有挂总结辅助软件)1)免费钻石:进一步探索免费脚本大陆,...
一分钟了解!德州之星扫描器(辅... 一分钟了解!德州之星扫描器(辅助挂)确实是真的有挂(有挂秘笈辅助插件)在进入软件靠谱后,参与本局比赛...
玩家必看教程!wpk俱乐部有没... 玩家必看教程!wpk俱乐部有没有辅助(辅助挂)总是是真的有挂(有挂头条辅助app)一、可以开透视的定...
分享实测!hhpoker德州作... 分享实测!hhpoker德州作弊(辅助挂)一贯是有挂(的确有挂辅助器)1、下载好透视辅助下载之后点击...
重大科普!aapoker真的假... 重大科普!aapoker真的假的(辅助挂)一贯是真的有挂(真的有挂辅助器)所有人都在同一条线上,像星...
带你了解!聚星ai辅助工具下载... 带你了解!聚星ai辅助工具下载(辅助挂)一直真的有挂(确实有挂辅助攻略)1)免费钻石:进一步探索免费...
记者爆料!wepoker俱乐部... 记者爆料!wepoker俱乐部辅助器(辅助挂)竟然是真的有挂(有挂教程辅助技巧)1、下载好透视辅助下...
必备教程!wpk辅助插件(辅助... 必备教程!wpk辅助插件(辅助挂)本来是有挂(讲解有挂辅助插件)1、许多玩家不知道辅助怎么退出观战2...
一分钟了解!德普之星辅助器怎么... 一分钟了解!德普之星辅助器怎么用(辅助挂)都是是真的有挂(有挂神器辅助技巧)1、在插件功能辅助器技巧...
一分钟教会你!德普之星透视辅助... 一分钟教会你!德普之星透视辅助(辅助挂)本来真的有挂(有挂存在辅助app)1、进入到是否有挂之后,能...