做网站能力介绍网站做优化好还是推广好
1. 二叉搜索树
1.1 二叉搜索树概念
二叉搜索树又称二叉排序树，他或者是一棵空树，或者是具有以下性质的二叉树：
①若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
②若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
③它的左右子树也分别为二叉搜索树
1.2 二叉搜索树操作
int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
1.二叉搜索树的查找
a、从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
b、最多查找高度次，走到空，还没找到，这个值不存在。
2.二叉搜索树的插入
插入的具体过程如下：
a、树为空，则直接新增节点，赋值给root指针
b、树不为空，按二叉搜索树性质查找插入位置，插入新节点。
3.二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的节点可能分下面四种情况：
a、要删除的节点无孩子节点
b、要删除的节点只有左孩子节点
c、要删除的节点只有右孩子节点
d、要删除的节点有左、右孩子节点
看起来有待删除节点有四种情况，实际情况a可以与b、c结合起来，因此真正的删除过程如下：
*有一个孩子或者无孩子的节点被删除，则让被删除节点的双亲指向被删除节点的孩子或者空——直接删除
*有两个孩子的节点被删除，则在它的右子树中寻找最小的节点，用它的值填补到删除节点中，再来处理该节点的删除问题（符合二叉搜索树，左节点<根<右节点）——替换法删除
1.3 二叉搜索树的实现
树的节点
树
完整代码：
template <class T>
struct BSTNode
{T _key;BSTNode<T>* _left;BSTNode<T>* _right;BSTNode(const T& key):_left(nullptr), _right(nullptr), _key(key){}
};template <class T>
class BSTree
{typedef BSTNode<T> Node;public:BSTree() = default;BSTree(const BSTree<T>& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}bool insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const T& key){Node* cur = _root;while (cur){if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool Erase(const T& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << endl;_InOrder(root->_right);}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key);newroot->_left = Copy(root->_left);newroot->_right = Copy(root->_right);return newroot;}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}Node* _root = nullptr;
};1.4 二叉搜索树的应用
1.K模型：K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
*以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
*在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型：每一个关键码key，都有与之对应的值Value，即的键值对。该种方式在现实生活中非常常见：
*比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文就构成一种键值对；
*再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是就构成一种键值对。
改造成kv结构的二叉搜索树的代码（与前面的逻辑基本上是一样的，无非就是多了一个值value）
完整代码：
using namespace std;template <class T,class V>
struct BSTNode
{T _key;V _value;BSTNode<T,V>* _left;BSTNode<T,V>* _right;BSTNode(const T& key,const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template <class T,class V>
class BSTree
{typedef BSTNode<T,V> Node;public:BSTree() = default;BSTree(const BSTree<T, V>& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}bool insert(const T& key,const V& value){if (_root == nullptr){_root = new Node(key,value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key,value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}Node* Find(const T& key){Node* cur = _root;while (cur){if (cur->_key < key)cur = cur->_right;else if (cur->_key > key)cur = cur->_left;elsereturn cur;}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}bool Erase(const T& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 删除// 0-1个孩子的情况if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;return true;}else{// 2个孩子的情况// 右子树的最小节点作为替代节点Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;elserightMinP->_right = rightMin->_right;delete rightMin;return true;}}}return false;}private:void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newroot = new Node(root->_key, root->_value);newroot->_left = Copy(root->_left);newroot->_right = Copy(root->_right);return newroot;}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}Node* _root=nullptr;
};1.5 二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：$log_2 N$
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：$\frac{N}{2}$
问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，二叉搜索树的性能都能达到最优？那么AVL树和红黑树就可以上场了，但是这边就不继续讲述AVL和红黑树了。