如何推广自己的个人网站呢,网页制作公司哪家比较好,益阳市住房和城乡建设局网站,扒站wordpress主题二叉树进阶
1.二叉搜索树(binary search tree)
二叉搜索树天然就适合查找#xff0c;对于满二叉树或者完全二叉树#xff0c;最多搜索lgn次(就像是有序数组二分查找#xff0c;每次搜索都会减少范围)#xff0c;极端情况简化成单链表就要走n次#xff0c;即要走高度次…二叉树进阶
1.二叉搜索树(binary search tree)
二叉搜索树天然就适合查找对于满二叉树或者完全二叉树最多搜索lgn次(就像是有序数组二分查找每次搜索都会减少范围)极端情况简化成单链表就要走n次即要走高度次时间复杂度是O(N)。所以需要用时间复杂度为O(lgn)的AVL树(平衡二叉树)或者RB树(红黑树)解决。
按中序遍历得到的结果就是有序的升序后序删除方便很多不用保留前面的值拷贝不可以调用插入否则结构会发生巨大的变化而是使用前序来赋值 。
相较于普通的二叉树增删查改就有了意义而有序数组二分查找是不可以的挪动数据效率很低。
二叉搜索树不允许有重复key一般要唯一。
1.1概念
二叉搜索树又称二叉排序树它或者是一棵空树或者是具有以下性质的二叉树:
1.若它的左子树不为空则左子树上所有节点的值都小于根节点的值 ;
2.若它的右子树不为空则右子树上所有节点的值都大于根节点的值 ;
3.它的左右子树也分别为二叉搜索树
2.二叉搜索树非递归模拟实现
#pragma once
#include cassert
namespace BinarySearchTree
{template class Kstruct BSTreeNode{BSTreeNode(const K key 0) : left_(nullptr), right_(nullptr), key_(key) {}BSTreeNodeK *left_;BSTreeNodeK *right_;K key_;};template class Kclass BSTree{// 内嵌类型typedef BSTreeNodeK node;public:// 默认成员函数BSTree() : root_(nullptr){}~BSTree() {}public:// 普通成员函数bool insert(const K key);void inorder(){_inorder(root_);}void _inorder(node *root);bool find(const K key);bool erase(const K key);private:// 成员变量node *root_;};template class Kbool BSTreeK::insert(const K key){if (root_ nullptr){root_ new node(key);return true;}node *cur root_;node *parent root_;while (cur){if (cur-key_ key){return false;}else if (key cur-key_){parent cur;cur cur-right_;}else{parent cur;cur cur-left_;}}cur new node(key);if (key parent-key_){parent-right_ cur;}else{parent-left_ cur;}return true;}template class Kvoid BSTreeK::_inorder(BSTreeK::node *root){if (root nullptr){return;}_inorder(root-left_);cout root-key_ ;_inorder(root-right_);}template class Kbool BSTreeK::find(const K key){if (root_ nullptr){return false;}node *cur root_;while (cur){if (key cur-key_){return true;}else if (key cur-key_){cur cur-right_;}else{cur cur-left_;}}return false;}template class Kbool BSTreeK::erase(const K key){node *cur root_;node *parent cur;while (cur){if (key cur-key_){// 找到了,托孤要考虑删root// 没有孩子托孤nullptr// 有一个孩子托孤if (cur-left_ nullptr){if (cur root_){parent cur-right_;}else{if (key_ parent-key_){parent-right_ cur-right_;}else{parent-left_ cur-right_;}}}else if (cur-right_ nullptr){if (cur root_){parent cur-left_;}else{if (key_ parent-key_){parent-right_ cur-left_;}else{parent-left_ cur-left_;}}}else // 有两个孩子要取左子树最右或者右子树最左{node *leftmax cur-left_; // 可能cur-left为leftmaxnode *pleftmax cur;while (leftmax-right_){pleftmax leftmax;leftmax leftmax-right_;}std::swap(cur-key_, leftmax-key_);if (pleftmax-left_ leftmax){pleftmax-left_ leftmax-left_;}else{pleftmax-right_ leftmax-left_;}cur leftmax;}delete cur;return true;}else if (key cur-key_){parent cur;cur cur-right_;}else{parent cur;cur cur-left_;}}return false;}}3.二叉搜索树优点
1.查找效率高
2.可以顺便实现排序升序
3.插入删除效率都不错
4.二叉搜索树递归实现
#pragma once
#include cassert
namespace BinarySearchTree
{template class Kstruct BSTreeNode{BSTreeNode(const K key 0) : left_(nullptr), right_(nullptr), key_(key) {}BSTreeNodeK *left_;BSTreeNodeK *right_;K key_;};template class Kclass BSTree{// 内嵌类型typedef BSTreeNodeK node;public:// 默认成员函数BSTree() : root_(nullptr){}BSTree(const BSTreeK t){root_ copy(t.root_);}BSTreeK operator(BSTreeK t){swap(*this, t);return *this;}~BSTree(){destroy(root_);}public:// 普通成员函数void swap(BSTreeK t);bool insert(const K key){return _insert(root_, key);}void inorder(){_inorder(root_);cout endl;}bool find(const K key){return _find(root_, key);}bool erase(const K key){return _erase(root_, key);}private:// 私有成员node *copy(node *root);void destroy(node *root);bool _insert(node *root, const K key);bool _find(node *root, const K key);void _inorder(node *root);bool _erase(node *root, const K key);node *root_;};template class Kbool BSTreeK::_insert(node *root, const K key){if (root nullptr){root new node(key);return true;}if (key root-key_){return _insert(root-right_, key);}else if (key root-key_){return _insert(root-left_, key);}else{return false;}}template class Kvoid BSTreeK::_inorder(node *root){if (root nullptr){cout nullptr ;return;}_inorder(root-left_);cout root-key_ ;_inorder(root-right_);}template class Kbool BSTreeK::_find(node *root, const K key){if (root nullptr){return false;}if (key root-key_){return _find(root-right_, key);}else if (key root-key_){return _find(root-left_, key);}else{return true;}}template class Kbool BSTreeK::_erase(node *root, const K key){if (root nullptr){return false;}if (key root-key_){return _erase(root-right_, key);}else if (key root-key_){return _erase(root-left_, key);}else{node *del root;if (root-left_ nullptr){root root-right_;}else if (root-right_ nullptr){root root-left_;}else{node *leftmax root-left_;while (leftmax-right_){leftmax leftmax-right_;}std::swap(leftmax-key_, root-key_);return _erase(root-left_, key);}delete del;return true;}}template class Kvoid BSTreeK::destroy(node *root){if (root nullptr){return;}destroy(root-left_);destroy(root-right_);delete root;root nullptr;}template class Ktypename BSTreeK::node *BSTreeK::copy(node *root){if (root nullptr){return nullptr;}node *newnode new node(root-key_);newnode-left_ copy(root-left_);newnode-right_ copy(root-right_);return newnode;}template class Kvoid BSTreeK::swap(BSTreeK t){std::swap(root_, t.root_);}
}5.二叉搜索树的应用场景
5.1key的搜索模型(在不在的场景)
门禁系统、车辆输入系统、查找单词是否拼写错误将词库放到一颗搜索树之中然后find。
5.1key/value的搜索模型(通过一个值找另外一个值)
手机号找快递信息、停车场(按时计费)、身份证检票查找车票信息不用制造车票并往车票里写入信息
namespace key_value
{template class K, class Vstruct BSTreeNode{BSTreeNode(const K key K(), const V value V()) : left_(nullptr), right_(nullptr), key_(key), value_(value) {}BSTreeNodeK, V *left_;BSTreeNodeK, V *right_;K key_;V value_;};template class K, class Vclass BSTree{// 内嵌类型public:typedef BSTreeNodeK, V node;public:// 默认成员函数BSTree() : root_(nullptr){}~BSTree(){}public:// 普通成员函数bool insert(const K key, const V value){return _insert(root_, key, value);}void inorder(){_inorder(root_);cout endl;}node *find(const K key){return _find(root_, key);}bool erase(const K key){return _erase(root_, key);}private:// 私有成员bool _insert(node *root, const K key, const V value);node *_find(node *root, const K key);void _inorder(node *root);bool _erase(node *root, const K key);node *root_;};template class K, class Vbool BSTreeK, V::_insert(node *root, const K key, const V value){if (root nullptr){root new node(key, value);return true;}if (key root-key_){return _insert(root-right_, key, value);}else if (key root-key_){return _insert(root-left_, key, value);}else{return false;}}template class K, class Vvoid BSTreeK, V::_inorder(node *root){if (root nullptr){return;}_inorder(root-left_);cout root-key_ : root-value_ ;_inorder(root-right_);}template class K, class Vtypename BSTreeK, V::node *BSTreeK, V::_find(node *root, const K key){if (root nullptr){return nullptr;}if (key root-key_){return _find(root-right_, key);}else if (key root-key_){return _find(root-left_, key);}else{return root;}}template class K, class Vbool BSTreeK, V::_erase(node *root, const K key){if (root nullptr){return false;}if (key root-key_){return _erase(root-right_, key);}else if (key root-key_){return _erase(root-left_, key);}else{node *del root;if (root-left_ nullptr){root root-right_;}else if (root-right_ nullptr){root root-left_;}else{node *leftmax root-left_;while (leftmax-right_){leftmax leftmax-right_;}std::swap(leftmax-key_, root-key_);return _erase(root-left_, key);}delete del;return true;}}
}
