C++ AVL树

目录

​编辑

0.前言

1.AVL树的概念

1.1 平衡因子

1.2 AVL树的性质

2.AVL树节点的定义

3.AVL树的插入

4.AVL树的旋转

4.1 左单旋(LL旋转)

4.2 右单旋(RR旋转)

4.3 右左旋(RL旋转)

4.4 左右旋(LR旋转)

5.AVL树的验证

6.AVL树的删除

7.AVL树的性能

7.1时间复杂度

7.1.1 查找操作

7.1.2 插入操作

7.1.3.删除操作

7.2空间复杂度

7.2.1存储空间

7.2.2递归调用栈空间

8.完整代码

9.小结


(图像由AI生成) 

0.前言

在计算机科学中,二叉搜索树是一种常用的数据结构,主要用于快速查找、插入和删除操作。然而,当插入的数据是有序或接近有序时,普通的二叉搜索树可能会退化成链表,从而降低操作效率。为了解决这一问题,1962年,两位俄罗斯数学家G.M. Adelson-Velskii和E.M. Landis发明了AVL树。AVL树是一种自平衡的二叉搜索树,通过对节点的高度进行调整,保证了查找、插入和删除操作的高效性。本文将详细介绍AVL树的概念、节点定义、插入、旋转、验证、删除以及其性能。

1.AVL树的概念

AVL树是一种自平衡的二叉搜索树,由G.M. Adelson-Velskii和E.M. Landis在1962年发明。其主要目的是解决普通二叉搜索树在插入数据有序或接近有序时可能退化成链表的问题。AVL树通过在每次插入或删除节点后自动调整树的结构,使得任何节点的左右子树高度之差(平衡因子)的绝对值不超过1,从而保证了树的高度尽可能小,进而提高查找、插入和删除操作的效率。

1.1 平衡因子

平衡因子(Balance Factor, BF)是AVL树中每个节点的一个重要属性,用于衡量节点的左右子树的高度差。具体定义如下:

BF=右子树的高度−左子树的高度BF=右子树的高度−左子树的高度

对于AVL树中的每个节点,其平衡因子的取值只能是-1、0或1:

  • 平衡因子为0:表示节点的左子树和右子树高度相同。
  • 平衡因子为1:表示节点的右子树高度比左子树高1。
  • 平衡因子为-1:表示节点的左子树高度比右子树高1。

1.2 AVL树的性质

一棵AVL树具有以下性质:

  1. 二叉搜索树性质:对于每个节点,其左子树的所有节点值都小于该节点的值,右子树的所有节点值都大于该节点的值。
  2. 自平衡性质:对于每个节点,其左右子树的高度差(即平衡因子)的绝对值不超过1。具体来说,一棵AVL树要么是空树,要么是具有以下性质的二叉搜索树:
    • 它的左右子树都是AVL树。
    • 左右子树高度之差的绝对值不超过1。

通过保持上述性质,AVL树在最坏情况下的高度也能控制在 O(logn) 级别,从而确保了查找、插入和删除操作的时间复杂度也维持在 O(logn)。

2.AVL树节点的定义

AVL树的每个节点包含存储数据的字段以及指向其子节点和父节点的指针。除此之外,每个节点还有一个平衡因子,用于记录右子树和左子树的高度差,以便在需要时进行旋转操作来维持AVL树的平衡。

以下是AVL树节点的C++模板定义:

template <class T>
struct AVLTreeNode {T _data;  // 节点存储的数据AVLTreeNode<T>* _left;  // 指向左子节点的指针AVLTreeNode<T>* _right;  // 指向右子节点的指针AVLTreeNode<T>* _parent;  // 指向父节点的指针int _bf;  // 平衡因子,右子树高度减去左子树高度// 构造函数,初始化节点数据及指针AVLTreeNode(const T& x = T()): _data(x), _left(NULL), _right(NULL), _parent(NULL), _bf(0) {}
};

节点属性说明

  • _data:节点存储的数据,可以是任何类型。
  • _left:指向左子节点的指针。如果左子节点不存在,则为NULL。
  • _right:指向右子节点的指针。如果右子节点不存在,则为NULL。
  • _parent:指向父节点的指针。如果节点是根节点,则为NULL。
  • _bf:平衡因子,表示右子树的高度减去左子树的高度。平衡因子用于AVL树的平衡维护,其值只能为-1、0或1。

