课程设计代做网站php,免费高清网站在线观看,wordpress用户仪表盘如何设计,怎么写app程序AVL树是首个被发明的自平衡二叉查找树#xff0c;在1962年由两位苏联科学家G.M. Adelson-Velsky和E.M. Landis提出。AVL树得名于发明者的首字母。在AVL树中#xff0c;任何节点的两个子树的高度最大差别为一#xff0c;确保了树的平衡度#xff0c;使得查找操作相比于普通的…AVL树是首个被发明的自平衡二叉查找树在1962年由两位苏联科学家G.M. Adelson-Velsky和E.M. Landis提出。AVL树得名于发明者的首字母。在AVL树中任何节点的两个子树的高度最大差别为一确保了树的平衡度使得查找操作相比于普通的二叉查找树更加高效。
AVL树的性质
AVL树保持了二叉查找树的基础性质即对于任何一个节点其左子树上的所有节点的值都小于该节点的值右子树所有节点的值都大于该节点的值。此外AVL树增加了以下平衡条件
平衡因子 AVL树中的每个节点的平衡因子被定义为左子树的高度减去右子树的高度有些定义为相反。给定的每个节点的平衡因子必须是-1、0或1。
这种强制的平衡条件确保树的最坏情况下的高度为O(log n)其中n是树中节点的数量从而也保证了查找/插入/删除操作都可以在对数时间内完成。
AVL树的旋转操作
保持AVL树平衡的主要机制是通过旋转操作分为四种基本旋转 LL左左旋转 当在节点的左子树的左侧插入导致不平衡时进行。通过一个右旋转来平衡树。 RR右右旋转 当在节点的右子树的右侧插入导致不平衡时进行。通过一个左旋转来平衡树。 LR左右旋转 当在节点的左子树的右侧插入导致不平衡时进行。首先在导致失衡节点的左子树上进行左旋转然后对该节点进行右旋转。 RL右左旋转 当在节点的右子树的左侧插入导致不平衡时进行。首先在导致失衡节点的右子树上进行右旋转然后对该节点进行左旋转。
这些旋转能够在维持二叉查找树的性质的同时回复AVL树特有的平衡性质。
AVL树的插入操作
向AVL树插入一个新的节点大体分为三步 常规二叉搜索树插入 首先按照二叉搜索树的规则将节点插入正确位置。 更新平衡因子 从插入点开始向上遍历回根节点更新祖先节点的平衡因子。 重新平衡如果必要 如果在更新过程中某个节点的平衡因子变为非-1、0或1将对该节点进行一次或多次旋转操作以恢复平衡。这可能涉及上述四种旋转中的任何一种或复合旋转。
AVL树的删除操作
从AVL树中删除一个节点包括了以下步骤 常规二叉搜索树删除 遵循二叉搜索树的规则找到并删除该节点这可能涉及将节点与其直接后继互换的操作。 更新平衡因子 从删除节点的父节点开始向上遍历到根节点更新节点的平衡因子。 重新平衡如果必要 如果在更新过程中某个节点的平衡因子不是-1、0或1将对该节点执行相应的旋转操作恢复平衡。
删除操作要复杂些因为可能需要在不同层上多次进行平衡调整。
深度分析
AVL树的设计主旨是维持二叉查找树在动态更新操作下的平衡从而避免性能恶化。为了保持深入的讨论我们将分别撷取关键方面进行详尽的分析。
平衡因子计算
AVL树中每个节点N都有一个平衡因子BF它是根据以下公式定义的
平衡因子(BF) 高度(左子树) - 高度(右子树)常规情况下左子树或右子树的高度的计算是从当前节点向下递归到叶子节点计算最长路径上边的数量叶子节点的高度定义为0。因此
BF 0 表示左子树和右子树的高度相同。BF -1 表示右子树比左子树高1层。BF 1 表示左子树比右子树高1层。
AVL树要求所有节点的平衡因子绝对值必须小于或等于1。每次插入或删除操作后都需要更新从影响节点到根节点路径上所有节点的平衡因子并进行相应的旋转操作以恢复平衡性。
旋转操作
旋转是用来恢复AVL树平衡的一种操作。在不同的情形下可能需要不同种类的旋转操作
LL旋转
当一个节点N的左子树的左边产生了一个新节点并造成不平衡时会进行LL旋转。以下是LL旋转的步骤
设N为失衡节点L为N的左子节点。将L的右子树移动成N的左子树。将N变成L的右子树。
RR旋转
这是LL的镜像操作当一个节点N的右子树的右边产生了一个新节点并造成不平衡时会进行RR旋转。以下是RR旋转的步骤
设N为失衡节点R为N的右子节点。将R的左子树移动成N的右子树。将N变成R的左子树。
LR旋转
当一个节点N的左子树的右边产生了一个新节点并造成不平衡时会进行LR旋转。LR旋转首先进行L的RR旋转然后对N进行LL旋转。
设N为失衡节点L为N的左子节点LR为L的右子节点。对L进行RR旋转。对N进行LL旋转。
RL旋转
这是LR旋转的镜像当一个节点N的右子树的左边产生了一个新节点并造成不平衡时会进行RL旋转。
设N为失衡节点R为N的右子节点RL为R的左子节点。对R进行LL旋转。对N进行RR旋转。
插入操作
插入操作可以概括为以下步骤
插入新节点X像在常规二叉查找树中那样。更新从X到根节点的路径上所有节点的平衡因子。检查这些节点的平衡因子如果发现任何节点的平衡因子变为2或-2那么从最低的不平衡点开始进行旋转操作来恢复平衡。
伪代码示例
function insert(node, value)if node nullreturn newNode(value)if value node.valuenode.left insert(node.left, value)else if value node.valuenode.right insert(node.right, value)elsereturn node// 更新节点的高度node.height 1 max(height(node.left), height(node.right))// 获取平衡因子balance getBalance(node)// 平衡if balance 1 and value node.left.valuereturn rightRotate(node)if balance -1 and value node.right.valuereturn leftRotate(node)if balance 1 and value node.left.valuenode.left leftRotate(node.left)return rightRotate(node)if balance -1 and value node.right.valuenode.right rightRotate(node.right)return leftRotate(node)return node删除操作
删除操作遵循以下步骤
在树中定位并删除指定节点。更新从删除节点的父节点到根节点的路径上所有节点的平衡因子。对失去平衡的节点进行旋转操作恢复平衡。
伪代码示例
function deleteNode(root, value)// STEP 1: PERFORM STANDARD BST DELETEif root nullreturn rootif value root.valueroot.left deleteNode(root.left, value)else if value root.valueroot.right deleteNode(root.right, value)else// node with only one child or no childif (root.left null) or (root.right null)temp nullif temp root.lefttemp root.rightelsetemp root.leftif temp null // No child casetemp rootroot nullelse // One child caseroot temp // Copy the contents of the non-empty childelse// node with two children: Get the inorder successortemp minValueNode(root.right)root.value temp.valueroot.right deleteNode(root.right, temp.value)if root nullreturn root// STEP 2: UPDATE HEIGHT OF THE CURRENT NODEroot.height max(height(root.left), height(root.right)) 1// STEP 3: GET THE BALANCE FACTOR OF THIS NODEbalance getBalance(root)// If this node becomes unbalanced, then there are 4 cases// Left Left Caseif balance 1 and getBalance(root.left) 0return rightRotate(root)// Left Right Caseif balance 1 and getBalance(root.left) 0root.left leftRotate(root.left)return rightRotate(root)// Right Right Caseif balance -1 and getBalance(root.right) 0return leftRotate(root)// Right Left Caseif balance -1 and getBalance(root.right) 0root.right rightRotate(root.right)return leftRotate(root)return root操作效率分析
由于AVL树的严格平衡特性插入和删除操作可能要求多次旋转这增加了操作的复杂性。尽管如此由于树的高度被严格控制在O(log n)因此插入和删除操作的最坏情况时间复杂度为O(log n)。实际的旋转操作仅涉及改变节点几个指针因此可以认为是O(1)操作不过这会在插入或删除后沿着路径向上逐步进行因此总的旋转成本是O(log n)。由于我们只会在最坏的情况下沿着路径上旋转一次所以这样的成本是可以接受的。
不同旋转操作情景的剖析
旋转操作虽然以四类基本操作来定义但是每种操作对树的结构和平衡因子都有不同的影响。例如LL旋转是对树的一边性质最直接的补救它通过一次简单的旋转即可恢复平衡。而LR旋转则涉及到两个步骤首先是对失衡节点的左子节点进行RR旋转然后对失衡节点本身进行LL旋转。这意味着在执行LR旋转时我们需要更新不仅是失衡节点同时也要更新其左子节点及LR节点的平衡因子。从逻辑上讲LR旋转处理的是两种不平衡因子的组合因此在理解和实现时需要更多的注意。
AVL树的维护需要对树的结构和旋转操作有深刻的理解。每次插入和删除操作后都可能要求维护这种平衡而这种保持平衡的要求是AVL树能够保持其性能特点的根本。
如果你想更深入地了解人工智能的其他方面比如机器学习、深度学习、自然语言处理等等也可以点击这个链接我按照如下图所示的学习路线为大家整理了100多G的学习资源基本涵盖了人工智能学习的所有内容包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料可以帮助你入门和进阶。
链接 人工智能交流群【最新顶会与项目实战】点击跳转
