平衡二叉树

目录

一、平衡二叉树的概念以及性能分析

1、概念

2、平衡二叉树的性能分析

二、平衡二叉树的代码实现

1、插入数据

2、查找数据

3、删除数据

三、Key_Value搜索

---

一、平衡二叉树的概念以及性能分析

1、概念

• 若平衡二叉树的左子树不为空，那么左子树上所有节点的值都小于根节点的值；
• 若平衡二叉树的右子树不为空，那么右子树上所有节点的值都大于根节点的值；
• 对于平衡二叉树的左子树和右子树也满足上述规律；
• 平衡二叉树中可存放相同的值，也可以不存放；若是存放，那么第一、二条规律加一个等于。

2、平衡二叉树的性能分析

这里的性能指的是在树里面找指定值的节点；根据左子树节点值小于根节点，右子树值大于根节点值，每次判断指定的值大于还是小于根节点的值，来实现往左子树走还是右子树走并且向下遍历了；

• 一般来说，时间复杂度是 O(logN)，类似于二分查找；
• 最坏情况就是树只有单支，只往一个方向遍历，那么就是O(N)级的时间复杂度；
• 所以综合来讲平衡二叉树查找数据的时间复杂度是O(N)；

相比于普通的二分查找，平衡二叉树具有的优势就是不会被限制于下标的固定形式去查找；并且平衡二叉树插入和删除数据时，不需要像数组结构那样大量地去移动元素；

二、平衡二叉树的代码实现

节点结构：

	template<class K>struct BSnode{K _key;BSnode<K>* _left;BSnode<K>* _right;BSnode(const K& key=K()):_key(key),_left(nullptr),_right(nullptr){}};

1、插入数据

二叉树实例化出对象，_root的缺省值给nullptr；

开始插入时树内没有节点，走第一个if，那么这个申请的节点就是这棵树的根节点；

后面的为了满足平衡二叉树的结构，插入时先比较，判断去左子树还是右子树，若是存在相同节点就不插入（这里规则默认为不存相同的值）；

定义一个parent节点是因为最终cur会走到空，parent最终就是每颗子树最底部的节点，循环结束后，判断key是大于还是小于parent的值来确定插入到左子树还是右子树。

using Node = BSnode<K>;//类似于typedef
//_root为Node* 类型的根节点，这里是私有成员变量
bool Insert(const K& key)
{if (!_root){_root = new Node(key);}else{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{break;}}if (key < parent->_key){parent->_left = new Node(key);return true;}else if(key > parent->_key){parent->_right = new Node(key);return true;}}return false;
}

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;
}

3、删除数据

首先查找要删除的数据存不存在，不存在最终cur走到空，循环结束返回假；

若是存在删除时分为几种情况：

        1、删除的节点左右子树都是空；

        2、删除的节点左子树或者右子树中只有一颗是空树；

        3、删除的节点左右子树都不是空；

解决方案：

        a：对于1，2两种情况适用于一种解决方案。若是这个节点一颗子树为空，那么就让这个节点的父节点指向这个节点的另一棵子树，再删除掉这个节点；对于情况1，所谓的另一颗子树就是空，但是最后还是达到了效果；

        补充说明：当要删除的节点是根节点时，parent在查找完之后还是空，那么后面不能解引用，所以要单独处理这个cur就是根节点的情况：根节点置为另一颗子树，再删除掉根节点；

        父节点重新指向时，要先判断删除节点原来是被父节点的右指针指向的还是左指针指向的来确定父节点的哪个指针要重新指向。

        b：对于情况3，找到一个替换的节点，这个节点是要删除的节点的右子树的最左节点或者是左子树的最右节点，找到替换节点后，将替换节点的值给要删除的节点，这是为了不打破平衡二叉树规则，再让此被删除节点的父节点指向此被删除节点的另一颗子树，再删除掉替换节点；这样转换了删除的节点，但是还是达到了相同的效果；

        若替换节点找的是右子树的最左节点，那么此替换节点的左子树一定为空，找到替换节点后，先让父节点指向替换节点的右子树，当找的是左子树的最右节点时，同理；

        值得注意的是替换节点的父节点初始值不能给nullptr，这是因为当右子树的根节点的第一个左子树就是空时，若替换节点父节点初始为nullptr，那么替换节点的父节点还是nullptr，后面解引用会出错；所以给cur；

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;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)//左为空{if (parent==nullptr)//可能第一个就要删，那么parent就是空，这里要单独处理{_root = cur->_right;}else if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}delete cur;return true;}else if (!cur->_right)//右为空{if (parent == nullptr){_root = cur->_left;}else if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right == cur){parent->_right = cur->_left;}delete cur;return true;}else if (cur->_left && cur->_right){Node* replace = cur->_right;Node* replace_p = cur;//不能初始为空，可能右子树第一个根节点的左子树就是空，//那replace_p就能解引用了while (replace->_left)//右子树的最左节点{replace_p = replace;replace = replace->_left;}//交换cur->_key = replace->_key;if (replace_p->_left == replace){replace_p->_left = replace->_right;}else if (replace_p->_right == replace){replace_p->_right = replace->_right;}delete replace;return true;}}}return false;
}

三、Key_Value搜索

上面的平衡二叉树是Key的搜索场景，找的是key；

这里介绍的是key带着一个value的情况，key不能被修改，找到key就找到value；value是和key相关的；例如通过key为英文单词，value是对应中文意思；

实现的代码：只需要将节点的成员变量加上一个value；

namespace Key_Value
{template<class K,class V>struct BSnode{K _key;V _value;BSnode<K,V>* _left;BSnode<K,V>* _right;BSnode(const K& key = K(),const V& value=V()):_key(key),_value(value), _left(nullptr), _right(nullptr){}};template<class K,class V>class BStree{using Node = BSnode<K,V>;public:BStree() = default;BStree(const BStree<K, V>& b){_root = Copy(b._root);}void operator=(BStree<K, V> tmp){swap(_root, tmp->_root);}~BStree(){Destroy(_root);}bool Insert(const K& key,const V& value){if (!_root){_root = new Node(key,value);}else{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{break;}}if (key < parent->_key){parent->_left = new Node(key,value);return true;}else if (key > parent->_key){parent->_right = new Node(key,value);return true;}}return false;}Node* 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 cur;}}return nullptr;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;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)//左为空{if (parent == nullptr)//可能第一个就要删，那么parent就是空，这里要单独处理{_root = cur->_right;}else if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right == cur){parent->_right = cur->_right;}delete cur;return true;}else if (!cur->_right)//右为空{if (parent == nullptr){_root = cur->_left;}else if (parent->_left == cur){parent->_left = cur->_left;}else if (parent->_right == cur){parent->_right = cur->_left;}delete cur;return true;}else if (cur->_left && cur->_right){Node* replace = cur->_right;Node* replace_p = cur;//不能初始为空，可能右子树第一个根节点的左子树就是空，那replace_p就能解引用了while (replace->_left)//右子树的最左节点{replace_p = replace;replace = replace->_left;}交换cur->_key = replace->_key;if (replace_p->_left == replace){replace_p->_left = replace->_right;}else if (replace_p->_right == replace){replace_p->_right = replace->_right;}delete replace;return true;}}}return false;}void InorderPrint(){Inorder(_root);cout << endl;}private:Node* _root = nullptr;void Inorder(const Node* root){if (root == nullptr){return;}Inorder(root->_left);cout << root->_key << " -> " << root->_value << endl;Inorder(root->_right);}Node* Copy(const 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 Destroy(Node* root){if (!root)return;Destroy(root->_left);Destroy(root->_right);delete root;}};
}