江苏省工程建设标准网站,济阳做网站多少钱,wordpress做联系页面,如何注册网站免费注册目录
一、二叉搜索树
1.什么是二叉搜索树
2.二叉搜索树的实现
#xff08;1#xff09;构建类
#xff08;2#xff09;查找函数
#xff08;3#xff09;插入函数
#xff08;4#xff09;删除函数
#xff08;5#xff09;补齐默认成员函数
#xff08;6… 目录
一、二叉搜索树
1.什么是二叉搜索树
2.二叉搜索树的实现
1构建类
2查找函数
3插入函数
4删除函数
5补齐默认成员函数
6中序遍历函数
二、AVL树
1.什么是AVL树
2.AVL树的简易实现
1构建类
2插入函数实现准备
3AVL树的检验 一、二叉搜索树
1.什么是二叉搜索树
二叉搜索树Binary Search Tree是一种特殊的二叉树它必须满足以下性质
若左子树不为空左子树中所有节点的键值都小于根节点的值。若右子树不为空右子树中所有节点的键值都大于根节点的值。左右子树也分别为二叉搜索树。空树也是搜索二叉树
简单地说就是这个二叉树的任意一棵子树它的左子树根节点值小于它的根节点值它的右子树根节点值大于它的根节点值这样的特性使得二叉搜索树的中序遍历结果是一个升序序列。这个特性使得二叉搜索树在搜索、插入和删除操作时具有高效性能同时后面的AVL树和红黑树等许多数据结构也是基于它而实现。
2.二叉搜索树的实现
1构建类
依旧换汤不换药在Binary Search Tree.h头文件中定义类在test.cpp中写测试代码。
构建好下面的两个类一个类是二叉树的节点类另一个是二叉搜索树的这个类在编写过程中注意包含需要的头文件。
#includeassert.h
namespace my_BST
{templateclass Kstruct BSTreeNode{K _key;struct BSTreeNode* _left;struct BSTreeNode* _right;BSTreeNode(const K x):_key(x), _left(nullptr), _right(nullptr){}};templateclass Kclass BSTree{typedef BSTreeNodeK node;public://成员函数private:node* _root;//搜索二叉树的根节点};
}
2查找函数
在一各二叉搜索树中查找数据很简单的给定一个确定的值先和该棵树的根进行比较如果这个值小于根节点保存的值那么就需要到它的左子树去寻找如果这个值大于根节点那么就需要到右子树去寻找。之后再在新的子树中进行比较直到找到该值或者找到空位置前者表示能找到后者就表示找不到了。
bool find(const K key)
{node* cur _root;while (cur){if (key cur-_key)//小于根左走{cur cur-_left;}else if (key cur-_key)//大于根右走{cur cur-_right;}else{return true;//相等返回真}}return false;//找到空位置肯定就不存在这个值
}
还有另一种递归写法
bool findR(const K key, node* root)
{if(root nullptr)return false; if(key root-_key)findR(root-_left);else if(key root-_key)findR(root-_right);elsereturn true;
}
但是如果我们直接将这个函数递归函数写到public的成员函数中我们会发现一个巨大的问题我们需要传递二叉树的_root指针而这个指针是内部封装的内容用户层看不到。那么我们就需要再使用一次封装将上面的函数定义为_findR函数在类公共成员函数中使用findR函数调用它即可。
templateclass K
class BSTree
{typedef BSTreeNodeK node;
public:bool findR(const K key){_findR(key, _root);}
private:bool _findR(const K key, node* root){if (root nullptr)return false;else if (key root-_key)return _findR(key, root-_left);else if (key root-_key)return _findR(key, root-_right);elsereturn true;}node* _root;
};
后面的我就不再将两个函数写在类中了。
3插入函数
插入和查找非常相似通过相同的查找策略这次我们需要找到空节点然后在空节点位置新建节点找到同样的元素就不再插入了。
bool insert(const K key)
{if (_root nullptr)//空树就直接插入{_root new node(key);return true;}node* parent nullptr;node* cur _root;while (cur){if (key cur-_key)//小于根左走{parent cur;cur cur-_left;}else if (key cur-_key)//大于根右走{parent cur;cur cur-_right;}else//找到了需要插入的值搜索二叉树的元素是不能重复的插入失败{return false;}}cur new node(key);if (key parent-_key)//key小于根做左节点{parent-_left cur;}else//大于根做右节点{parent-_right cur;}return true;
}
插入函数同样也可以写成递归的函数
bool insertR(const K key)
{return _insertR(key, _root);
}bool _insertR(const K key, node* root)
{if (root nullptr){root new node(key);return true;}else if (key root-_key)//小于根向左走{return _insertR(key, root-_left);}else if (key root-_key)//大于根向右走{return _insertR(key, root-_right);}else//找到相同的元素{return false;}
}
4删除函数
删除函数的实现比较复杂主要分为三种情况
要删除的节点只有右子节点或既没有左子节点也没有右子节点
如果是叶子节点或者只有右子节点的节点就可以先将该节点的父节点与它的右子节点进行链接使这个右节点成为父节点的右节点然后将该节点删除。同时被删除的也可能是根节点需要判断并特殊处理。
要删除的节点只有左子节点
如果节点只有左子节点可以将该节点的左子节点与其父节点进行链接使这个左节点成为父节点的右节点由于二叉搜索树的特性右子树的内容都会比根大所以右子树的左子树也可以做根的右子树然后将该节点删除。同时被删除的也可能是根节点需要判断并特殊处理。
要删除的节点有左、右子节点
此时需要寻找该节点右子树的最小值将这个最小节点的值覆盖该节点然后需要被被删除的节点就转化为了右子树的最左节点右子树一直向左走直到没有左节点就是最小节点此时满足情况一的删除条件此时就可以使用原先的代码了但此时不需要特殊处理了因为被删除的节点一定不是根节点。
bool Erase(const K key)
{//一共分为三种情况//要删除的节点只有右子节点或既没有左子节点也没有右子节点//要删除的节点只有左子节点//要删除的节点有左、右子节点//空树不能删除assert(_root ! nullptr);//找寻该节点node* parent nullptr;node* cur _root;while (cur){if (key cur-_key)//小于根左走{parent cur;cur cur-_left;}else if (key cur-_key)//大于根右走{parent cur;cur cur-_right;}else{//找到了该节点//节点只有右子结点或既没有左子节点也没有右子节点if (cur-_left nullptr){//根节点删除if (cur _root)//或if(parent nullptr){_root _root-_right;}//非根节点删除else{if (parent-_left cur){parent-_left cur-_right;}else if (parent-_right cur){parent-_right cur-_right;}}delete cur;}//节点只有左子节点else if (cur-_right nullptr){//根节点删除if (cur _root)//或if(parent nullptr){_root _root-_right;}//非根节点删除else{if (parent-_left cur){parent-_left cur-_left;}else if (parent-_right cur){parent-_right cur-_left;}}delete cur;}//节点左、右子节点都有else{//找右子树的最小节点node* parent cur;node* min_right cur-_right;while (min_right-_left){parent min_right;min_right min_right-_left;}//覆盖cur-_key min_right-_key;//托孤//由于min_right是右子树的最小节点所以这个节点一定是一直向左走得到的//所以当找到min_right时它一定没有左子树所以只需要托孤自己的右子节点即可if (parent-_left min_right){parent-_left min_right-_right;}else if (parent-_right min_right){parent-_right min_right-_right;}delete min_right;}return true;}}
}
删除函数也有递归写法
首先先通过递归找到需要删除的节点这个节点同样分为上面的三种情况也同样按照上面的方式删除。不过注意我们此时传递的是引用这就代表它传递的不只是子节点的地址它也是它父节点的左或右子节点的地址取决于该节点为左节点还是右节点直接将引用进行赋值就改变了父节点的指向。如果我们使用传值的方式传递对象 此时改变的只是这个临时对象而不会改变父节点的指向。
BSTree(const BSTreeK t)
{_root Copy(t._root);
}BSTreeK operator(BSTreeK t)
{swap(_root, t._root);return *this;
}~BSTree()
{Destroy(_root);_root nullptr;
}node* Copy(node* root)
{if (root nullptr) //空树直接返回return nullptr;node* copyNode new node(root-_key); //拷贝根结点copyNode-_left Copy(root-_left); //拷贝左子树copyNode-_right Copy(root-_right); //拷贝右子树return copyNode; //返回拷贝的树
}void Destroy(node* root)
{if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root
}
5补齐默认成员函数
包括赋值运算符重载、析构函数和拷贝构造函数都很简单
BSTree(const BSTreeK t)
{_root Copy(t._root);
}BSTreeK operator(BSTreeK t)
{swap(_root, t._root);return *this;
}~BSTree()
{Destroy(_root);_root nullptr;
}node* Copy(node* root)
{if (root nullptr) //空树直接返回return nullptr;node* copyNode new node(root-_key); //拷贝根结点copyNode-_left Copy(root-_left); //拷贝左子树copyNode-_right Copy(root-_right); //拷贝右子树return copyNode; //返回拷贝的树
}void Destroy(node* root)
{if (root nullptr)return;Destroy(root-_left);Destroy(root-_right);delete root
}
6中序遍历函数
这个函数就很简单了它的实现是用于检验二叉搜索树的中序遍历是否为升序。
void Inorder()
{_Inorder(_root);
}void _Inorder(const node* root)
{if (root nullptr)return;_Inorder(root-_left);std::cout root-_key ;_Inorder(root-_right);
}
二、AVL树
1.什么是AVL树
二叉搜索树是有其局限性的它的查找数据的时间复杂度为O(N)。这里你可能会不理解二叉搜索树每一层数据成倍数级上涨如果有三层数据最多查找三次就够了。为什么不是O(logN)呢
其实这种想法是没有问题的但是我们不妨设想一下一些极端的情况比如说我们按降序插入多个数字那么这些数字都会插入到左树就导致这个二叉搜索树一边十分地高近似一个顺序排列的数组这也是二叉搜索树最糟糕的状态查找的时间复杂度就是O(N)。一个程序的时间复杂度应该是分析它耗时最长的情况所以时间复杂度为O(N)。
此时AVL树就出场了AVL树就是为了解决二叉搜索树两子树高度差别过大的问题而建立的。它可以通过旋转的方式在一侧子树过高时降低它以尽可能达到二叉搜索树搜索数据的最佳状态。故它的中文名称叫做平衡二叉搜索树。
2.AVL树的简易实现
1构建类
AVL树调节平衡有很多种方式我们使用平衡因子法。
namespace MY_AVLTree
{templateclass K, class Vstruct AVLTreeNode{pairK, V _kv;//pair是一个由两个数据组成的结构体AVLTreeNode* _parent;//父指针AVLTreeNode* _left;//左子树指针AVLTreeNode* _right;//右子树指针int _bf; //平衡因子AVLTreeNode(pairK, V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}};templateclass K, class Vclass AVLTree{typedef AVLTreeNodeK, V Node;public://构造函数AVLTree():_root(nullptr){}private:Node* _root;};
}
2插入函数实现准备
在AVL树的实现中我们只学习插入函数。
它的实现主要包括三个部分查找需要插入空位置 - 更新平衡因子 - 在平衡因子出现大于1或小于1的情况下对树进行旋转。
第一步查找空位置
bool insert(pairK, V kv)
{if (_root nullptr)//树中还没有元素直接插入即可{_root new Node(kv);return true;}//定义一个parent指针和一个cur指针不断向下寻找可以插入的节点Node* parent nullptr;Node* cur _root;while (cur)//小于往左走大于往右走{if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false;}}//此时的cur就是可以插入的空位置//…………//接下来的函数操作//…………
}
第二步更新平衡因子
平衡因子是调节树高的重要变量每一个AVL树的节点都有一个平衡因子它是该节点右子树高度减去左子树高度的值表明了右树比左树高多少。
更新平衡因子是一个十分重要的过程平衡因子的调节遵循以下条件
新增节点在右子树右子树高度加一对应父节点平衡因子加一新增在左子树左子树高度加一对应父节点平衡因子减一新增后被插入节点的父节点平衡因子如果为0则表明要么是右树不为空且节点插入到左树要么是左树不为空且节点插入到右树。相当于插入一个节点补齐了子树中较矮的一侧此时父节点的子树高度不变也就不需要继续向上调节平衡因子新增后被插入节点的父节点平衡因子如果为1或-1则表明本来平衡的树在一侧又插入了一个节点这次父节点子树的高度就被改变了需要继续向上调整平衡因子当平衡因子大于等于2或者小于等于-2时此时该节点的左树和右树的高度差2此时需要旋转才可以降低较高的子树高度
bool insert(pairK, V kv)
{if (_root nullptr)//树中还没有元素直接插入即可{_root new Node(kv);return true;}//定义一个parent指针和一个cur指针不断向下寻找可以插入的节点Node* parent nullptr;Node* cur _root;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false;}}//找到了空位置cur new Node(kv);if (parent-_kv.first kv.first){parent-_left cur;//插入数据cur-_parent parent;//把新插入元素的父节点与其链接起来}else{parent-_right cur;//插入数据cur-_parent parent;//把新插入元素的父节点与其链接起来}//更新平衡因子while (parent){//新增的节点在左子树还是右子树if (parent-_right cur){//新增在右子树右子树高度加一对应父节点平衡因子加一parent-_bf;}else if (parent-_left cur){//新增在左子树左子树高度加一对应父节点平衡因子减一--parent-_bf;}//更新子树平衡因子根据子树高度是否变化判断是否需要继续向上更新平衡因子和旋转当前树//1.parent-_bf 0说明之前parent-_bf一定是 1 或者 -1//说明之前parent一边高一边低这次插入填上矮的那边parent所在子树高度不变不需要继续往上更新//2.parent-_bf 1 或 -1 说明之前是parent-_bf 0两边一样高现在插入一边更高了//parent所在子树高度变了继续往上更新//3.parent-_bf 2 或 -2说明之前parent-_bf 1 或者 -1现在插入严重不平衡违反规则//就地处理--旋转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){RotateLR(parent);//左右双旋}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);//右左双旋}else{assert(false);}break;}else{assert(false);}}
}
第三步四种旋转
左单旋
左单旋主要用于下面的情况右侧高且从需要被旋转的树根节点开始有连续的三个右节点
对于下面的情况就是将较高的3节点转移到6节点的左子节点然后将b子树变为3节点的右子树最后调节平衡因子 代码实现
//左单旋
void RotateL(Node* parent)
{Node* SubR parent-_right;//必不为空Node* SubRL SubR-_left;//可能为空Node* ppnode parent-_parent;//保存根的父节点parent-_right SubRL;if (SubRL)SubRL-_parent parent;SubR-_left parent;parent-_parent SubR;if (ppnode nullptr){_root SubR;SubR-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left SubR;}else{ppnode-_right SubR;}}SubR-_bf 0;parent-_bf 0;
}
右单旋
右单旋主要用于下面的情况左侧高且从需要被旋转的树根节点开始有连续的三个左节点
对于下面的情况就是将较高的3节点转移到1节点的右子节点然后将b子树变为3节点的左子树最后调节平衡因子 代码实现
//右单旋
void RotateR(Node* parent)
{Node* SubL parent-_left;Node* SubLR SubL-_right;Node* ppnode parent-_parent;parent-_left SubLR;if (SubLR)SubLR-_parent parent;SubL-_right parent;parent-_parent SubL;if (ppnode nullptr){SubL-_parent nullptr;_root SubL;}else{if (ppnode-_left SubL){ppnode-_left SubL;}else{ppnode-_right SubL;}}SubL-_bf 0;parent-_bf 0;
}
左右双旋
左右双旋主要用于下面的情况从需要被旋转的树根节点的子节点开始存在一个左子节点再在这个左子节点接上右子节点
对于下面的情况就是以1为根节点进行左单旋然后就会转化为右单旋的情况再对以3为根做右单旋最后根据下面的三种情况调整平衡因子 代码实现
//左右双旋
void RotateLR(Node* parent)
{Node* SubL parent-_left;Node* SubLR SubL-_right;int bf SubLR-_bf;RotateL(parent-_left);RotateR(parent);//插在b子树if (bf -1){parent-_bf 1;SubL-_bf 0;SubLR-_bf 0;}//插在c子树else if (bf 1){parent-_bf 0;SubL-_bf -1;SubLR-_bf 0;}//本身是新增else if (bf 0){parent-_bf 0;SubL-_bf 0;SubLR-_bf 0;}//错误情况else{assert(false);}
}
右左双旋
右左双旋主要用于下面的情况从需要被旋转的树根节点的子节点开始存在一个右子节点再在这个右子节点接上左子节点
对于下面的情况就是以4为根节点的树进行右单旋然后就会转化为左单旋的情况再对以2为根的树做左单旋最后根据下面的三种情况调整平衡因子 代码实现
//右左双旋
void RotateRL(Node* parent)
{Node* SubR parent-_right;Node* SubRL SubR-_left;int bf SubRL-_bf;RotateR(parent-_right);RotateL(parent);//插在b子树if (bf -1){parent-_bf 0;SubR-_bf 1;SubRL-_bf 0;}//插在c子树else if (bf 1){parent-_bf -1;SubR-_bf 0;SubRL-_bf 0;}//本身是新增else if (bf 0){parent-_bf 0;SubR-_bf 0;SubRL-_bf 0;}//错误情况else{assert(false);}
}
3AVL树的检验
AVL树的检验
bool IsBalance()
{return IsBalance(_root);
}bool IsBalance(Node* root)
{if (root nullptr){return true;//空树一定是AVL树}int leftHeight Height(root-_left);//计算左树的高度int rightHeight Height(root-_right);//计算右树的高度if (rightHeight - leftHeight ! root-_bf)//平衡因子必须满足右树高减左树高{cout root-_kv.first 平衡因子异常 endl;return false;}return abs(rightHeight - leftHeight) 2//左树和右树的高度差绝对值不超过1 IsBalance(root-_left) IsBalance(root-_right);
}
