關(guān)于AVLTree（C++實(shí)現(xiàn)）沒(méi)有統(tǒng)一旋轉(zhuǎn)操作的問(wèn)題
更新時(shí)間：2020年02月06日 14:46:32 作者：路璐
這篇文章主要介紹了關(guān)于AVLTree（C++實(shí)現(xiàn)）沒(méi)有統(tǒng)一旋轉(zhuǎn)操作的問(wèn)題,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
最近疫情比較嚴(yán)重，只能在家里休息，利用休息之余，我用C++把AVL樹實(shí)現(xiàn)了一遍
大學(xué)老師只講一些比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)和算法，這些高級(jí)數(shù)據(jù)結(jié)構(gòu)還是需要自己主動(dòng)學(xué)習(xí)并且動(dòng)手來(lái)實(shí)現(xiàn)的，
從前只聽說(shuō)過(guò)AVLTree，我從看書了解原理到把它一點(diǎn)一點(diǎn)寫出來(lái)最后在調(diào)試一共花了大概3天的時(shí)間。應(yīng)該已經(jīng)算很長(zhǎng)時(shí)間了。
一般情況下AVL樹是不用我么自己寫的，但是為了有一份已經(jīng)實(shí)現(xiàn)的代碼作為我以后再來(lái)回顧算法實(shí)現(xiàn)的依照，我還是決定對(duì)自己狠一些把它實(shí)現(xiàn)了一遍
以下代碼均采用C++11 標(biāo)準(zhǔn)
在ubuntu 18.04上經(jīng)過(guò)編譯和調(diào)試
/*
* BinarySearchTree.h
* 1. 添加元素時(shí)需自己做判斷元素是否合法
* 2. 除層序遍歷外，本源代碼均采用遞歸遍歷，若要減少棧的消耗，應(yīng)該實(shí)現(xiàn)遞歸遍歷
* 3. 本代碼實(shí)現(xiàn)的AVL樹沒(méi)有統(tǒng)一旋轉(zhuǎn)操作，采用分情況討論LL,LR,RR,RL來(lái)進(jìn)行樹的平衡
* Created on: 2020年1月29日
* Author: LuYonglei
*/
#ifndef SRC_BINARYSEARCHTREE_H_
#define SRC_BINARYSEARCHTREE_H_
#include <queue>
template<typename Element>
class BinarySearchTree {
public:
BinarySearchTree(int (*cmp)(Element e1, Element e2)); //比較函數(shù)指針
virtual ~BinarySearchTree();
int size(); //元素的數(shù)量
bool isEmpty(); //是否為空
void clear() {
//清空所有元素
NODE *node = root_;
root_ = nullptr;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *tmp = q.front();
if (tmp->left != nullptr)
q.push(tmp->left);
if (tmp->right != nullptr)
q.push(tmp->right);
delete tmp;
q.pop();
}
}
void add(Element e) {
//添加元素
add(e, cmp_);
}
void remove(Element e) {
//刪除元素
remove(Node(e, cmp_));
}
bool contains(Element e) {
//是否包含某元素
return Node(e, cmp_) != nullptr;
}
void preorderTraversal(bool (*visitor)(Element &e)) {
//前序遍歷
if (visitor == nullptr)
return;
bool stop = false; //停止標(biāo)志，若stop為true，則停止遍歷
preorderTraversal(root_, stop, visitor);
}
void inorderTraversal(bool (*visitor)(Element &e)) {
//中序遍歷
if (visitor == nullptr)
return;
bool stop = false; //停止標(biāo)志，若stop為true，則停止遍歷
inorderTraversal(root_, stop, visitor);
}
void postorderTraversal(bool (*visitor)(Element &e)) {
//后序遍歷
if (visitor == nullptr)
return;
bool stop = false; //停止標(biāo)志，若stop為true，則停止遍歷
postorderTraversal(root_, stop, visitor);
}
void levelOrderTraversal(bool (*visitor)(Element &e)) {
//層序遍歷，迭代實(shí)現(xiàn)
if (visitor == nullptr)
return;
levelOrderTraversal(root_, visitor);
}
int height() {
//樹的高度
return height(root_);
}
bool isComplete() {
//判斷是否是完全二叉樹
return isComplete(root_);
}
private:
int size_;
typedef struct _Node {
Element e;
_Node *parent;
_Node *left;
_Node *right;
int height; //節(jié)點(diǎn)的高度
_Node(Element e_, _Node *parent_) :
e(e_), parent(parent_), left(nullptr), right(nullptr), height(1) {
//節(jié)點(diǎn)構(gòu)造函數(shù)
}
inline bool isLeaf() {
return (left == nullptr && right == nullptr);
}
inline bool hasTwoChildren() {
return (left != nullptr && right != nullptr);
}
inline int balanceFactor() {
//獲得節(jié)點(diǎn)的平衡因子
int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度
int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度
return leftHeight - rightHeight;
}
inline bool isBalanced() {
//判斷node是否平衡
int balanceFactor_ = balanceFactor();
return balanceFactor_ >= -1 && balanceFactor_ <= 1; //平衡因子為-1,0,1則返回true
}
inline void updateHeight() {
//更新節(jié)點(diǎn)的高度
int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度
int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度
height = 1 + (leftHeight > rightHeight ? leftHeight : rightHeight); //把節(jié)點(diǎn)高度更新為左右子樹最大的高度+1
}
inline bool isLeftChild() {
//判斷節(jié)點(diǎn)是否是父親節(jié)點(diǎn)的左子結(jié)點(diǎn)
return parent != nullptr && parent->left == this;
}
inline bool isRightChild() {
//判斷節(jié)點(diǎn)是否是父親節(jié)點(diǎn)的右子結(jié)點(diǎn)
return parent != nullptr && parent->right == this;
}
inline _Node* tallerChild() {
//獲得高度更高的子樹
int leftHeight = left == nullptr ? 0 : left->height; //獲得左子樹的高度
int rightHeight = right == nullptr ? 0 : right->height; //獲得右子樹的高度
if (leftHeight > rightHeight)
return left;
if (leftHeight < rightHeight)
return right;
return isLeftChild() ? left : right;
}
} NODE;
NODE *root_;
int (*cmp_)(Element e1, Element e2); //為實(shí)現(xiàn)樹的排序的個(gè)性化配置，私有成員保存一個(gè)比較函數(shù)指針
NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
//返回e元素所在的節(jié)點(diǎn)
NODE *node = root_;
while (node != nullptr) {
int cmp = cmp_(e, node->e);
if (cmp == 0) //找到了元素
return node;
if (cmp > 0) { //待尋找元素大于節(jié)點(diǎn)存儲(chǔ)的元素
node = node->right;
} else { //待尋找元素小于節(jié)點(diǎn)存儲(chǔ)的元素
node = node->left;
}
}
return nullptr;
}
NODE* predecessor(NODE *node) {
//返回node的前驅(qū)節(jié)點(diǎn)
if (node == nullptr)
return nullptr;
//前驅(qū)節(jié)點(diǎn)在左子樹
NODE *tmp = node->left;
if (tmp != nullptr) {
while (tmp->right != nullptr)
tmp = tmp->right;
return tmp;
}
//從父節(jié)點(diǎn)，祖父節(jié)點(diǎn)中尋找前驅(qū)節(jié)點(diǎn)
while (node->parent != nullptr && node == node->parent->left) {
node = node->parent;
}
return node->parent;
}
NODE* successor(NODE *node) {
//返回node的后繼節(jié)點(diǎn)
if (node == nullptr)
return nullptr;
//后繼節(jié)點(diǎn)在右子樹
NODE *tmp = node->right;
if (tmp != nullptr) {
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
//從父節(jié)點(diǎn)，祖父節(jié)點(diǎn)中尋找后繼節(jié)點(diǎn)
while (node->parent != nullptr && node == node->parent->right) {
node = node->parent;
}
return node->parent;
}
void afterRotate(NODE *gNode, NODE *pNode, NODE *child) {
//在左旋轉(zhuǎn)與右旋轉(zhuǎn)中統(tǒng)一調(diào)用
pNode->parent = gNode->parent;
if (gNode->isLeftChild())
gNode->parent->left = pNode;
else if (gNode->isRightChild())
gNode->parent->right = pNode;
else
//此時(shí)gNode->parent 為nullptr，gNode為root節(jié)點(diǎn)
root_ = pNode;
if (child != nullptr)
child->parent = gNode;
gNode->parent = pNode;
//左右子樹發(fā)生變化，所以要更新高度
gNode->updateHeight();
pNode->updateHeight();
}
void rotateLeft(NODE *gNode) {
//對(duì)gNode進(jìn)行左旋轉(zhuǎn)
NODE *pNode = gNode->right;
NODE *child = pNode->left;
gNode->right = child;
pNode->left = gNode;
afterRotate(gNode, pNode, child);
}
void rotateRight(NODE *gNode) {
//對(duì)gNode進(jìn)行右旋轉(zhuǎn)
NODE *pNode = gNode->left;
NODE *child = pNode->right;
gNode->left = child;
pNode->right = gNode;
afterRotate(gNode, pNode, child);
}
void rebalance(NODE *gNode) {
//恢復(fù)平衡,grand為高度最低的不平衡節(jié)點(diǎn)
NODE *pNode = gNode->tallerChild();
NODE *nNode = pNode->tallerChild();
if (pNode->isLeftChild()) {
if (nNode->isLeftChild()) {
//LL
/*
* gNode
* / 對(duì)gNode右旋
* pNode ====> pNode
* / / \
* nNode nNode gNode
*/
rotateRight(gNode);
} else {
//LR
/*
* gNode gNode
* / 對(duì)pNode左旋 / 對(duì)gNode右旋
* pNode ====> nNode ====> nNode
* \ / / \
* nNode pNode pNode gNode
*/
rotateLeft(pNode);
rotateRight(gNode);
}
} else {
if (nNode->isLeftChild()) {
//RL
/*
* gNode gNode
* \ 對(duì)pNode右旋 \ 對(duì)gNode左旋
* pNode ====> nNode ====> nNode
* / \ / \
* nNode pNode gNode pNode
*/
rotateRight(pNode);
rotateLeft(gNode);
} else {
//RR
/*
* gNode
* \ 對(duì)gNode左旋
* pNode ====> pNode
* \ / \
* nNode gNode nNode
*/
rotateLeft(gNode);
}
}
}
void afterAdd(NODE *node) {
//添加node之后的調(diào)整
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
//如果節(jié)點(diǎn)平衡，則對(duì)其更新高度
node->updateHeight();
} else {
//此時(shí)對(duì)第一個(gè)不平衡節(jié)點(diǎn)操作，使其平衡
rebalance(node);
//整棵樹恢復(fù)平衡后,跳出循環(huán)
break;
}
node = node->parent;
}
}
void add(Element e, int (*cmp_)(Element e1, Element e2)) {
//當(dāng)樹為空時(shí)，添加的節(jié)點(diǎn)作為樹的根節(jié)點(diǎn)
if (root_ == nullptr) {
root_ = new NODE(e, nullptr);
size_++;
//插入一個(gè)根節(jié)點(diǎn)之后進(jìn)行調(diào)整
afterAdd(root_);
return;
}
//當(dāng)添加的節(jié)點(diǎn)不是第一個(gè)節(jié)點(diǎn)
NODE *parent = root_;
NODE *node = root_;
int cmp = 0; //比較結(jié)果
while (node != nullptr) {
parent = node; //保存父節(jié)點(diǎn)
cmp = cmp_(e, node->e); //由函數(shù)指針來(lái)比較
if (cmp > 0) {
node = node->right; //添加的元素大于節(jié)點(diǎn)中的元素
} else if (cmp < 0) {
node = node->left; //添加的元素小于節(jié)點(diǎn)中的元素
} else {
node->e = e; //相等時(shí)就覆蓋
return; //添加的元素等于節(jié)點(diǎn)中的元素,直接返回
}
}
//判斷要插入父節(jié)點(diǎn)的哪個(gè)位置
NODE *newNode = new NODE(e, parent); //為新元素創(chuàng)建節(jié)點(diǎn)
if (cmp > 0) {
parent->right = newNode; //添加的元素大于節(jié)點(diǎn)中的元素
} else {
parent->left = newNode; //添加的元素小于節(jié)點(diǎn)中的元素
}
size_++;
//添加一個(gè)新節(jié)點(diǎn)之后進(jìn)行調(diào)整
afterAdd(newNode);
}
void afterRemove(NODE *node) {
//刪除node之后的調(diào)整
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
//如果節(jié)點(diǎn)平衡，則對(duì)其更新高度
node->updateHeight();
} else {
//此時(shí)對(duì)不平衡節(jié)點(diǎn)操作，使其平衡
rebalance(node);
}
node = node->parent;
}
}
void remove(NODE *node_) {
//刪除某一節(jié)點(diǎn)
if (node_ == nullptr)
return;
size_--;
//優(yōu)先刪除度為2的節(jié)點(diǎn)
if (node_->hasTwoChildren()) {
NODE *pre = successor(node_); //找到node_的后繼節(jié)點(diǎn)
node_->e = pre->e; //用后繼節(jié)點(diǎn)的值覆蓋度為2的節(jié)點(diǎn)的值
//刪除后繼節(jié)點(diǎn)(后繼節(jié)點(diǎn)的度只能為1或0)
node_ = pre;
}
//此時(shí)node_的度必然為0或1
NODE *replacement = node_->left != nullptr ? node_->left : node_->right;
if (replacement != nullptr) { //node_的度為1
replacement->parent = node_->parent;
if (node_->parent == nullptr) //度為1的根節(jié)點(diǎn)
root_ = replacement;
else if (node_->parent->left == node_)
node_->parent->left = replacement;
else
node_->parent->right = replacement;
//所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作
afterRemove(node_);
delete node_;
} else if (node_->parent == nullptr) { //node_是葉子節(jié)點(diǎn)，也是根節(jié)點(diǎn)
root_ = nullptr;
//所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作
afterRemove(node_);
delete node_;
} else { //node_是葉子節(jié)點(diǎn)，但不是根節(jié)點(diǎn)
if (node_->parent->left == node_)
node_->parent->left = nullptr;
else
node_->parent->right = nullptr;
//所有刪除操作準(zhǔn)備完成，準(zhǔn)備釋放節(jié)點(diǎn)內(nèi)存前進(jìn)行平衡操作
afterRemove(node_);
delete node_;
}
}
void preorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
//遞歸實(shí)現(xiàn)前序遍歷
if (node == nullptr || stop == true)
return;
stop = visitor(node->e);
preorderTraversal(node->left, stop, visitor);
preorderTraversal(node->right, stop, visitor);
}
void inorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element &e)) {
//遞歸實(shí)現(xiàn)中序遍歷
if (node == nullptr || stop == true)
return;
inorderTraversal(node->left, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
inorderTraversal(node->right, stop, visitor);
}
void postorderTraversal(NODE *node, bool &stop,
bool (*visitor)(Element &e)) {
//遞歸實(shí)現(xiàn)后序遍歷
if (node == nullptr || stop == true)
return;
postorderTraversal(node->left, stop, visitor);
postorderTraversal(node->right, stop, visitor);
if (stop == true)
return;
stop = visitor(node->e);
}
void levelOrderTraversal(NODE *node, bool (*visitor)(Element &e)) {
if (node == nullptr)
return;
using namespace std;
queue<NODE*> q;
q.push(node);
while (!q.empty()) {
NODE *node = q.front();
if (visitor(node->e) == true)
return;
if (node->left != nullptr)
q.push(node->left);
if (node->right != nullptr)
q.push(node->right);
q.pop();
}
}
int height(NODE *node) {
//某一節(jié)點(diǎn)的高度
return node->height;
}
bool isComplete(NODE *node) {
if (node == nullptr)
return false;
using namespace std;
queue<NODE*> q;
q.push(node);
bool leaf = false; //判斷接下來(lái)的節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)
while (!q.empty()) {
NODE *node = q.front();
if (leaf && !node->isLeaf()) //判斷葉子節(jié)點(diǎn)
return false;
if (node->left != nullptr) {
q.push(node->left);
} else if (node->right != nullptr) { //node->left == nullptr && node->right != nullptr
return false;
}
if (node->right != nullptr) {
q.push(node->right);
} else { //node->right==nullptr
leaf = true;
}
q.pop();
}
return true;
}
};
template<typename Element>
BinarySearchTree<Element>::BinarySearchTree(int (*cmp)(Element e1, Element e2)) :
size_(0), root_(nullptr), cmp_(cmp) {
//樹的構(gòu)造函數(shù)
}
template<typename Element>
BinarySearchTree<Element>::~BinarySearchTree() {
// 析構(gòu)函數(shù)
clear();
}
template<typename Element>
inline int BinarySearchTree<Element>::size() {
//返回元素個(gè)數(shù)
return size_;
}
template<typename Element>
inline bool BinarySearchTree<Element>::isEmpty() {
//判斷是否為空樹
return size_ == 0;
}
#endif /* SRC_BINARYSEARCHTREE_H_ */
main方法
/*
* main.cpp
*
* Created on: 2020年1月29日
* Author: LuYonglei
*/
#include "BinarySearchTree.h"
#include <iostream>
#include <time.h>
using namespace std;
template<typename Element>
int compare(Element e1, Element e2) {
//比較函數(shù),相同返回0,e1<e2返回-1,e1>e2返回1
return e1 == e2 ? 0 : (e1 < e2 ? -1 : 1);
}
template<typename Elemnet>
bool visitor(Elemnet &e) {
cout << e << " ";
cout << endl;
return false; //若返回true，則在遍歷時(shí)會(huì)退出
}
int main(int argc, char **argv) {
BinarySearchTree<double> a(compare);
// a.add(85);
// a.add(19);
// a.add(69);
// a.add(3);
// a.add(7);
// a.add(99);
// a.add(95);
// a.add(2);
// a.add(1);
// a.add(70);
// a.add(44);
// a.add(58);
// a.add(11);
// a.add(21);
// a.add(14);
// a.add(93);
// a.add(57);
// a.add(4);
// a.add(56);
// a.remove(99);
// a.remove(85);
// a.remove(95);
clock_t start = clock();
for (int i = 0; i < 1000000; i++) {
a.add(i);
}
for (int i = 0; i < 1000000; i++) {
a.remove(i);
}
// a.inorderTraversal(visitor);
clock_t end = clock();
cout << end - start << endl;
// cout <<a.height()<< endl;
// cout << a.isComplete() << endl;
// a.remove(7);
// a.clear();
// a.levelOrderTraversal(visitor);
// cout << endl;
// cout<<a.contains(0)<<endl;
}
總結(jié)
以上所述是小編給大家介紹的關(guān)于AVLTree（C++實(shí)現(xiàn)）沒(méi)有統(tǒng)一旋轉(zhuǎn)操作的問(wèn)題，希望對(duì)大家有所幫助！
相關(guān)文章
這篇文章主要介紹了C++中move的使用及說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
這篇文章主要給大家介紹了關(guān)于C程序和C++程序之間互相調(diào)用的相關(guān)資料,我們平常在刷題的時(shí)候,難免遇到實(shí)現(xiàn)多組輸入這樣的問(wèn)題,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)掃雷、排雷小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
本篇文章是對(duì)memset()函數(shù)又進(jìn)行了深一步的了解，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言的變量和常量，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-04-04
CLion搭建配置C++開發(fā)環(huán)境的圖文教程 (MinGW-W64 GCC-8.1.0)
這篇文章主要介紹了CLion搭建配置C++開發(fā)環(huán)境的教程 (MinGW-W64 GCC-8.1.0),本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02
自C++17起就通過(guò)使用類模板參數(shù)推導(dǎo),只要編譯器能根據(jù)初始值推導(dǎo)出所有模板參數(shù),那么就可以不指明參數(shù),下面我們就來(lái)看看C++17中類模板參數(shù)推導(dǎo)的具體使用吧2024-03-03
這篇文章主要介紹了詳解C++編程中的私有繼承和公有繼承,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2015-09-09
使用WinExec命令打開指定程序或者文件的參數(shù)說(shuō)明2008-11-11
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱2022-11-11