3.AVL树的插入

AVL树是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。AVL树的插入过程可以分为两步:1. 按照二叉搜索树的方式插入新节点;2. 调整节点的平衡因子。

1. 按照二叉搜索树的方式插入新节点

首先,按照二叉搜索树的规则找到新节点应插入的位置,并将其插入树中。具体过程如下:

  • 从根节点开始,比较新节点的值与当前节点的值。
  • 如果新节点的值小于当前节点的值,则移动到左子节点;否则,移动到右子节点。
  • 重复上述步骤,直到找到一个空位置,将新节点插入该位置。

2. 调整节点的平衡因子

新节点插入后,需要调整路径上所有节点的平衡因子。具体过程如下:

  1. 如果新节点插入到父节点的左侧,只需将父节点的平衡因子减1。
  2. 如果新节点插入到父节点的右侧,只需将父节点的平衡因子加1。

此时,父节点的平衡因子可能有三种情况:0,±1,±2。

  • 平衡因子为0:说明插入之前父节点的平衡因子为±1,插入后被调整成0,此时满足AVL树的性质,插入成功。
  • 平衡因子为±1:说明插入前父节点的平衡因子一定为0,插入后被更新成±1,此时以父节点为根的树的高度增加,需要继续向上更新。
  • 平衡因子为±2:则父节点的平衡因子违反平衡树的性质,需要对其进行旋转处理(具体旋转处理代码在此省略)。

以下是AVL树插入操作的伪代码,省略了具体的旋转处理部分:

template <class T>
class AVLTree {
public:bool Insert(const T& data) {if (_root == nullptr) {_root = new AVLTreeNode<T>(data);return true;}AVLTreeNode<T>* pParent = nullptr;AVLTreeNode<T>* pCur = _root;// 按照二叉搜索树的方式找到插入位置while (pCur) {pParent = pCur;if (data < pCur->_data) {pCur = pCur->_left;} else if (data > pCur->_data) {pCur = pCur->_right;} else {return false; // 树中已存在相同的值}}// 创建新节点并插入pCur = new AVLTreeNode<T>(data);if (data < pParent->_data) {pParent->_left = pCur;} else {pParent->_right = pCur;}pCur->_parent = pParent;// 调整平衡因子while (pParent) {if (pCur == pParent->_left) {pParent->_bf -= 1;} else {pParent->_bf += 1;}if (pParent->_bf == 0) {break; // 插入前平衡因子为±1,插入后被调整成0} else if (pParent->_bf == 1 || pParent->_bf == -1) {pCur = pParent;pParent = pParent->_parent;} else {// 需要旋转处理// 省略具体的旋转处理代码break;}}return true;}private:AVLTreeNode<T>* _root = nullptr;
};

在上面的伪代码中,Insert 函数首先按照二叉搜索树的规则找到插入位置,并将新节点插入树中。接着,通过调整路径上所有节点的平衡因子,维护AVL树的平衡性。如果发现某个节点的平衡因子为±2,则需要进行旋转处理以恢复平衡(具体旋转处理代码在此省略)。 

4.AVL树的旋转

在AVL树中,为了保持平衡性,需要在插入或删除节点后进行旋转操作。旋转的目的是调整节点的高度和结构,使得每个节点的平衡因子在[-1, 1]之间。下面详细介绍左单旋、右单旋、右左旋、左右旋的原理和实现,并通过复杂的例子进行说明。

4.1 左单旋(LL旋转)

左单旋用于修正因为在右子树中插入节点导致的不平衡情况。

插入之前的树:

    A\B\C

插入节点D导致A的平衡因子为2,需要进行左单旋。

旋转后的树:

    B/ \A   C

 下面是左单旋的代码实现:

void RotateL(pNode parent) {pNode subR = parent->_right;pNode subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;pNode parentParent = parent->_parent;parent->_parent = subR;subR->_parent = parentParent;if (parentParent == nullptr)_root = subR;else {if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;}parent->_bf = subR->_bf = 0;
}

4.2 右单旋(RR旋转)

右单旋用于修正因为在左子树中插入节点导致的不平衡情况。

插入之前的树:

