收费的网站怎么做的,网页设计师的要求,电子工程网单片机,地下城封号做任务网站AVL树
AVL树#xff08;Adelson-Velsky和Landis树#xff09;是一种自平衡二叉搜索树。它通过维护树的高度平衡来确保树的操作复杂度为O(log n)。它通过在每个节点上跟踪平衡因子来保持树的平衡。平衡因子是左子树和右子树高度之间的差值。
AVL树的特性
每个节点都有一个平…AVL树
AVL树Adelson-Velsky和Landis树是一种自平衡二叉搜索树。它通过维护树的高度平衡来确保树的操作复杂度为O(log n)。它通过在每个节点上跟踪平衡因子来保持树的平衡。平衡因子是左子树和右子树高度之间的差值。
AVL树的特性
每个节点都有一个平衡因子。平衡因子等于左子树高度减去右子树高度。平衡因子必须为-1、0或1。当插入或删除节点后平衡因子可能会发生改变如果平衡因子超出了-1到1的范围需要通过旋转操作来调整树的结构。
AVL树的操作
AVL树提供了基本的操作包括插入、删除和查找操作。下面是这些操作的C语言实现。
定义节点结构
首先我们定义AVL树的节点结构。节点包含一个整数值 value指向左子树和右子树的指针 left 和 right以及一个表示子树高度的字段 height。
typedef struct AVLNode {int value;int height;struct AVLNode *left;struct AVLNode *right;
} AVLNode;左旋和右旋操作
AVL树使用左旋和右旋操作来调整树的结构确保树的平衡。
// 计算节点的高度
int height(AVLNode *node) {if (node NULL) {return 0;}return node-height;
}// 更新节点的高度
void updateHeight(AVLNode *node) {if (node) {node-height 1 fmax(height(node-left), height(node-right));}
}// 左旋操作
AVLNode* leftRotate(AVLNode *z) {AVLNode *y z-right;AVLNode *T2 y-left;// 执行左旋y-left z;z-right T2;// 更新节点高度updateHeight(z);updateHeight(y);// 返回新的根节点return y;
}// 右旋操作
AVLNode* rightRotate(AVLNode *z) {AVLNode *y z-left;AVLNode *T2 y-right;// 执行右旋y-right z;z-left T2;// 更新节点高度updateHeight(z);updateHeight(y);// 返回新的根节点return y;
}左旋操作将节点 z 的右子树调整为其父节点右旋操作将节点 z 的左子树调整为其父节点。这些操作用于调整树的结构并保持平衡。
平衡因子计算
平衡因子是AVL树的一个重要属性。它表示节点的左子树高度减去右子树高度的差值。
int getBalance(AVLNode *node) {if (node NULL) {return 0;}return height(node-left) - height(node-right);
}插入操作
插入操作在AVL树中插入一个新的值同时确保树保持平衡。插入后需要调整树的结构以保持平衡。
// 插入操作
AVLNode* insert(AVLNode *node, int value) {// 执行标准的二叉搜索树插入操作if (node NULL) {AVLNode *newNode (AVLNode *)malloc(sizeof(AVLNode));newNode-value value;newNode-height 1;newNode-left newNode-right NULL;return newNode;}if (value node-value) {node-left insert(node-left, value);} else if (value node-value) {node-right insert(node-right, value);} else {// 值已存在于树中return node;}// 更新节点的高度updateHeight(node);// 获取平衡因子int balance getBalance(node);// 根据平衡因子进行调整// 左左情况if (balance 1 value node-left-value) {return rightRotate(node);}// 右右情况if (balance -1 value node-right-value) {return leftRotate(node);}// 左右情况if (balance 1 value node-left-value) {node-left leftRotate(node-left);return rightRotate(node);}// 右左情况if (balance -1 value node-right-value) {node-right rightRotate(node-right);return leftRotate(node);}return node;
}插入操作首先执行标准的二叉搜索树插入操作将新值插入树中。然后更新节点的高度并获取平衡因子。根据平衡因子的值决定是否需要进行旋转操作来保持树的平衡。
删除操作
删除操作在AVL树中删除特定值同时确保树保持平衡。删除操作可能需要多种情况处理。
// 找到最小值节点
AVLNode* minValueNode(AVLNode *node) {while (node-left ! NULL) {node node-left;}return node;
}// 删除操作
AVLNode* deleteNode(AVLNode *root, int value) {// 执行标准的二叉搜索树删除操作if (root NULL) {return root;}if (value root-value) {root-left deleteNode(root-left, value);} else if (value root-value) {root-right deleteNode(root-right, value);} else {// 找到要删除的节点if (root-left NULL) {AVLNode *temp root-right;free(root);return temp;} else if (root-right NULL) {AVLNode *temp root-left;free(root);return temp;}// 找到右子树的最小值节点AVLNode *temp minValueNode(root-right);// 复制最小值节点的值到当前节点root-value temp-value;// 递归删除右子树的最小值节点root-right deleteNode(root-right, temp-value);}// 更新节点的高度updateHeight(root);// 获取平衡因子int balance getBalance(root);// 根据平衡因子进行调整// 左左情况if (balance 1 getBalance(root-left) 0) {return rightRotate(root);}// 左右情况if (balance 1 getBalance(root-left) 0) {root-left leftRotate(root-left);return rightRotate(root);}// 右右情况if (balance -1 getBalance(root-right) 0) {return leftRotate(root);}// 右左情况if (balance -1 getBalance(root-right) 0) {root-right rightRotate(root-right);return leftRotate(root);}return root;
}删除操作首先执行标准的二叉搜索树删除操作。删除后更新节点的高度并获取平衡因子。根据平衡因子的值决定是否需要进行旋转操作来保持树的平衡。
查找操作
查找操作在AVL树中查找特定值。查找过程与二叉搜索树类似但AVL树能够在操作后确保树的平衡。
AVLNode* search(AVLNode* node, int value) {if (node NULL || node-value value) {return node;}// 根据值的大小决定查找方向if (value node-value) {return search(node-left, value);} else {return search(node-right, value);}
}查找操作递归地遍历树根据值的大小选择左子树或右子树进行查找。
总结
AVL树是一种自平衡二叉搜索树通过维护树的高度平衡来确保树的操作复杂度为O(log n)。它提供了查找、插入和删除操作的对数时间复杂度非常适合需要快速操作和高性能的数据结构。
