C++:AVL树的实现
AVL的代码
Gitee_AVL的实现代码
一、定义与性质
-
定义:AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
-
性质:
- 它的左右子树都是AVL树。
- 节点的左子树不为空,平衡因子-1,右子树不为空,平衡因子+1。
- 任意节点的左子树和右子树的高度差(平衡因子)的绝对值不超过1(-1、0或1)。
- 当该树的平衡因子等于二或负二的时候要进行调整。
- 增删查改的效率为O(logN)。
当树里有平衡因子等于2或-2时,就需要进行调整了。
二、AVL树的节点结构
需要一个链接左右子树的指针和父节点的指针,一个变量_data来存储数据,一个平衡因子来判断是否要进行调整AVL树。
template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data = T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;AVLTreeNode<T>* _pRight;AVLTreeNode<T>* _pParent;T _data;int _bf; // 节点的平衡因子
};
三、操作与平衡
-
基本操作:AVL树支持常见的二叉搜索树操作,如插入、删除和搜索。在执行这些操作时,AVL树会根据节点的平衡因子进行自平衡调整。
若不熟悉二叉搜索树可以看这篇文章->数据结构:详解搜索二叉树-CSDN博客
-
平衡方法:AVL树通过四种旋转操作来维持平衡:
-
右旋转(Right Rotation):当某个节点的左子树高度较高时,通过右旋转来降低左子树的高度。
- 左旋转(Left Rotation):当某个节点的右子树高度较高时,通过左旋转来降低右子树的高度。
- 左右旋转(Left-Right Rotation):当某个节点的左子树的右子树高度较高时,通过先对左子树进行左旋转,再对根节点进行右旋转来调整树的平衡。
- 右左旋转(Right-Left Rotation):当某个节点的右子树的左子树高度较高时,通过先对右子树进行右旋转,再对根节点进行左旋转来调整树的平衡。
1、右旋转
出现下面这种情况需要用左旋转来调整AVL树,确保节点的平衡因子不为2或-2。
这里我们需要将 p 节点的左子树链接 s 节点的右子树,s 节点的右子树链接 p 节点。其中还需要注意父节点的链接。我们可以发现 p 节点的平衡因子变为零,s 节点也变为零。调整完的结果应该像下面这样。
void RotateR(Node* parent)
{Node* pParent = parent->_pParent;Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;subL->_pParent = pParent;if (pParent){if (pParent->_pLeft == parent)pParent->_pLeft = subL;elsepParent->_pRight = subL;}else{_pRoot = subL;subL->_pParent = pParent;}subL->_pRight = parent;parent->_pParent = subL;parent->_pLeft = subLR;if (subLR){subLR->_pParent = parent;}subL->_bf = 0;parent->_bf = 0;
}
2、左旋转
基本同理,转为下面这样
void RotateL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;parent->_pRight = subRL;if (subRL)subRL->_pParent = parent;Node* parentParent = parent->_pParent;subR->_pLeft = parent;parent->_pParent = subR;if (parentParent == nullptr){_pRoot = subR;subR->_pParent = nullptr;} else{if (parent == parentParent->_pLeft){parentParent->_pLeft = subR;} else{parentParent->_pRight = subR;} subR->_pParent = parentParent;} parent->_bf = subR->_bf = 0;
}
3、左右旋转
先对 sl 节点进行一次左旋转
再对 p 节点进行一次右旋转
void RotateLR(Node* parent)
{Node* subL = parent->_pLeft;Node* subLR = subL->_pRight;int bf = subLR->_bf;RotateL(parent->_pLeft);RotateR(parent);if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;} else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;} else if (bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;} else{assert(false);}
}
4、右左旋转
右左旋转的图形就与左右旋转的图形类似。这里偷个懒就不画了
void RotateRL(Node* parent)
{Node* subR = parent->_pRight;Node* subRL = subR->_pLeft;int bf = subRL->_bf;RotateR(parent->_pRight);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;} else{assert(false);}
}
四、时间复杂度
在AVL树中,查找、插入和删除操作的时间复杂度都是O(log n),其中n是树中节点的数量。这是因为AVL树通过自平衡机制保持了树的高度在O(log n)范围内,从而确保了这些操作的高效性。