企业官网建设流程全解析

制作网站多少钱一个,北京网站建设联系电话,购物网站建设咨询,滕州网站建设培训一、平衡二叉树#xff08;AVL 树#xff09; 设计目的#xff1a;保证二叉排序树的高度为 $ O(\log_2 n) $#xff0c;使插入、删除、查找等操作的最坏时间复杂度稳定在 $ O(\log_2 n) $。普通二叉排序树在极端情况下可能退化为链表#xff0c;导致操作时间复杂度上升至 …一、平衡二叉树AVL 树设计目的保证二叉排序树的高度为 $ O(\log_2 n) $使插入、删除、查找等操作的最坏时间复杂度稳定在 $ O(\log_2 n) $。普通二叉排序树在极端情况下可能退化为链表导致操作时间复杂度上升至 $ O(n) $。核心定义满足BST 性质即对于任意节点左子树所有节点值小于根节点值右子树所有节点值大于根节点值。平衡条件任一节点的左右子树高度差称为平衡因子的绝对值不超过 1。平衡因子 左子树深度 - 右子树深度其值只能是 -1、0 或 1。高度特性含有 $ n $ 个节点的 AVL 树其最大高度约为 $ 1.44 \log_2 n $远优于最坏情况下的 $ O(n) $接近完全二叉树的理想高度 $ \log_2 n $。为了维持平衡在插入或删除节点后若出现不平衡平衡因子变为 ±2需通过旋转操作单旋LL、RR双旋LR、RL进行调整恢复平衡。二、线索二叉树Threaded Binary Tree设计目的解决普通二叉树中无法高效获取某节点在中序遍历中的前驱和后继的问题。同时利用原本浪费的空指针域n 个节点共有 $ n1 $ 个空指针来存储有用的线索信息提高空间利用率和遍历效率。实现方式将空的左指针改为指向该节点在中序遍历中的前驱节点。将空的右指针改为指向该节点在中序遍历中的后继节点。引入两个标志位ltag0 表示左指针指向左孩子1 表示左指针为线索指向前驱。rtag0 表示右指针指向右孩子1 表示右指针为线索指向后继。节点结构示例C语言风格structBTnode{intdata;structBTnode*left,*right;intltag;// 0: child, 1: thread (predecessor)intrtag;// 0: child, 1: thread (successor)};通过中序线索化后可以不使用栈或递归实现高效的中序遍历直接沿线索访问下一个节点。AVL树的四种旋转操作用于在插入或删除节点导致二叉树失去平衡即某个节点的平衡因子变为±2时恢复其平衡性。这些旋转操作根据失衡节点与其子树中“过高”部分的位置关系分为四类LL、RR、LR、RL。一、四种旋转类型及适用场景类型全称触发条件以失衡节点为z场景描述LL型Left-Leftz 的左子树比右子树高 2且 z 的左孩子y的左子树更高平衡因子为 1 或 2失衡路径连续向左形成“左偏左”结构RR型Right-Rightz 的右子树比左子树高 2且 z 的右孩子y的右子树更高平衡因子为 -1 或 -2失衡路径连续向右“右偏右”结构LR型Left-Rightz 的左子树过高但 z 的左孩子的右子树更高先左后右的“Z”字形结构RL型Right-Leftz 的右子树过高但 z 的右孩子的左子树更高先右后左的镜像“Z”字形核心思想通过一次或两次旋转将“过高”的中间节点提升为新的根使树重新满足 AVL 平衡条件。二、旋转操作实现C语言风格假设节点结构如下typedefstructAVLNode{intdata;structAVLNode*left;structAVLNode*right;intheight;// 存储当前节点高度便于计算平衡因子}AVLNode;辅助函数获取高度与平衡因子intmax(inta,intb){return(ab)?a:b;}intheight(AVLNode*node){returnnodeNULL?0:node-height;}intgetBalance(AVLNode*node){returnnodeNULL?0:height(node-left)-height(node-right);}1.右单旋LL旋转适用于 LL 型失衡。AVLNode*rotateRight(AVLNode*y){AVLNode*xy-left;AVLNode*T2x-right;// 执行右旋x-righty;y-leftT2;// 更新高度先更新子节点再更新父节点y-heightmax(height(y-left),height(y-right))1;x-heightmax(height(x-left),height(x-right))1;returnx;// 新的根节点}2.左单旋RR旋转适用于 RR 型失衡。AVLNode*rotateLeft(AVLNode*x){AVLNode*yx-right;AVLNode*T2y-left;// 执行左旋y-leftx;x-rightT2;// 更新高度x-heightmax(height(x-left),height(x-right))1;y-heightmax(height(y-left),height(y-right))1;returny;// 新的根节点}3.左右双旋LR旋转先对左孩子左旋RR再对根右旋LL。AVLNode*rotateLeftRight(AVLNode*z){z-leftrotateLeft(z-left);// 左孩子做一次左旋RRreturnrotateRight(z);// 再整体右旋LL}4.右左双旋RL旋转先对右孩子右旋LL再对根左旋RR。AVLNode*rotateRightLeft(AVLNode*z){z-rightrotateRight(z-right);// 右孩子做一次右旋LLreturnrotateLeft(z);// 再整体左旋RR}三、插入后的平衡调整逻辑示例AVLNode*insert(AVLNode*node,intdata){// 1. 标准BST插入if(nodeNULL){AVLNode*newNode(AVLNode*)malloc(sizeof(AVLNode));newNode-datadata;newNode-leftnewNode-rightNULL;newNode-height1;returnnewNode;}if(datanode-data)node-leftinsert(node-left,data);elseif(datanode-data)node-rightinsert(node-right,data);elsereturnnode;// 不允许重复值// 2. 更新当前节点高度node-heightmax(height(node-left),height(node-right))1;// 3. 获取平衡因子intbalancegetBalance(node);// 4. 判断失衡类型并旋转调整// LL型if(balance1datanode-left-data)returnrotateRight(node);// RR型if(balance-1datanode-right-data)returnrotateLeft(node);// LR型if(balance1datanode-left-data){node-leftrotateLeft(node-left);returnrotateRight(node);}// RL型if(balance-1datanode-right-data){node-rightrotateRight(node-right);returnrotateLeft(node);}returnnode;// 已平衡返回原节点}✅总结记忆口诀“同方向用单旋”LL → 右旋RR → 左旋“异方向用双旋”LR → 先左旋左孩子再右旋根RL → 先右旋右孩子再左旋根