网站托管服务合同范本,找公司做网站注意事项,慈溪市住房和城乡建设局网站,学做网站和推广要多久C手撕AVL树 1、AVL树的概念2、AVL树的结构3、AVL树的插入3.1、大概过程3.2、更新平衡因子3.3、更新平衡因子代码3.4、左单旋3.5、右单旋3.6、右左双旋3.7、左右双旋 4、AVL树的删除5、AVL树的查找6、AVL树的平衡检测7、AVL树的其他函数完整代码 1、AVL树的概念
二叉搜索树虽可… C手撕AVL树 1、AVL树的概念2、AVL树的结构3、AVL树的插入3.1、大概过程3.2、更新平衡因子3.3、更新平衡因子代码3.4、左单旋3.5、右单旋3.6、右左双旋3.7、左右双旋 4、AVL树的删除5、AVL树的查找6、AVL树的平衡检测7、AVL树的其他函数完整代码 1、AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
AVL树实现这里我们引入一个平衡因子(balance factor)的概念每个结点都有一个平衡因子任何结点的平衡因子等于右子树的高度减去左子树的高度也就是说任何结点的平衡因子等于0/1/-1AVL树并不是必须要平衡因子但是有了平衡因子可以更方便我们去进⾏观察和控制树是否平衡就像一个风向标一样。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树 1、它的左右子树都是AVL树。 2、左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)。
平衡因子的计算我们统一用右边高度减去左边高度后面的实现也是如此。当然也可以反过来。 思考一下为什么AVL树是高度平衡搜索二叉树要求高度差不超过1而不是高度差是0呢0不是更好的平衡吗画画图分析我们发现不是不想这样设计而是有些情况是做不到高度差是0的。比如一棵树是2个结点4个结点等情况下高度差最好就是1无法作为高度差是0。而如果高度差是2/3/4…呢也是不行的因为这样在插入删除时的旋转调整将会非常麻烦。
下面对AVL树的效率进行分析 2、AVL树的结构
节点的结构是三叉链需要存储父节点的指针还需要存储bf平衡因子变量。存储父节点的指针是为了在更新平衡因子的时候可以快速找到父节点。 然后我们这里就直接实现key/value模型了所以需要两个模板参数分别用K、V来表示通过pair存储。
templateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:private:Node* _root nullptr;
};3、AVL树的插入
3.1、大概过程
这里的插入代码和我们之前写的二叉搜索树是类似的只不过由于插入之后平衡因子可能发生变化例如变成2/-2那么就需要调整平衡并更新平衡因子所以比二叉搜索树多了一步更新平衡因子的过程。
bool Insert(const pairK, V kv)
{if (_root nullptr){_root new Node(kv);return false;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_parent parent;// 更新平衡因子// ...return true;
}3.2、更新平衡因子
更新规则 1、新增节点在父节点的左侧父节点的平衡因子--。 2、新增节点在父节点的右侧父节点的平衡因子。 3、更新后父节点的平衡因子0说明父节点所在的子树高度没有发生变化不会影响祖先不用再沿着到根节点的路径往上更新更新结束。 4、更新后父节点的平衡因子1/-1说明父节点所在的子树高度发生了变化会影响祖先需要沿着到根节点的路径往上更新。 5、更新后父节点的平衡因子2/-2说明父节点所在的子树高度变化并且不平衡需要对父节点所在的子树旋转并更新平衡因子。由于旋转后父节点所在子树高度并没有增加所以不需要再向上更新更新结束。 6、若更新到根节点则停止。 3.3、更新平衡因子代码
while (parent)
{if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}
}正常情况下节点的平衡因子要么是0±1±2不会是其他值但是说不准我们写的代码有bug所以对于其他值我们直接assert终止程序。 3.4、左单旋 代码如下
void RotateL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;parent-_right curleft;if (curleft) curleft-_parent parent;cur-_left parent;parent-_parent cur;if (_root parent){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;
}3.5、右单旋 代码如下
void RotateR(Node* parent)
{Node* cur parent-_left;Node* curright cur-_right;Node* ppnode parent-_parent;parent-_left curright;if (curright)curright-_parent parent;cur-_right parent;parent-_parent cur;if (_root parent){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;
}3.6、右左双旋 代码如下
void RotateRL(Node* parent)
{Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf; RotateR(cur);RotateL(parent);if (bf 0){curleft-_bf 0;parent-_bf 0;cur-_bf 0;}else if (bf -1){curleft-_bf 0;parent-_bf 0;cur-_bf 1;}else if (bf 1){curleft-_bf 0;parent-_bf -1;cur-_bf 0;}else{assert(false);}
}这里bf0这种情况不需要写包括bf1和bf-1这两种情况中平衡因子0的也不需要赋值只需要写出平衡因子不为0的赋值因为在我们写的左旋和右旋函数中已经将平衡因子修改为0了。 这里我们三种情况分别写出来是为了对应上图的分析写出来更加清晰、好理解。 3.7、左右双旋 代码如下
void RotateLR(Node* parent)
{Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(cur);RotateR(parent);if (bf 0){curright-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf -1){curright-_bf 0;cur-_bf 0;parent-_bf 1;}else if (bf 1){curright-_bf 0;cur-_bf -1;parent-_bf 0;}else{assert(false);}
}4、AVL树的删除 代码如下
bool Erase(const K key) {Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first key){parent cur;cur cur-_right;}else if (cur-_kv.first key){parent cur;cur cur-_left;}else{if (cur-_left nullptr) // 左边为空{if (_root cur){_root cur-_right;if (_root)_root-_parent nullptr;delete cur;return true;}}else if (cur-_right nullptr) // 右边为空{if (_root cur){_root cur-_left;if (_root)_root-_parent nullptr;delete cur;return true;}}else // 左右都不为空寻找替换节点{parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}cur-_kv.first leftMax-_kv.first;cur-_kv.second leftMax-_kv.second;cur leftMax;}break;}}// 找不到直接返回if (cur nullptr) return false;Node* del cur;Node* delParent parent;while (parent){if (parent-_left cur){ parent-_bf;}else{parent-_bf--;}if (parent-_bf 0){cur parent;parent parent-_parent;}else if (parent-_bf 1 || parent-_bf -1){break;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf -2){if (parent-_left-_bf 0){cur parent-_left;RotateR(parent);cur-_bf 1;parent-_bf -1;break;}else if (parent-_left-_bf -1){cur parent-_left;RotateR(parent);}else // parent-_left-_bf 1;{cur parent-_left-_right;RotateLR(parent);}}else // parent-_bf 2{if (parent-_right-_bf 0){cur parent-_right;RotateL(parent);cur-_bf -1;parent-_bf 1;break;}else if (parent-_right-_bf 1){cur parent-_right;RotateL(parent);}else{cur parent-_right-_left;RotateRL(parent);}}parent cur-_parent;}else{assert(false);}}cur del, parent delParent;if (cur-_left nullptr){if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;if (cur-_right)cur-_right-_parent parent;}else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;if (cur-_left)cur-_left-_parent parent;}delete cur;return true;
}5、AVL树的查找
Node* Find(const K key)
{Node* cur _root;while (cur){if (cur-_kv.first key)cur cur-_right;else if (cur-_kv.first key)cur cur-_left;elsereturn cur;}return nullptr;
}6、AVL树的平衡检测
bool IsBalance(){return IsBalance(_root);}int Height()
{return Height(_root);
}bool IsBalance(Node* root)
{if (root nullptr) return true;int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(leftHeight - rightHeight) 2 IsBalance(root-_left) IsBalance(root-_right);
}int Height(Node* root)
{if (root nullptr) return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}通过IsBalance函数来判断树中的平衡因子计算是否正确如果存在异常就会打印输出信息。 同时为了计算平衡因子需要求出左右高度然后相减所以还需要实现Height函数获取树的高度。 7、AVL树的其他函数
这里实现构造函数、拷贝构造函数、赋值运算符重载、析构函数、中序遍历函数。基本上类似前面的二叉搜索树。
AVLTree():_root(nullptr)
{}AVLTree(const AVLTreeK, V t):_root(nullptr)
{_root Copy(t._root, nullptr);
}AVLTreeK, V operator(AVLTreeK, V t)
{swap(_root, t._root);return *this;
}~AVLTree()
{Destroy(_root);
}void InOrder()
{InOrder(_root);cout endl;
}Node* Copy(Node* root, Node* parent)
{if (root nullptr) return nullptr;Node* copy new Node(root-_kv);copy-_bf root-_bf;copy-_parent parent;copy-_left Copy(root-_left, copy);copy-_right Copy(root-_right, copy);return copy;
}void Destroy(Node* root)
{if (root nullptr) return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;
}void InOrder(Node* root)
{if (root nullptr) return;InOrder(root-_left);cout root-_kv.first ;InOrder(root-_right);
}完整代码
#pragma oncetemplateclass K, class V
struct AVLTreeNode
{AVLTreeNodeK, V* _left;AVLTreeNodeK, V* _right;AVLTreeNodeK, V* _parent;pairK, V _kv;int _bf;AVLTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}
};templateclass K, class V
class AVLTree
{typedef AVLTreeNodeK, V Node;
public:AVLTree():_root(nullptr){}AVLTree(const AVLTreeK, V t):_root(nullptr){_root Copy(t._root, nullptr);}AVLTreeK, V operator(AVLTreeK, V t){swap(_root, t._root);return *this;}~AVLTree(){Destroy(_root);}bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return false;}Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);if (parent-_kv.first kv.first)parent-_right cur;elseparent-_left cur;cur-_parent parent;while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf -1){cur parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}break;}else{assert(false);}}return true;}bool Erase(const K key) {Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first key){parent cur;cur cur-_right;}else if (cur-_kv.first key){parent cur;cur cur-_left;}else{if (cur-_left nullptr) // 左边为空{if (_root cur){_root cur-_right;if (_root)_root-_parent nullptr;delete cur;return true;}}else if (cur-_right nullptr) // 右边为空{if (_root cur){_root cur-_left;if (_root)_root-_parent nullptr;delete cur;return true;}}else // 左右都不为空寻找替换节点{parent cur;Node* leftMax cur-_left;while (leftMax-_right){parent leftMax;leftMax leftMax-_right;}cur-_kv.first leftMax-_kv.first;cur-_kv.second leftMax-_kv.second;cur leftMax;}break;}}// 找不到直接返回if (cur nullptr) return false;Node* del cur;Node* delParent parent;while (parent){if (parent-_left cur){ parent-_bf;}else{parent-_bf--;}if (parent-_bf 0){cur parent;parent parent-_parent;}else if (parent-_bf 1 || parent-_bf -1){break;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf -2){if (parent-_left-_bf 0){cur parent-_left;RotateR(parent);cur-_bf 1;parent-_bf -1;break;}else if (parent-_left-_bf -1){cur parent-_left;RotateR(parent);}else // parent-_left-_bf 1;{cur parent-_left-_right;RotateLR(parent);}}else // parent-_bf 2{if (parent-_right-_bf 0){cur parent-_right;RotateL(parent);cur-_bf -1;parent-_bf 1;break;}else if (parent-_right-_bf 1){cur parent-_right;RotateL(parent);}else{cur parent-_right-_left;RotateRL(parent);}}parent cur-_parent;}else{assert(false);}}cur del, parent delParent;if (cur-_left nullptr){if (parent-_left cur)parent-_left cur-_right;elseparent-_right cur-_right;if (cur-_right)cur-_right-_parent parent;}else{if (parent-_left cur)parent-_left cur-_left;elseparent-_right cur-_left;if (cur-_left)cur-_left-_parent parent;}delete cur;return true;}Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key)cur cur-_right;else if (cur-_kv.first key)cur cur-_left;elsereturn cur;}return nullptr;}bool IsBalance(){return IsBalance(_root);}int Height(){return Height(_root);}void InOrder(){InOrder(_root);cout endl;}private:Node* Copy(Node* root, Node* parent){if (root nullptr) return nullptr;Node* copy new Node(root-_kv);copy-_bf root-_bf;copy-_parent parent;copy-_left Copy(root-_left, copy);copy-_right Copy(root-_right, copy);return copy;}void Destroy(Node* root){if (root nullptr) return;Destroy(root-_left);Destroy(root-_right);delete root;root nullptr;}void InOrder(Node* root){if (root nullptr) return;InOrder(root-_left);cout root-_kv.first ;InOrder(root-_right);}bool IsBalance(Node* root){if (root nullptr) return true;int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (rightHeight - leftHeight ! root-_bf){cout 平衡因子异常: root-_kv.first - root-_bf endl;return false;}return abs(leftHeight - rightHeight) 2 IsBalance(root-_left) IsBalance(root-_right);}int Height(Node* root){if (root nullptr) return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;parent-_right curleft;if (curleft) curleft-_parent parent;cur-_left parent;parent-_parent cur;if (_root parent){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;Node* ppnode parent-_parent;parent-_left curright;if (curright)curright-_parent parent;cur-_right parent;parent-_parent cur;if (_root parent){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}parent-_bf cur-_bf 0;}void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;int bf curleft-_bf; RotateR(cur);RotateL(parent);if (bf 0){curleft-_bf 0;parent-_bf 0;cur-_bf 0;}else if (bf -1){curleft-_bf 0;parent-_bf 0;cur-_bf 1;}else if (bf 1){curleft-_bf 0;parent-_bf -1;cur-_bf 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;int bf curright-_bf;RotateL(cur);RotateR(parent);if (bf 0){curright-_bf 0;cur-_bf 0;parent-_bf 0;}else if (bf -1){curright-_bf 0;cur-_bf 0;parent-_bf 1;}else if (bf 1){curright-_bf 0;cur-_bf -1;parent-_bf 0;}else{assert(false);}}
private:Node* _root nullptr;
};