      C/B/A

插入节点A导致C的平衡因子为-2,需要进行右单旋。

旋转后的树:

    B/ \A   C

  

下面是右单旋的代码实现:

void RotateR(pNode parent) {pNode subL = parent->_left;pNode subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;pNode parentParent = parent->_parent;parent->_parent = subL;subL->_parent = parentParent;if (parentParent == nullptr)_root = subL;else {if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;}parent->_bf = subL->_bf = 0;
}

4.3 右左旋(RL旋转)

右左旋用于修正因为在右子树的左子树中插入节点导致的不平衡情况。

插入之前的树:

    A\C/B

插入节点B导致A的平衡因子为2,且C的平衡因子为-1,需要进行右左旋。

旋转后的树:

    B/ \A   C

 

下面是右左双旋的代码实现:

void RotateRL(pNode parent) {pNode subR = parent->_right;pNode subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1) {parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;} else if (bf == -1) {parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;} else { // bf == 0parent->_bf = subR->_bf = subRL->_bf = 0;}
}

4.4 左右旋(LR旋转)

左右旋用于修正因为在左子树的右子树中插入节点导致的不平衡情况。

插入之前的树:

    C/A\B

插入节点B导致C的平衡因子为-2,且A的平衡因子为1,需要进行左右旋。

旋转后的树:

    B/ \A   C

 下面是左右双旋的代码实现:

void RotateLR(pNode parent) {pNode subL = parent->_left;pNode subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1) {parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;} else if (bf == -1) {parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;} else { // bf == 0parent->_bf = subL->_bf = subLR->_bf = 0;}
}

5.AVL树的验证

在AVL树中,验证树的平衡性是确保其高效操作的关键步骤。验证的目的是检查每个节点的平衡因子是否在[-1, 1]之间,并且树的高度是否符合平衡二叉搜索树的性质。通过验证,可以确认树在插入和删除操作后仍然保持平衡。

验证的步骤

  1. 遍历整棵树:使用递归或迭代的方法遍历树的所有节点。
  2. 计算平衡因子:对于每个节点,计算其左子树和右子树的高度差,得到平衡因子。
  3. 检查平衡因子:验证每个节点的平衡因子是否在[-1, 1]之间。
  4. 验证递归结果:对于每个子树,递归地检查其平衡性。

验证的伪代码

以下是验证AVL树的平衡性的伪代码:

template <class T>
class AVLTree {
public:bool IsBalanced() {return IsBalanced(_root);}private:struct AVLTreeNode {T _data;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf; // balance factorAVLTreeNode(const T& x = T()): _data(x), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}};AVLTreeNode* _root = nullptr;bool IsBalanced(AVLTreeNode* node) {if (node == nullptr)return true;int leftHeight = GetHeight(node->_left);int rightHeight = GetHeight(node->_right);int balanceFactor = rightHeight - leftHeight;if (balanceFactor < -1 || balanceFactor > 1)return false;return IsBalanced(node->_left) && IsBalanced(node->_right);}int GetHeight(AVLTreeNode* node) {if (node == nullptr)return 0;return 1 + std::max(GetHeight(node->_left), GetHeight(node->_right));}
};

详细解释

  1. IsBalanced() 方法:这是验证树是否平衡的入口方法。它调用私有方法 IsBalanced(AVLTreeNode* node) 对根节点进行验证。
  2. IsBalanced(AVLTreeNode node) 方法*:这是递归验证每个节点是否平衡的方法。
    • 如果节点为空,返回 true
    • 计算节点的左子树和右子树的高度。
    • 计算平衡因子 balanceFactor
    • 如果平衡因子超出 [-1, 1],返回 false
    • 递归验证左右子树。
  3. GetHeight(AVLTreeNode node) 方法*:这是计算节点高度的辅助方法。
    • 如果节点为空,返回 0。
    • 递归计算左右子树的高度,并返回较大者加 1。

6.AVL树的删除

AVL树的删除操作相较于普通二叉搜索树的删除,需要额外考虑树的平衡性问题。删除节点后,必须检查并调整树的平衡,以确保AVL树的性质不被破坏。

AVL树的删除过程可以分为三个主要步骤:

