一文學會二叉搜索樹，AVL樹，紅黑樹

文章目錄

二叉搜索樹
- 查找
- 插入
- 刪除
AVL樹
- 概念
- 插入
- 旋轉
- AVL驗證
紅黑樹
- 概念
- 插入
- 檢測

二叉搜索樹

也稱二叉排序樹或二叉查找樹

二叉搜索樹：可以為空，若不為空滿足以下性質
?1，非空左子樹小于根節點的值
?2，非空右子大于根節點的值
?3，左右子樹都是二叉搜索樹
在這里插入圖片描述

二叉搜索樹節點代碼：

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

查找

a，大于根節點向右找，小于向左找。
b，最多查找高度次，若走到空了，說沒沒有這個數。

bool find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}return false;

插入

a, 若樹是空=
=，新增節點，將節點賦值給_root;
b, 若樹不為空，按二叉搜索樹性質==找到插入位置，插入
在這里插入圖片描述
代碼實現

bool 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){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(key);if (cur->_key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

刪除

刪除要分4種情況：
a，刪除節點無左右子樹
b，刪除節點只有左子樹
c，刪除節點只有右子樹
d，刪除節點左右子樹都有

實際情況中，a可以和b/c結合起來，因此情況有三種

b：讓父親節點指向左子樹（兩種情況，要刪除的節點是父親的左節點還是右節點），刪除節點
c：讓父親節點指向右子樹，刪除節點
d：找到左子樹最大節點，與根節點值替換（?因為最大，所以該節點無左子樹，或只能有左子樹）再按照b方法處理，刪除替換的節點。 //////////////或者找右子樹最小節點，再按照c方法處理，刪除替換節點。

代碼實現：

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key == key)break;else if (cur->_key < key){parent = cur;cur = cur->_right;}else{parent = cur;cur = cur->_left;}}if (cur == nullptr)return false;//左空 a情況的左右子樹都空也進入這里if (cur->_left == nullptr){if (cur == _root)_root = cur->_right;else{if (parent->_left == cur){parent->_left = cur->_right;}elseparent->_right = cur->_right;}}//右空else if (cur->_right == nullptr){if (cur == _root)_root = cur->_left;else{if (parent->_left == cur){parent->_left = cur->_left;}elseparent->_right = cur->_left;}}else //替換{parent = cur;Node* leftmax = cur->_left;while (leftmax->_right){parent = leftmax;leftmax = leftmax->_right;}swap(cur->_key, leftmax->_key);if (parent->_left == leftmax){parent->_left = leftmax->_left;}elseparent->_right = leftmax->_left;cur = leftmax;}delete cur;return true;return false;
}```c
template<class K>
class BSTree
{typedef TreeNode<K> Node;
public:BSTree():_root(nullptr){}
void Inorder()
{_Inorder(_root);
}
void _Inorder(Node* cur)
{if (cur == nullptr)return;_Inorder(cur->_left);cout << cur->_key << " ";_Inorder(cur->_right);
}
private:Node* _root;
};

AVL樹

概念

雖然二叉搜索樹加快了查找效率，但是如果數據接近順序，那么二叉樹就退化成單側樹了，查找元素就相當于在順序表查找，效率低下，所以發明了AVL樹，
在這里插入圖片描述
AVL樹：是空樹或滿足以下性質的二叉搜索樹
?1，左右樹都是二叉搜索樹
?2，左右子樹高度之差（簡稱平衡因子）絕對值不超過1，

搜索時間復雜度log2n
AVL節點代碼:

struct AVLTreeNode
{AVLTreeNode(const T& date = T()):_left(nullptr),_right(nullptr),_parent(nullptr),_date(date),_bf(0){}AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;T _date;int _bf;
};

插入

AVL樹插入分兩步
1，按二叉搜索樹性質插入節點，
2，調整平衡因子

插入新節點，那父節點平衡因子一定要調整，如果插在父節點左子樹，則父節點平衡–，反之++
接下來會有三種情況：
a，如果父節點平衡因子=0，說明平衡了，不用再調整了
b，如果父節點等于±1，說明還需要向上調整，祖父節點的平衡因子也要調整
c，如果父節點平衡因子等于±2，說明不平衡了，需要旋轉。

旋轉

旋轉分4種
1，如果新節點插在較高左子樹左側：左左，右單旋
在這里插入圖片描述
2，如果新節點插在較高右子樹右側：右右，左單旋

3，如果新節點插在較高左子樹右側：左右，先左單旋再右單旋

旋轉后考慮平衡因子更新，據圖得知90父節點為1，30子節點為0

如果新插入節點是60，則父子為0，
根據新插入節點左右子樹不同，平衡因子更新不同

4，如果新節點插在較高右子樹左側：右左，先右單旋再左單旋
在這里插入圖片描述

參考左右單旋

總結：

當父節點等于2時，

若子節點=1，則左單旋
若子節點=-1，則右單旋再單旋

當父節點等于-2

若字節點=-1，則右單旋
若子節點=1，則左右單旋

代碼實現：

template<class T>
class AVLTree
{typedef AVLTreeNode<T> Node;
public:AVLTree():_root(nullptr){}bool Insert(const T& date){if (nullptr == _root){_root = new Node(date);return true;}Node* pCur = _root;Node* pParent = nullptr;while (pCur){if (pCur->_date < date){pParent = pCur;pCur = pCur->_right;}else if (pCur->_date > date){pParent = pCur;pCur = pCur->_left;}else{return false;}}pCur = new Node(date);if (pParent->_date > date){pParent->_left = pCur;}else if (pParent->_date < date){pParent->_right = pCur;}pCur->_parent = pParent;while (pParent){if (pParent->_left == pCur){pParent->_bf--;}elsepParent->_bf++;if (pParent->_bf == 0)break;else if (pParent->_bf == -1 || pParent->_bf == 1){pCur = pParent;pParent = pParent->_parent;}else if (pParent->_bf == 2 || pParent->_bf == -2){if (pParent->_bf == 2 && pCur->_bf == 1){RotateL(pParent);}else if (pParent->_bf == -2 && pCur->_bf == -1){RotateR(pParent);}else if (pParent->_bf == 2 && pCur->_bf == -1){RotateRL(pParent);}else if (pParent->_bf == -2 && pCur->_bf == 1){RotateLR(pParent);}elsereturn false;}}return true;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* pnode = parent->_parent;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pnode->_right == parent){pnode->_right = cur;}elsepnode->_left = cur;cur->_parent = pnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* pnode = parent->_parent;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pnode->_right == parent){pnode->_right = cur;}elsepnode->_left = cur;cur->_parent = pnode;}cur->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(cur);RotateL(parent);if (bf == 0){cur->_bf = parent->_bf = curleft->_bf = 0;}else if (bf == 1){parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}elseassert(false);}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0){cur->_bf = parent->_bf = curright->_bf = 0;}else if (bf == 1){cur->_bf = -1;parent->_bf = 0;curright->_bf = 0;}else if (bf == -1){cur->_bf = 1;curright->_bf = 0;parent->_bf = 0;}elseassert(false);}void Inorder(Node* root){if (root == nullptr){return;}Inorder(root->_left);cout << root->_date;Inorder(root->_right);}void Inorder(){Inorder(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool IsBalance(Node* root){if (root == nullptr)return true;int left = Height(root->_left);int right = Height(root->_right);if (right - left != root->_bf){std::cout << "平衡因子錯誤" << root->_bf << std::endl;}return abs(left - right) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}private:Node* _root;
};

AVL驗證

1，中序遍歷，如果是升序則說明是二叉平衡樹

2，判斷左右子樹高度差不超過1，確認平衡性

紅黑樹

概念

AVL樹限制比較大，旋轉次數多，所以發明了紅黑樹。
紅黑樹：一種二叉搜索樹，每個節點加了顏色限制紅或黑，通過對每一條路徑顏色限制，確保紅黑樹最短路徑不會超過最短路徑的兩倍，因而平衡。

?紅黑樹性質：
1，根節點必須是黑色的
2，每個節點不是黑色的就是紅色的
3，每一條路徑黑色節點數相同
4，如果一個節點是紅色的，那么兩個孩子都是黑色的（不能出現連續的紅色）
5，葉子節點是黑色的（此處葉子節點是空）
在這里插入圖片描述

插入

💪如果樹是空的，說明插入的是根節點，直接設置為黑，
否則來的節點就設置為紅節點，因為每條路徑黑節點數相同，如果新來的變為黑，那么整個樹都要做調整
如果插入的紅節點父親是黑節點，那么無事發生，但如果父節點也是紅，那就違反紅黑樹性質（紅節點的孩子必須是黑節點），需要調整，接下來分兩種情況分析
💪1，孩子的叔叔(與父節點相對的另一支)存在且為紅，則把叔叔和父親都設為黑，祖父設為紅（依舊保持黑節點數不變），祖父設為紅了，還要檢查祖父的父親是否為紅，繼續向上調整，
在這里插入圖片描述
💪2，叔叔節點不存在/存在且為黑，旋轉，旋轉又分兩種情況，單旋和雙旋

旋轉之后父節點為黑，祖父為紅
代碼實現：

bool insert(const pair<key,value>& kv){if (_root == nullptr){_root = new Node(kv);_root->_col = BLACK;return true;}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;}elsereturn false;}cur = new Node(kv);cur->_col = RED;if (parent->_kv.first <cur->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;while (parent&&parent->_col==RED){Node* grandparent = parent->_parent;if(grandparent->_left==parent){Node* uncle = grandparent->_right;//uncle存在且為紅if (uncle && uncle->_col==RED){parent->_col = uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else//uncle不存在或存在且為黑{if (parent->_left == cur){//g//p//cRotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else if (parent->_right == cur){//g//p//cRotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}	}else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){uncle->_col = parent->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandparent);grandparent->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}//把根設為黑_root->_col = BLACK;return true;}void RotateL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;Node* pnode = parent->_parent;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pnode->_right == parent){pnode->_right = cur;}elsepnode->_left = cur;cur->_parent = pnode;}parent->_bf = cur->_bf = 0;
}
void RotateR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;Node* pnode = parent->_parent;parent->_left = curright;if (curright){curright->_parent = parent;}cur->_right = parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (pnode->_right == parent){pnode->_right = cur;}elsepnode->_left = cur;cur->_parent = pnode;}
}

檢測

檢測是否為二叉樹分兩步
1，中序遍歷是否是升序
2，是否滿足紅黑樹性質

bool checkcolour(Node* root, int blacknum, int benchblack){//黑節點數目不一樣錯誤if (root == nullptr){if (blacknum != benchblack)return false;return true;}//遇到黑++if (root->_col == BLACK){++blacknum;}//是否連續紅節點if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "flase" << root->_kv.first;return false;}return checkcolour(root->_left,blacknum,benchblack) && checkcolour(root->_right,blacknum,benchblack);}bool isbalance(){return isbalance(_root);}bool isbalance(Node* root){//空樹正確//根不黑直接錯誤if (root == nullptr)return true;if (root->_col != BLACK)return false;Node* cur = root;int benchblack = 0;while (cur){//確定一條路上的黑節點if (cur->_col == BLACK)++benchblack;cur = cur->_left;			}return checkcolour(root,0,benchblack);}