虚拟主机网站建设实训总结,吉林大学建设工程学院官方网站,怎么上传网站程序到空间,2021百度模拟点击工具1:二叉搜索树的定义 二叉搜索树的底层是一个二叉链表 二叉搜索树又称二叉排序树#xff0c;它或者是一棵空树 #xff0c;或者是具有以下性质的二叉树 : 若它的左子树不为空#xff0c;则左子树上所有节点的值都小于根节点的值 若它的右子树不为空#xff0c;则右子树上所…1:二叉搜索树的定义 二叉搜索树的底层是一个二叉链表 二叉搜索树又称二叉排序树它或者是一棵空树 或者是具有以下性质的二叉树 : 若它的左子树不为空则左子树上所有节点的值都小于根节点的值 若它的右子树不为空则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 举个例子,我们要把数组[50,87,64,100,24,35,1,77]插入到二叉搜索树中,对应的树应该是这个样子 2.二叉搜索树的特点 既然以搜索树为名字,显然搜索功能是很强大的(相较于数组的搜索),对于二叉树的每一个节点来说其左子树的任意值绝对小于根节点,右子树的任意值绝对大于根节点,如果我们要查找一个值,该值比根节点小的话去左子树找,比根节点大的话去右子树找,如果二叉搜索树是一颗满二叉树的话,搜索的时间复杂度将为log(N),相当于从全世界70亿人中找一个人仅用了30次操作.因为二叉树的左子树的任意值绝对小于根节点,右子树的任意值绝对大于根节点,所以其中序遍历即为升序数组,搜索树理论上不可以同时存在多个相同的元素,因为这是没有意义的,所以严格来说,这是一个无重复元素的升序数组 3.二叉搜索树的底层原理
插入 显然原树在执行完插入操作后仍应该是二叉搜索树,为了不破坏原树的结构,对于根节点来说,如果插入值大于根节点,应该往右插入,插入值小于根节点,应该往左插入.直到最后1.找到的节点为空,代表应该向空节点处插入2.存在节点值 插入值,这样的插入是无意义的,插入失败! 以上图为例,如果要插入一个76 模拟实现
/* template class T//二叉搜索的节点struct TreeNode {typedef TreeNodeT Node;Node* _left;Node* _right;T _val;//构造函数TreeNode(T val T()):_left(nullptr),_right(nullptr),_val(val){}};
*/bool insert(T val) {if (_root nullptr){_root new Node(val);}Node* child _root;Node* parent _root;while (child ! nullptr) {parent child;if (val child-_val) //val比根节点小,往左走{child child-_left;}else if (val child-_val) //val比根节点大,往右走{child child-_right;}else {return false; //val与根节点相等,二叉搜索树中不许存在相同元素,所以不可插入,返回假}}if (parent-_val val) parent-_right new Node(val);else if (parent-_val val) parent-_left new Node(val);return true; //插入成功
}
查找 查找与插入很类似,大于的话去右边找,小于的话去左边找,找到了返回节点,没找到返回nullptr 以找64为例 模拟实现
/* template class T//二叉搜索的节点struct TreeNode {typedef TreeNodeT Node;Node* _left;Node* _right;T _val;//构造函数TreeNode(T val T()):_left(nullptr),_right(nullptr),_val(val){}};
*/Node* find(T val) {Node* tmp _root;while (tmp ! nullptr) {if (val tmp-_val)return tmp; //找到啦else if (val tmp-val) {tmp tmp-_right; //val大于该节点的值,去右子树找}else {tmp tmp-_left; //val小于该节点的值,去左子树找}}return nullptr; //树里没有val,不存在该节点
}
删除 这边我们重画一个比较大一些的搜索二叉树以便于举例,数据很简单,1到16 首先,当删去8时,其余的所有节点都仍旧符合搜索二叉树的定义,删去其他叶子节点有相同的效果,同理,在删去2节点时,理论上来说仅有2的子树受到影响,搜索树的其他部分仍旧符合定义. 再以删去九号节点为例,由于二叉树的定义,删去九号节点后新节点的值必须满足除自身外,左子树都小于其,右子树都大于其. 由上图为例,对二叉树进行分析可得:除8外的左树8910除10外的右树,也就是说: 左子树的右边的右边的右边的......的叶节点和右子树左边的左边的.......的叶节点最适合做根节点 特殊情况1:左子树没有右节点 使用左子树自身的根节点即可. 特殊情况2:没有左子树只有一个孩子节点 上图为删除节点4的示意图,可以看出,4号节点没有左子树,此时4号节点仅有一个子节点,直接让子节点代替自己即可 模拟实现 bool earse(const T val) {Node* parent _root;Node* child _root;while (child! nullptr) {if (val child-_val){parent child;child child-_right;}else if (val child-_val){parent child;child child-_left;}else //相等{if (child-_left nullptr){if (child _root)_root child-_right;else {if (parent-_left child) parent-_left child-_right;else if (parent-_right child) parent-_right child-_right;}delete child;}else if (child-_right nullptr) {if (child _root)_root child-_left;else {if (parent-_left child) parent-_left child-_left;else if (parent-_right child) parent-_right child-_left;}delete child;}else {Node* tmp child-_left;Node* pp tmp;while (tmp-_right) {pp tmp;tmp tmp-_right;}child-_val tmp-_val;if (pp ! tmp)pp-_right tmp-_left;delete tmp;}return true;}}return false;}
高度(不重要) public:size_t height() {return _height(_root);}private:size_t _height(Node* root) {if (root nullptr)return 0;elsereturn _height(root-_left) _height(root-_right) 1;} 节点个数(不重要) public:size_t size() {return _size(_root);}private:size_t _size(Node* root) {if (root nullptr)return 0;return _size(root-_left) _size(root-_right) 1;}
打印(不重要)
void print() {std::queueNode* q1,q2;q1.push(_root);while (!q1.empty() || !q2.empty()) {while (!q1.empty()) {if (q1.front() nullptr)std::cout # ;else {q2.push(q1.front()-_left);q2.push(q1.front()-_right);std::cout q1.front()-_val ;}q1.pop();}std::swap(q1,q2);std::cout std::endl;}} 搜索二叉树模拟实现
#include queue
#include iostream
namespace SearchTree {template class T//二叉搜索的节点struct TreeNode {typedef TreeNodeT Node;Node* _left;Node* _right;T _val;//构造函数TreeNode(T val T()):_left(nullptr),_right(nullptr),_val(val){}};template class Tclass SearchTree {typedef TreeNodeT Node;Node* _root; //根节点public:SearchTree():_root(nullptr){} //构造函数bool insert(T val) {if (_root nullptr){_root new Node(val);}Node* child _root;Node* parent _root;while (child ! nullptr) {parent child;if (val child-_val) //val比根节点小,往左走{child child-_left;}else if (val child-_val) //val比根节点大,往右走{child child-_right;}else {return false; //val与根节点相等,二叉搜索树中不许存在相同元素,所以不可插入,返回假}}if (parent-_val val) parent-_right new Node(val);else if (parent-_val val) parent-_left new Node(val);return true; //插入成功}bool earse(const T val) {Node* parent _root;Node* child _root;while (child! nullptr) {if (val child-_val){parent child;child child-_right;}else if (val child-_val){parent child;child child-_left;}else //相等{if (child-_left nullptr){if (child _root)_root child-_right;else {if (parent-_left child) parent-_left child-_right;else if (parent-_right child) parent-_right child-_right;}delete child;}else if (child-_right nullptr) {if (child _root)_root child-_left;else {if (parent-_left child) parent-_left child-_left;else if (parent-_right child) parent-_right child-_left;}delete child;}else {Node* tmp child-_left;Node* pp tmp;while (tmp-_right) {pp tmp;tmp tmp-_right;}child-_val tmp-_val;if (pp ! tmp)pp-_right tmp-_left;delete tmp;}return true;}}return false;}Node* find(T val) {Node* tmp _root;while (tmp ! nullptr) {if (val tmp-_val)return tmp; //找到啦else if (val tmp-val) {tmp tmp-_right; //val大于该节点的值,去右子树找}else {tmp tmp-_left; //val小于该节点的值,去左子树找}}return nullptr; //树里没有val,不存在该节点}void print() {std::queueNode* q1,q2;q1.push(_root);while (!q1.empty() || !q2.empty()) {while (!q1.empty()) {if (q1.front() nullptr)std::cout # ;else {q2.push(q1.front()-_left);q2.push(q1.front()-_right);std::cout q1.front()-_val ;}q1.pop();}std::swap(q1,q2);std::cout std::endl;}}size_t size() {return _size(_root);}size_t height() {return _height(_root);}private:size_t _size(Node* root) {if (root nullptr)return 0;return _size(root-_left) _size(root-_right) 1;}size_t _height(Node* root) {if (root nullptr)return 0;elsereturn std::max(_height(root-_left) , _height(root-_right)) 1;}};
} 对搜索二叉树的分析及AVL树红黑树的优势 参考我在前文查找处的分析可得查找的时间复杂度与树的高度空间复杂度恒为o(1)当插入从a到b的值是优先输入[a,b]中间的值后输入接近a,b的极端值此时树较为平衡查找的时间复杂度接近o(logn)而当数据有序的进行插入时树相当于一个链表时间复杂度较高为o(n) 举个例子当把数据[1,2,3,4,5,6,7]插入二叉树时 以[4,2,1,3,6,5,7]插入时如果我们要查找7需要进行三次判断即可 以[1,2,3,4,5,6,7]插入时如果我们要查找7需要进行七次判断时间复杂度为o(n)再加上额外的空间开销还不如直接在原数组中查找 如果有一种改进的插入方式可以在插入时依据原树的高度差进行动态的重构树结构便可大大加快查找速度 附AVL树模拟实现供参考
#include queue
#include iostream
#include assert.h
namespace AVL {templateclass Tstruct AVLTreeNode{AVLTreeNode(const T data T()): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNodeT* _pLeft;AVLTreeNodeT* _pRight;AVLTreeNodeT* _pParent;T _data;int _bf; // 节点的平衡因子};// AVL: 二叉搜索树 平衡因子的限制templateclass Tclass AVLTree{typedef AVLTreeNodeT Node;public:AVLTree(): _pRoot(nullptr){}void print() {std::queueNode*q1;std::queueNode*q2;q1.push(_pRoot);while (!q1.empty() || !q2.empty()) {while (!q1.empty()){if (q1.front() ! nullptr) {std::cout q1.front()-_data ;q2.push(q1.front()-_pLeft);q2.push(q1.front()-_pRight);}elsestd::cout # ;q1.pop();}swap(q1, q2);std::cout std::endl;}}// 在AVL树中插入值为data的节点bool Insert(const T data) {Node* node new Node(data);if (_pRoot nullptr) {_pRoot node;return true;}Node* parent _pRoot,*child _pRoot;while (child) {parent child;if (child-_data data) child child-_pLeft;else if (child-_data data) child child-_pRight;else return false;}if (parent-_data data){parent-_pRight node;}else{parent-_pLeft node;}node-_pParent parent;while (parent) {if (node parent-_pLeft)parent-_bf--;elseparent-_bf;if (parent-_bf 0)break;else if (parent-_bf 1 || parent-_bf -1)node parent, parent parent-_pParent;else { //出问题了if (parent-_bf -2 node-_bf -1) {RotateR(node);}else if (parent-_bf -2 node-_bf 1){RotateLR(node);}else if (parent-_bf 2 node-_bf 1) {RotateL(parent);}else if (parent-_bf -2 node-_bf -1) {RotateRL(node);}else {// 树损坏}}}return true;}// AVL树的验证bool IsAVLTree(){return _IsAVLTree(_pRoot);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAVLTree(Node* pRoot) {std::queueNode* q;q.push(pRoot);while (!q.empty()) {if (q.front() nullptr){q.pop();continue;}if (q.front()-_bf 2 || q.front()-_bf -2){return false;}else {q.push(q.front()-_pLeft);q.push(q.front()-_pRight);q.pop();}}return true;}size_t _Height(Node* pRoot) {size_t h 0;std::queueNode* q1;std::queueNode* q2;q2.push(pRoot);while (!q1.empty()!q2.empty()) {while (!q1.empty()){if (q1.front() ! nullptr){q2.push(q1.front()-_pLeft);q2.push(q1.front()-_pRight);}q1.pop();}std::swap(q1, q2);h;}q1.empty();q2.empty();return h - 1;}// 左单旋void RotateL(Node* pParent) {//新的头节点Node* new_Parent pParent-_pRight;//旧头结点的父节点Node* grand pParent-_pParent;//修改pParent的父节点if (grand ! nullptr){if (grand-_pLeft pParent)grand-_pLeft new_Parent;elsegrand-_pRight new_Parent;}else {_pRoot new_Parent;}// 修改pParent节点pParent-_pParent new_Parent;pParent-_pRight new_Parent-_pLeft;//修改new_Parent节点if(new_Parent-_pLeft!nullptr)new_Parent-_pLeft-_pParent pParent;new_Parent-_pLeft pParent;new_Parent-_pParent grand;pParent-_pParent new_Parent;pParent-_bf new_Parent-_bf 0;}// 右单旋void RotateR(Node* pParent) {//新的头节点Node* new_Parent pParent-_pLeft;//旧头结点的父节点Node* grand pParent-_pParent;//修改pParent的父节点if (grand ! nullptr){if (grand-_pLeft pParent)grand-_pLeft new_Parent;elsegrand-_pRight new_Parent;}else {_pRoot new_Parent;}// 修改pParent节点pParent-_pParent new_Parent;pParent-_pLeft new_Parent-_pRight;//修改new_Parent节点if(new_Parent-_pRight!nullptr)new_Parent-_pRight-_pParent pParent;new_Parent-_pRight pParent;new_Parent-_pParent grand;pParent-_pParent new_Parent;pParent-_bf new_Parent-_bf 0;}// 右左双旋void RotateRL(Node* pParent) {RotateR(pParent);RotateL(pParent-_pParent-_pParent);}// 左右双旋void RotateLR(Node* pParent) {RotateL(pParent);RotateR(pParent-_pParent-_pParent);}protected:Node* _pRoot;};
} 结语 截止至结语本文已有接近1万字制作不易可以留个免费的赞吗