  1. 找到要删除的节点:按照二叉搜索树的删除规则,找到并删除指定节点。
  2. 更新平衡因子:删除节点后,沿路径向上更新所有相关节点的平衡因子。
  3. 旋转调整:如果某个节点的平衡因子超出[-1, 1]范围,则需要通过旋转操作来恢复树的平衡。

删除节点的详细步骤

  1. 找到并删除节点

    • 如果要删除的节点没有子节点,直接删除该节点。
    • 如果要删除的节点只有一个子节点,用该子节点替代被删除节点。
    • 如果要删除的节点有两个子节点,用其右子树的最小节点(或左子树的最大节点)替代被删除节点,并递归删除该最小节点(或最大节点)。
  2. 更新平衡因子

    • 从删除节点的位置向上,逐层更新节点的平衡因子。
    • 如果某个节点的平衡因子变为±2,则需要进行旋转操作来恢复平衡。
  3. 旋转调整

    • 根据节点的平衡因子值和子树的平衡因子,选择合适的旋转操作进行调整。
    • 旋转操作包括单旋转(左旋和右旋)和双旋转(左右旋和右左旋)。

删除操作的伪代码

以下是AVL树删除操作的伪代码:

template <class T>
class AVLTree {
public:bool Delete(const T& data) {return Delete(_root, data);}private:AVLTreeNode* _root = nullptr;bool Delete(AVLTreeNode*& root, const T& data) {if (root == nullptr)return false;if (data < root->_data) {if (!Delete(root->_left, data))return false;} else if (data > root->_data) {if (!Delete(root->_right, data))return false;} else {if (root->_left == nullptr || root->_right == nullptr) {AVLTreeNode* temp = root;root = (root->_left) ? root->_left : root->_right;if (root)root->_parent = temp->_parent;delete temp;} else {AVLTreeNode* minNode = FindMin(root->_right);root->_data = minNode->_data;Delete(root->_right, minNode->_data);}}// 更新平衡因子并进行旋转调整if (root == nullptr)return true;UpdateBalanceFactor(root);return Balance(root);}AVLTreeNode* FindMin(AVLTreeNode* node) {while (node->_left)node = node->_left;return node;}void UpdateBalanceFactor(AVLTreeNode* node) {int leftHeight = GetHeight(node->_left);int rightHeight = GetHeight(node->_right);node->_bf = rightHeight - leftHeight;}int GetHeight(AVLTreeNode* node) {if (node == nullptr)return 0;return 1 + std::max(GetHeight(node->_left), GetHeight(node->_right));}bool Balance(AVLTreeNode*& node) {if (node->_bf == -2) {if (node->_left->_bf <= 0)RotateR(node);elseRotateLR(node);} else if (node->_bf == 2) {if (node->_right->_bf >= 0)RotateL(node);elseRotateRL(node);}return true;}};

7.AVL树的性能

AVL树是一种自平衡的二叉搜索树,其主要特点是保持树的高度尽可能低,从而保证查找、插入和删除操作的高效性。下面将详细介绍AVL树在时间复杂度和空间复杂度方面的性能。

7.1时间复杂度

7.1.1 查找操作

在AVL树中,查找操作的时间复杂度与树的高度密切相关。由于AVL树始终保持平衡,其高度始终在 O(logn) 级别,因此查找操作的时间复杂度为:O(logn)

7.1.2 插入操作

插入操作包括按照二叉搜索树的规则插入节点和调整树的平衡。具体步骤如下:

  1. 按照二叉搜索树的规则找到插入位置并插入节点,时间复杂度为 O(logn)。
  2. 插入后,从插入点向上回溯,更新平衡因子并进行必要的旋转操作。每次旋转操作的时间复杂度为常数 O(1),最多进行 O(logn) 次旋转。

因此,插入操作的总体时间复杂度为:O(logn)

7.1.3.删除操作

删除操作包括按照二叉搜索树的规则删除节点和调整树的平衡。具体步骤如下:

  1. 按照二叉搜索树的规则找到并删除节点,时间复杂度为 O(logn)。
  2. 删除后,从删除点向上回溯,更新平衡因子并进行必要的旋转操作。每次旋转操作的时间复杂度为常数 O(1),最多进行O(logn) 次旋转。

因此,删除操作的总体时间复杂度为:O(logn)

7.2空间复杂度

7.2.1存储空间

AVL树的节点结构与普通二叉搜索树类似,但每个节点增加了一个平衡因子(或高度信息)。因此,AVL树的空间复杂度主要由节点数量决定,为:O(n)

7.2.2递归调用栈空间

在插入、删除和查找操作中,递归调用栈的最大深度等于树的高度。由于AVL树的高度始终在 O(logn) 级别,因此递归调用栈的空间复杂度为:O(logn)

8.完整代码

#include <iostream>
using namespace std;template <class T>
struct AVLTreeNode
{T _data;AVLTreeNode<T>* _left;AVLTreeNode<T>* _right;AVLTreeNode<T>* _parent;int _bf;//balance factorAVLTreeNode(const T& x=T()):_data(x), _left(NULL), _right(NULL), _parent(NULL), _bf(0){}
};template <class T>
class AVLTree
{typedef AVLTreeNode<T> Node;typedef Node* pNode;
private:pNode _root;
public:AVLTree() :_root(nullptr) {}~AVLTree(){Destroy();}void RotateL(pNode parent){pNode subR = parent->_right;pNode subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;pNode parentParent = parent->_parent;parent->_parent = subR;subR->_parent = parentParent;if (parentParent == nullptr)_root = subR;else{if (parentParent->_left == parent)parentParent->_left = subR;elseparentParent->_right = subR;}parent->_bf = subR->_bf = 0;}void RotateR(pNode parent){pNode subL = parent->_left;pNode subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;pNode parentParent = parent->_parent;parent->_parent = subL;subL->_parent = parentParent;if (parentParent == nullptr)_root = subL;else{if (parentParent->_left == parent)parentParent->_left = subL;elseparentParent->_right = subL;}parent->_bf = subL->_bf = 0;}void RotateRL(pNode parent){pNode subR = parent->_right;pNode subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else //bf == 0{parent->_bf = subR->_bf = subRL->_bf = 0;}}void RotateLR(pNode parent){pNode subL = parent->_left;pNode subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else //bf == 0{parent->_bf = subL->_bf = subLR->_bf = 0;}}void _Destroy(pNode node) {if (node) {_Destroy(node->_left);_Destroy(node->_right);delete node;}}void Destroy() {_Destroy(_root);_root = nullptr;}bool Insert(const T& data){if (_root == nullptr){_root = new Node(data);return true;}pNode parent = nullptr;pNode cur = _root;while (cur){if (cur->_data == data)return false;parent = cur;if (cur->_data > data)cur = cur->_left;elsecur = cur->_right;}cur = new Node(data);if (parent->_data > data)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//更新平衡因子while (parent){if (parent->_left == cur)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0)break;if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;}else{if (parent->_bf == 2){if (cur->_bf == 1)RotateL(parent);elseRotateRL(parent);}else{if (cur->_bf == -1)RotateR(parent);elseRotateLR(parent);}break;}}return true;}pNode Find(const T& data){pNode cur = _root;while (cur){if (cur->_data == data)return cur;else if (cur->_data > data)cur = cur->_left;elsecur = cur->_right;}return nullptr;}void _InOrder(pNode p)const//从根节点开始中序遍历{if (p){_InOrder(p->_left);cout << p->_data << " ";_InOrder(p->_right);}}void InOrder()const{_InOrder(_root);}
};

9.小结

本文详细介绍了AVL树的概念、节点定义、插入、旋转、验证、删除及性能。AVL树通过严格维护节点的平衡因子,在插入和删除操作后通过旋转调整保持树的高度在 O(logn),从而保证查找、插入和删除操作的高效性,适用于频繁动态操作的数据管理场景。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/380214.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

集群架构-web服务器(接入负载均衡+数据库+会话保持redis)--15454核心配置详解

紧接着前面的集群架构深化—中小型公司&#xff08;拓展到大型公司业务&#xff09;–下面图简单回顾一下之前做的及故障核心知识总结&#xff08;等后期完全整理后&#xff0c;上传资源希望能帮大家&#xff09; web集群架构-接入负载均衡部署web02服务器等 web集群-搭建web0…

介绍 Elasticsearch 中的 Learning to Tank - 学习排名

作者&#xff1a;来自 Elastic Aurlien Foucret 从 Elasticsearch 8.13 开始&#xff0c;我们提供了原生集成到 Elasticsearch 中的学习排名 (learning to rank - LTR) 实现。LTR 使用经过训练的机器学习 (ML) 模型为你的搜索引擎构建排名功能。通常&#xff0c;该模型用作第二…

postman接口测试实战篇

击杀小游戏接口测试 接口测试简单介绍击杀小游戏代码下载单接口测试(postman)接口关联并参数化接口测试简单介绍 首先思考两个问题:1.接口是什么?2.接口测试是什么? 1.我们总是把接口想的很复杂,其实呢,它就是一个有特定输入和输出参数的交互逻辑处理单元,它不需要知…

通过 EMR Serverless Spark 提交 PySpark 流任务

在大数据快速发展的时代&#xff0c;流式处理技术对于实时数据分析至关重要。EMR Serverless Spark提供了一个强大而可扩展的平台&#xff0c;它不仅简化了实时数据处理流程&#xff0c;还免去了服务器管理的烦恼&#xff0c;提升了效率。本文将指导您使用EMR Serverless Spark…

PostgreSQL使用(二)

说明&#xff1a;本文介绍PostgreSQL的DML语言&#xff1b; 插入数据 -- 1.全字段插入&#xff0c;字段名可以省略 insert into tb_student values (1, 张三, 1990-01-01, 88.88);-- 2.部分字段插入&#xff0c;字段名必须写全 insert into tb_student (id, name) values (2,…

[数据集][目标检测]导盲犬拐杖检测数据集VOC+YOLO格式4635张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;4635 标注数量(xml文件个数)&#xff1a;4635 标注数量(txt文件个数)&#xff1a;4635 标注…

graham 算法计算平面投影点集的凸包

文章目录 向量的内积&#xff08;点乘&#xff09;、外积&#xff08;叉乘&#xff09;确定旋转方向numpy 的 cross 和 outernp.inner 向量与矩阵计算示例np.outer 向量与矩阵计算示例 python 示例生成样例散点数据图显示按极角排序的结果根据排序点计算向量转向并连成凸包 基本…

Linux云计算 |【第一阶段】ENGINEER-DAY3

主要内容&#xff1a; LVM逻辑卷管理、VDO、RAID磁盘阵列、进程管理 一、新建逻辑卷 1、什么是逻辑卷 逻辑卷&#xff08;Logical Volume&#xff09;是逻辑卷管理&#xff08;Logical Volume Management&#xff0c;LVM&#xff09;系统中的一个概念。LVM是一种用于磁盘管理…

C++ :友元类

友元类的概念和使用 (1)将类A声明为B中的friend class后&#xff0c;则A中所有成员函数都成为类B的友元函数了 (2)代码实战&#xff1a;友元类的定义和使用友元类是单向的 (3)友元类是单向的&#xff0c;代码实战验证 互为友元类 (1)2个类可以互为友元类&#xff0c;代码实战…

Intel和AMD用户再等等!微软确认Win11 24H2年底前登陆

微软近日确认&#xff0c;Windows 11 24H2版本将于2024年底前正式登陆使用英特尔和AMD处理器的PC。 根据微软介绍&#xff0c;Windows 11 24H2将作为传统功能更新&#xff0c;将在今年晚些时候提供给所有设备。 此前&#xff0c;微软已向搭载骁龙X Plus和X Elite系列处理器的Co…

VS2019安装MFC组件

VS2019支持的MFC版本是mfc140 ~ mfc142版本&#xff0c;它兼容VS2015、VS2017之前的老版本程序。 一、MFC的历史版本 MFC的历史版本如下&#xff1a; IDE发布时间工具集版本MSC_VERMSVCMFC版本dllVisual C6.01998V601200MSVC6.06.0mfc42.dll、mfcce400.dllVisual Studio 2002…

Linux的热插拔UDEV机制和守护进程

目录 一、Linux的热插拔UDEV机制 二、守护进程 2.1 守护进程概念和基本特点&#xff1a; 2.2 显示进程信息&#xff1a; 2.3 守护进程和后台进程的区别&#xff1a; 2.4 创建守护进程的步骤和守护进程的特征&#xff1a; 2.4.1 创建守护进程的步骤&#xff1a; 2.4.2 守…

前端不懂 Docker ?先用它换掉常规的 Vue 项目部署方式

本项目代码已开源&#xff0c;具体见&#xff1a; 前端工程&#xff1a;vue3-ts-blog-frontend 后端工程&#xff1a;express-blog-backend 数据库初始化脚本&#xff1a;关注公众号程序员白彬&#xff0c;回复关键字“博客数据库脚本”&#xff0c;即可获取。 为什么需要容器化…

如何在 Mac 上下载安装植物大战僵尸杂交版? 最新版本 2.2 详细安装运行教程问题详解

植物大战僵尸杂交版已经更新至2.2了&#xff0c;但作者只支持 Windows、手机等版本并没有支持 MAC 版本&#xff0c;最近搞到了一个最新的杂交 2.2 版本的可以在 Macbook 上安装运行的移植安装包&#xff0c;试了一下非常完美能够正常在 MAC 上安装运行&#xff0c;看图&#x…

Linux云计算 |【第一阶段】ENGINEER-DAY5

主要内容&#xff1a; SELinux、系统故障修复、HTTPD/FTP服务搭建、防火墙策略管理、服务管理 一、SELinux安全制度 SELinux&#xff08;Security-Enhanced Linux&#xff09;&#xff0c;美国NSA国家安全局主导开发&#xff0c;一套增强Linux系统安全的强制访问控制体系&…

大模型只是轮子,与其闭门重复造轮子,不如深耕场景应用

如何理解李彦宏说的“不要卷模型&#xff0c;要卷应用” 7月4日&#xff0c;2024世界人工智能大会暨人工智能全球治理高级别会议全体会议在上海世博中心举办。在产业发展主论坛上&#xff0c;百度创始人、董事长兼首席执行官李彦宏呼吁&#xff1a;“大家不要卷模型&#xff0…

JavaWeb JavaScript ① JS简介

目录 一、HTML&CSS&JavaScript的作用 二、前后端关联标签——表单标签 1.form标签 2.input标签 3.get/post提交的差异 4.表单项标签 5.布局相关标签 块元素——div 行内元素——span 三、CSS 1.CSS引入方式 方式1 行内式 方式2 内嵌式 方式3 外部样式表 2.CSS选择器 元…

第三届智能机械与人机交互技术学术会议(IHCIT 2024)

【北航主办丨本届SPIE独立出版丨已确认ISSN号】 第三届智能机械与人机交互技术学术会议&#xff08;IHCIT 2024&#xff09; 2024 3rd International Conference on Intelligent Mechanical and Human-Computer Interaction Technology 2024年7月27日----中国杭州&#xff0…

Artix7系列FPGA实现SDI视频编解码,基于GTP高速接口,提供3套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐本博已有的 SDI 编解码方案本方案在Xilinx--Kintex系列FPGA上的应用本方案在Xilinx--Zynq系列FPGA上的应用 3、详细设计方案设计原理框图SDI 输入设备Gv8601a 均衡器GTP 高速接口-->解串与串化SMPTE SD/HD/3G SDI IP核BT1120转…

Python+Flask+MySQL/Sqlite的个人博客系统(前台+后端管理)【附源码,运行简单】

PythonFlaskMySQL/Sqlite的个人博客系统&#xff08;前台后端管理&#xff09;【附源码&#xff0c;运行简单】 总览 1、《个人博客系统》1.1 方案设计说明书设计目标工具列表 2、详细设计2.1 管理员登录2.2 程序主页面2.3 笔记新增界面2.4 文章新增界面2.5 文章/笔记管理界面2…