做的比较好的车载嗨曲网站,零基础网络工程师培训,宁德市住房和城乡建设局新网站,官网摩尔庄园文章目录1. 二叉搜索树1.1 二叉搜索树概念1.2 二叉搜索树操作1.3 二叉搜索树的实现1.4 二叉搜索树的应用1.5 二叉搜索树的性能分析2. AVL 树2.1 AVL树的概念2.2 AVL树节点的定义2.3 AVL树的插入2.4 AVL树的旋转2.5 AVL树的验证2.7 AVL树的性能3. 具体代码实现区3.1 二叉搜索树的…
文章目录1. 二叉搜索树1.1 二叉搜索树概念1.2 二叉搜索树操作1.3 二叉搜索树的实现1.4 二叉搜索树的应用1.5 二叉搜索树的性能分析2. AVL 树2.1 AVL树的概念2.2 AVL树节点的定义2.3 AVL树的插入2.4 AVL树的旋转2.5 AVL树的验证2.7 AVL树的性能3. 具体代码实现区3.1 二叉搜索树的代码实现3.2 AVL树的具体代码实现1. 二叉搜索树
1.1 二叉搜索树概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
若它的左子树不为空则左子树上所有节点的值都小于根节点的值若它的右子树不为空则右子树上所有节点的值都大于根节点的值它的左右子树也分别为二叉搜索树 1.2 二叉搜索树操作 int a[] {8, 3, 1, 10, 6, 4, 7, 14, 13};二叉搜索树的查找 a、从根开始比较查找比根大则往右边走查找比根小则往左边走查找。 b、最多查找高度次走到到空还没找到这个值不存在。 二叉搜索树的插入 插入的具体过程如下 a. 树为空则直接新增节点赋值给root指针 b. 树不空按二叉搜索树性质查找插入位置插入新节点 二叉搜索树的删除 首先查找元素是否在二叉搜索树中如果不存在则返回, 否则要删除的结点可能分下面四种情况 a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点
看起来有待删除节点有4中情况实际情况a可以与情况b或者c合并起来因此真正的删除过程 如下 情况b删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除 情况c删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除 情况d在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题–替换法删除
1.3 二叉搜索树的实现
跳转到下面—》代码区 1.4 二叉搜索树的应用 K模型K模型即只有key作为关键码结构中只需要存储Key即可关键码即为需要搜索到的值。 比如给一个单词word判断该单词是否拼写正确具体方式如下 以词库中所有单词集合中的每个单词作为key构建一棵二叉搜索树在二叉搜索树中检索该单词是否存在存在则拼写正确不存在则拼写错误。 KV模型每一个关键码key都有与之对应的值Value即Key, Value的键值对。该种方式在现实生活中非常常见(C库中就有一个pair,就是KV模型下面将会学习) 比如英汉词典就是英文与中文的对应关系通过英文可以快速找到与其对应的中文英文单词与其对应的中文word, chinese就构成一种键值对再比如统计单词次数统计成功后给定单词就可快速找到其出现的次数单词与其出现次数就是word, count就构成一种键值对
// 改造二叉搜索树为KV结构
templateclass K, class V
struct BSTNode
{BSTNode(const K key K(), const V value V()): _pLeft(nullptr), _pRight(nullptr), _key(key), _Value(value){}BSTNodeT* _pLeft;BSTNodeT* _pRight;K _key;V _value
};
templateclass K, class V
class BSTree
{typedef BSTNodeK, V Node;typedef Node* PNode;
public:BSTree() : _pRoot(nullptr){}PNode Find(const K key);bool Insert(const K key, const V value)bool Erase(const K key)
private:PNode _pRoot;
}1.5 二叉搜索树的性能分析
插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。
但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树(或者接近完全二叉树)其平均比较次数为log2Nlog_2 Nlog2N**最差情况下二叉搜索树退化为单支树(或者类似单支)其平均比较次数为N2\frac{N}{2}2N ** 问题如果退化成单支树二叉搜索树的性能就失去了。那能否进行改进不论按照什么次序插入关键码二叉搜索树的性能都能达到最优 那么AVL树和红黑树就可以上场了。 2. AVL 树
2.1 AVL树的概念
二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。
一棵AVL树或者是空树或者是具有以下性质的二叉搜索树
它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1) 如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在O(log2n)O(log_2 n)O(log2n)搜索时间复杂度O(log2nlog_2 nlog2n)。 2.2 AVL树节点的定义
AVL树节点的定义
采用的是三叉链结构
templateclass T
struct AVLTreeNode
{T data;AVLTreeNodeT*_left;// 该节点的左孩子AVLTreeNodeT* _right;// 该节点的右孩子AVLTreeNodeT* _parent;// 该节点的双亲int _bf;// 该节点的平衡因子----可以用右子树的高度-左子树的高度AVLTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
2.3 AVL树的插入
AVL树就是在二叉搜索树的基础上引入了平衡因子因此AVL树也可以看成是二叉搜索树。
那么AVL树的插入过程可以分为两步 按照二叉搜索树的方式插入新节点 调整节点的平衡因子
具体代码实现在看下面的代码
跳转到下面–》代码区 2.4 AVL树的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点可能造成不平衡此时必须调整树的结构使之平衡化。根据节点插入位置的不同AVL树的旋转分为四种
新节点插入较高左子树的左侧—左左右单旋 新节点插入较高右子树的右侧—右右左单旋 新节点插入较高左子树的右侧—左右先左单旋再右单旋 将双旋变成单旋后再旋转即先对30进行左单旋然后再对90进行右单旋旋转完成后再考虑平衡因子的更新。
一个简单的例子 新节点插入较高右子树的左侧—右左先右单旋再左单旋 参考右左双旋。
一个简单的例子 总结
假如以pParent为根的子树不平衡即pParent的平衡因子为2或者-2分以下情况考虑 pParent的平衡因子为2说明pParent的右子树高设pParent的右子树的根为pSubR 当pSubR的平衡因子为1时执行左单旋当pSubR的平衡因子为-1时执行右左双旋 pParent的平衡因子为-2说明pParent的左子树高设pParent的左子树的根为pSubL 当pSubL的平衡因子为-1是执行右单旋当pSubL的平衡因子为1时执行左右双旋
旋转完成后原pParent为根的子树个高度降低已经平衡不需要再向上更新。 2.5 AVL树的验证
AVL树的代码这么复杂那我们该如何确认我们写的代码是否有问题呢
这时候我们可以写一个程序进行验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确
bool IsBalanceTree(Node* root)
{if (root nullptr)//空树叶是AVL树return true;// 计算root节点的平衡因子即root左右子树的高度差int leftHeight GetTreeHeight(root-_left);int rightHeight GetTreeHeight(root-_right);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if (diff ! root-_bf || diff1 || diff-1){std::cout root-_val -该节点平衡因子错误! root-_bf: root-_bf 实际_bf diff std::endl;return false;}// root的左和右如果都是AVL树则该树一定是AVL树return IsBalanceTree(root-_left) IsBalanceTree(root-_right);
}验证用例 可以结合上述代码按照以下的数据次序自己动手画AVL树的创建过程验证代码是否有漏洞。
常规场景1 {16, 3, 7, 11, 9, 26, 18, 14, 15}特殊场景2 {4, 2, 6, 1, 3, 5, 15, 7, 16, 14} 2.7 AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即log2(N)log_2 (N)log2(N)。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。 3. 具体代码实现区
3.1 二叉搜索树的代码实现 #pragma once
#include iostream
#include cassert
using namespace std;namespace hdm
{/*Binary Search Tree---二叉搜索树或二叉排序树*/templateclass Tstruct BSTreeNode{T _val;BSTreeNodeT* _left;//左孩子BSTreeNodeT* _right;//右孩子BSTreeNode(const T val T()):_val(val), _left(nullptr), _right(nullptr){}};templateclass Tclass BSTree{public:typedef BSTreeNodeT Node;Node* find(const T x){Node* cur _root;while (cur){if (cur-_val x)//比cur小往左子树找{cur cur-_left;}else if (cur-_val x)//比cur大往右子树找{cur cur-_right;}else//相等即返回{return cur;}}return nullptr;}bool insert(const T x){if (_root nullptr)//_rootnullptr说明为空树{_root new Node(x);return true;}Node* cur _root;Node* parent cur;//记录父节点用于连接新节点while (cur){//cur往子树走的同时记录子树的父节点if (cur-_val x)//比cur小往左子树找{parent cur;cur cur-_left;}else if (cur-_val x)//比cur大往右子树找{parent cur;cur cur-_right;}else//进入else说明cur-_valx,表示已经存在该节点不需要插入返回false表示插入失败{return false;}}//程序走到这说明curnullptr最后x就应该要插入在parent的下面至于是插入左边还是右边//具体看x与parent-_val 之间值的关系if (parent-_val x)//如果x的值小于parent就往左边插入{parent-_left new Node(x);}else//如果x的值大于parent就往右边插入{parent-_right new Node(x);}return true;}bool erase(const T x){if (!find(x))//如果该树不存在这节点就返回false表示删除失败return false;Node* cur _root;Node* parent cur;while (cur){//cur往子树走的同时记录子树的父节点if (cur-_val x)//比cur小往左子树找{parent cur;cur cur-_left;}else if (cur-_val x)//比cur大往右子树找{parent cur;cur cur-_right;}else//已找到--分情况删除{//1.左孩子不存在//2.右孩子不存在//3.左右孩子都存在--替换删if (cur-_left nullptr)//情况1左孩子不存在{if (cur _root)//如果_root刚好是要删除的节点的情况{_root cur-_right;}//比较parent和cur的值要分清cur的parent的那一个孩子if (parent-_left cur){parent-_left cur-_right;}else{parent-_right cur-_right;}delete cur;cur nullptr;}else if (cur-_right nullptr)//情况2.右孩子不存在{if (cur _root)//跟上面一样_root刚好是要删除的节点的情况{_root cur-_left;}//同样要判断cur是parent的哪一边if (parent-_left cur){parent-_left cur-_left;}else{parent-_right cur-_left;}delete cur;cur nullptr;}else if (cur-_left!nullptr cur-_right!nullptr)//情况3.左右孩子都存在--替换删{//这里找的是右子树的最小节点(就是右子树的最左节点)Node* min_right cur-_right;Node* min_right_parent cur;//记录右子树最小节点的父节点用于后续连接while (min_right-_left){min_right_parent min_right;min_right min_right-_left;}swap(cur-_val, min_right-_val);//可以交换也可以覆盖原来要删除的节点//cur-_val min_right-_val;//这个是覆盖//要删除min_right把它的右孩子要连上if (min_right_parent-_left min_right){min_right_parent-_left min_right-_right;}else{min_right_parent-_right min_right-_right;}delete min_right;min_right nullptr;break;}else{//如果进入了else说明都没有出现上面的情况就是程序哪里写错了直接断言报错assert(false);}}}return true;}void InorderTree(){_InorderTree(_root);cout endl;}Node* findNonR(const T x)//查找的递归版本{return findNonR(_root, x);}bool insertNonR(const T x)//插入的递归版本{return insertNonR(_root, x);}bool eraseNonR(const T x)//删除的递归版本{return eraseNonR(_root, x);}private:bool eraseNonR(Node* root, const T x){if (root nullptr)return false;if (root-_val x){return eraseNonR(root-_left, x);}else if (root-_val x){return eraseNonR(root-_right, x);}else{//1.左孩子不存在//2.右孩子不存在//3.左右孩子都存在Node* del root;if (root-_left nullptr){root root-_right;}else if (root-_right nullptr){root root-_left;}else if (root-_left root-_right){Node* right_min root-_right;Node* parent_min root;while (right_min-_left){parent_min right_min;right_min right_min-_left;}swap(root-_val, right_min-_val);return eraseNonR(root-_right, x);//然后再让root-_right去递归删除交换后的x}else{//未知错误assert(false);}delete del;del nullptr;return true;}}bool insertNonR(Node* root,const T x)//插入的递归版本{if (root nullptr){root new Node(x);return true;}if (root-_val x){return insertNonR(root-_left, x);}else if (root-_val x){return insertNonR(root-_right, x);}else{return false;}}Node* findNonR(Node* root,const T x)//查找的递归版本{if (root nullptr)return root;if (root-_val x)return findNonR(root-_left, x);else if (root-_val x)return findNonR(root-_right, x);elsereturn root;}void _InorderTree(Node* root){if (root nullptr)return;_InorderTree(root-_left);cout root-_val ;_InorderTree(root-_right);}private:Node* _root nullptr;};
}3.2 AVL树的具体代码实现 #pragma once
#include iostream
namespace hdm
{templateclass Tstruct AVLTreeNode{T _val;AVLTreeNodeT*_left;// 该节点的左孩子AVLTreeNodeT* _right;// 该节点的右孩子AVLTreeNodeT* _parent;// 该节点的双亲int _bf;// 该节点的平衡因子AVLTreeNode(const T data):_val(data), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};templateclass Tclass AVLTree{public:typedef AVLTreeNodeT Node;bool insert(const T x){if (_root nullptr){_root new Node(x);return true;}Node* cur _root;Node* parent cur;//记录父节点用于连接新节点while (cur){//cur往子树走的同时记录子树的父节点if (cur-_val x)//比cur小往左子树找{parent cur;cur cur-_left;}else if (cur-_val x)//比cur大往右子树找{parent cur;cur cur-_right;}else//进入else说明cur-_valx,表示已经存在该节点不需要插入返回false表示插入失败{return false;}}//程序走到这说明curnullptr最后x就应该要插入在parent的下面至于是插入左边还是右边//具体看x与parent-_val 之间值的关系cur new Node(x);if (parent-_val x)//如果x的值小于parent就往左边插入{parent-_left cur;}else//如果x的值大于parent就往右边插入{parent-_right cur;}//注意这里是三叉链结构要把父子关系连上cur-_parent parent;//更新平衡因子while (parent)//parent为空就结束也就是更新到根的位置就停止{//新增在右,parent-_bf//新增在左,parent-_bf--if (parent-_left cur){parent-_bf--;}else{parent-_bf;}/*判断是否更新的依据子树的高度是否变化1.parent-_bf0,说明parent-_bf是1或者-1,也就是说明之前是一边高一个边低这次插入填上矮的那边parent所在子树高度不变现在插入的节点刚好让它平衡了就不需要向上更新了2.parent-_bf1 或 parent-_bf-1,说明之前parent-_bf0,插入前是平衡的插入之后导致一边高一边低这个时候就要继续向上更新3.parent-_bf2 或 parent-_bf-2 ,说明之前parent-_bf1 或 -1的现在插入的节点导致严重不平衡违反了规则就要进行就地处理--旋转*///旋转//1.让这棵子树左右高度不超过1//2.旋转过程中进行保持它是搜索树//3.更新调整孩子节点的高度平衡因子//3.让这颗子树的高度跟插入前保持一致if (parent-_bf 0){break;}else if (parent-_bf -1 || parent-_bf 1){cur parent;parent cur-_parent;}else if (parent-_bf 2 || parent-_bf -2){//旋转if (parent-_bf -2 cur-_bf -1){//右单旋RotateR(parent);}else if (parent-_bf 2 cur-_bf 1){//左单旋RotateL(parent);}else if (parent-_bf -2 cur-_bf 1){//左右旋RotateLR(parent);}else if (parent-_bf 2 cur-_bf -1){//右左旋RotateRL(parent);}else{//未知错误(比如程序写错)assert(false);}break;//旋转完了之后要break}else{//未知错误assert(false);}}return true;}Node* find(const T x){Node* cur _root;while (cur){if (cur-_val x)//比cur小往左子树找{cur cur-_left;}else if (cur-_val x)//比cur大往右子树找{cur cur-_right;}else//相等即返回{return cur;}}return nullptr;}void InorderTree(){InorderTree(_root);std::cout std::endl;}bool IsBalanceTree()//检验平衡二叉树{return IsBalanceTree(_root);}private:bool IsBalanceTree(Node* root){if (root nullptr)//空树叶是AVL树return true;// 计算root节点的平衡因子即root左右子树的高度差int leftHeight GetTreeHeight(root-_left);int rightHeight GetTreeHeight(root-_right);int diff rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等或者// pRoot平衡因子的绝对值超过1则一定不是AVL树if (diff ! root-_bf || diff1 || diff-1){std::cout root-_val -该节点平衡因子错误! root-_bf: root-_bf 实际_bf diff std::endl;return false;}// root的左和右如果都是AVL树则该树一定是AVL树return IsBalanceTree(root-_left) IsBalanceTree(root-_right);}int GetTreeHeight(Node* root){if (root nullptr)return 0;int left GetTreeHeight(root-_left);int right GetTreeHeight(root-_right);return left right ? left 1 : right 1;}void InorderTree(Node* root){if (root nullptr)return;InorderTree(root-_left);std::cout root-_val ;InorderTree(root-_right);}void RotateR(Node* parent)//右单旋{/*最要注意的点就是这个是三叉链结构要注意处理parent节点*/Node* subL parent-_left;Node* subLR subL-_right;//左子树的右子树Node* pparent parent-_parent;if (subLR)//subLR 不为空就要修改它的parentsubLR-_parent parent;parent-_left subLR;subL-_right parent;parent-_parent subL;if (pparent nullptr)//pparent为空就表示parent为_root就要修改整棵树的根{_root subL;_root-_parent nullptr;}else//不是根节点就要判断是位于pparent的那一边{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}//更新平衡因子subL-_bf parent-_bf 0;}void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;if (subRL)//subRL不为空就要连接它的parentsubRL-_parent parent;parent-_right subRL;subR-_left parent;parent-_parent subR;if (pparent nullptr)//pparent为空就表示parent为_root就要修改整棵树的根{_root subR;_root-_parent nullptr;}else//不是根节点就要判断是位于pparent的那一边{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}//更新平衡因子subR-_bf parent-_bf 0;}void RotateLR(Node* parent)//左右旋{Node* subL parent-_left;Node* subLR subL-_right;int oldBf subLR-_bf;//记录旧的平衡因子,这样才知道是在哪插入的新节点//先左单旋,然后再右单旋RotateL(parent-_left);RotateR(parent);subLR-_bf 0;if (oldBf -1)//就是在原节点的左子树插入{parent-_bf 1;subL-_bf 0;}else if(oldBf 1)//右子树新增{subL-_bf -1;parent-_bf 0;}else if (oldBf 0)//自己就是新增的节点{subL-_bf parent-_bf 0;}else{//都不是上述情况只能是有些地方写错了assert(false);}}void RotateRL(Node* parent)//右左旋{Node* subR parent-_right;Node* subRL subR-_left;int oldBf subRL-_bf;//记录旧的平衡因子RotateR(parent-_right);RotateL(parent);//更新平衡因子subRL-_bf 0;if (oldBf -1){parent-_bf 0;subR-_bf 1;}else if (oldBf 1){parent-_bf -1;subR-_bf 0;}else if (oldBf 0){parent-_bf subR-_bf 0;}else{//未知错误assert(false);}}private:Node* _root nullptr;};void AVLTreeTest1(){int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 ,1,2,4,3,4,4,4,4,4};AVLTreeint avl;for (auto e: a){avl.insert(e);}avl.InorderTree();cout avl.IsBalanceTree() endl;}
}
