AVLtree（C++实现）有统一的旋转操作

/*
* BinarySearchTree.h
* 1. 添加元素时需自己做判断元素是否合法
* 2. 除层序遍历外，本源代码均采用递归遍历，若要减少栈的消耗，应该实现迭代遍历
* 3. 本代码实现的AVL树有统一旋转操作，不用分情况讨论LL,LR,RR,RL来进行树的平衡
* 统一旋转操作有特殊优化版本和统一接口版本，本代码保留了统一接口的源码，但是采用的是特殊优化版本
* 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)); //比较函数指针 virtual ~BinarySearchTree(); int size(); //元素的数量 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; //停止标志，若stop为true，则停止遍历
preorderTraversal(root_, stop, visitor);
} void inorderTraversal(bool (*visitor)(Element e)) {
//中序遍历
if (visitor == nullptr)
return;
bool stop = false; //停止标志，若stop为true，则停止遍历
inorderTraversal(root_, stop, visitor);
} void postorderTraversal(bool (*visitor)(Element e)) {
//后序遍历
if (visitor == nullptr)
return;
bool stop = false; //停止标志，若stop为true，则停止遍历
postorderTraversal(root_, stop, visitor);
} void levelOrderTraversal(bool (*visitor)(Element e)) {
//层序遍历，迭代实现
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; //节点的高度
_Node(Element e_, _Node *parent_) :
e(e_), parent(parent_), left(nullptr), right(nullptr), height() {
//节点构造函数
} inline bool isLeaf() {
return (left == nullptr && right == nullptr);
} inline bool hasTwoChildren() {
return (left != nullptr && right != nullptr);
} inline int balanceFactor() {
//获得节点的平衡因子
int leftHeight = left == nullptr ? : left->height; //获得左子树的高度
int rightHeight = right == nullptr ? : right->height; //获得右子树的高度
return leftHeight - rightHeight;
} inline bool isBalanced() {
//判断node是否平衡
int balanceFactor_ = balanceFactor();
return balanceFactor_ >= - && balanceFactor_ <= ; //平衡因子为-1,0,1则返回true
} inline void updateHeight() {
//更新节点的高度
int leftHeight = left == nullptr ? : left->height; //获得左子树的高度
int rightHeight = right == nullptr ? : right->height; //获得右子树的高度
height = + (leftHeight > rightHeight ? leftHeight : rightHeight); //把节点高度更新为左右子树最大的高度+1
} inline bool isLeftChild() {
//判断节点是否是父亲节点的左子结点
return parent != nullptr && parent->left == this;
} inline bool isRightChild() {
//判断节点是否是父亲节点的右子结点
return parent != nullptr && parent->right == this;
} inline _Node* tallerChild() {
//获得高度更高的子树
int leftHeight = left == nullptr ? : left->height; //获得左子树的高度
int rightHeight = right == nullptr ? : 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); //为实现树的排序的个性化配置，私有成员保存一个比较函数指针 NODE* Node(Element e, int (*cmp_)(Element e1, Element e2)) {
//返回e元素所在的节点
NODE *node = root_;
while (node != nullptr) {
int cmp = cmp_(e, node->e);
if (cmp == ) //找到了元素
return node;
if (cmp > ) { //待寻找元素大于节点存储的元素
node = node->right;
} else { //待寻找元素小于节点存储的元素
node = node->left;
}
}
return nullptr;
} NODE* predecessor(NODE *node) {
//返回node的前驱节点
if (node == nullptr)
return nullptr;
//前驱节点在左子树
NODE *tmp = node->left;
if (tmp != nullptr) {
while (tmp->right != nullptr)
tmp = tmp->right;
return tmp;
}
//从父节点，祖父节点中寻找前驱节点
while (node->parent != nullptr && node == node->parent->left) {
node = node->parent;
}
return node->parent;
} NODE* successor(NODE *node) {
//返回node的后继节点
if (node == nullptr)
return nullptr;
//后继节点在右子树
NODE *tmp = node->right;
if (tmp != nullptr) {
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
//从父节点，祖父节点中寻找后继节点
while (node->parent != nullptr && node == node->parent->right) {
node = node->parent;
}
return node->parent;
}#if 0
//统一接口版本(未优化)
void rotate(NODE *r, NODE *a, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f,
NODE *g) {
//统一的旋转操作
/* r是变换前高度最低的不平衡节点
* 传入的参数a,b,c,d,e,f,g是经过变换后节点应该在的位置
* d
* / \
* b f
* / \ / \
* a c e g
* a,c,e,g均有可能为空，所以要对它们做判空处理
* b,d,f绝不为空
* d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向
*/
//对d节点做处理
d->parent = r->parent;
if (r->isLeftChild())
r->parent->left = d;
else if (r->isRightChild())
r->parent->right = d;
else
root_ = d;
//a-b-c
b->left = a;
b->right = c;
if (a != nullptr)
a->parent = b;
if (c != nullptr)
c->parent = b;
b->updateHeight();
//e-f-g
f->left = e;
f->right = g;
if (e != nullptr)
e->parent = f;
if (g != nullptr)
g->parent = f;
f->updateHeight();
//b-d-f
d->left = b;
d->right = f;
b->parent = d;
f->parent = d;
d->updateHeight();
} void rebalance(NODE *gNode) {
//恢复平衡,grand为高度最低的不平衡节点
NODE *pNode = gNode->tallerChild();
NODE *nNode = pNode->tallerChild();
if (pNode->isLeftChild()) {
if (nNode->isLeftChild()) {
//LL
/*
* gNode(f)
* / \ 变换后
* pNode(d) g ====> pNode(d)
* / \ / \
* nNode(b) e nNode(b) gNode(f)
* / \ / \ / \
* a c a c e g
*/
rotate(gNode, nNode->left, nNode, nNode->right, pNode,
pNode->right, gNode, gNode->right);
} else {
//LR
/*
* gNode(f)
* / \ 变换后
* pNode(b) g ====> nNode(d)
* / \ / \
* a nNode(d) pNode(b) gNode(f)
* / \ / \ / \
* c e a c e g
*/
rotate(gNode, pNode->left, pNode, nNode->left, nNode,
nNode->right, gNode, gNode->right);
}
} else {
if (nNode->isLeftChild()) {
//RL
/*
* gNode(b)
* / \ 变换后
* a pNode(f) ====> nNode(d)
* / \ / \
* nNode(d) g gNode(b) pNode(f)
* / \ / \ / \
* c e a c e g
*/
rotate(gNode, gNode->left, gNode, nNode->left, nNode,
nNode->right, pNode, pNode->right);
} else {
//RR
/*
* gNode(b)
* / \ 变换后
* a pNode(d) ====> pNode(d)
* / \ / \
* c nNode(f) gNode(b) nNode(f)
* / \ / \ / \
* e g a c e g
*/
rotate(gNode, gNode->left, gNode, pNode->left, pNode,
nNode->left, nNode, nNode->right);
}
}
}#endif void rotate(NODE *r, NODE *b, NODE *c, NODE *d, NODE *e, NODE *f) {
//统一的旋转操作
/* r是变换前高度最低的不平衡节点
* 传入的参数b,c,d,e,f是经过变换后节点应该在的位置
* d
* / \
* b f
* / \ / \
* a c e g
* c,e均有可能为空，所以要对它们做判空处理
* b,d,f绝不为空
* d的parent可能为null，则d就为根节点，所以就要改变树中root_的指向
*/
//对d节点做处理
d->parent = r->parent;
if (r->isLeftChild())
r->parent->left = d;
else if (r->isRightChild())
r->parent->right = d;
else
root_ = d;
//b-c
b->right = c;
if (c != nullptr)
c->parent = b;
b->updateHeight();
//e-f
f->left = e;
if (e != nullptr)
e->parent = f;
f->updateHeight();
//b-d-f
d->left = b;
d->right = f;
b->parent = d;
f->parent = d;
d->updateHeight();
} void rebalance(NODE *gNode) {
//恢复平衡,grand为高度最低的不平衡节点
NODE *pNode = gNode->tallerChild();
NODE *nNode = pNode->tallerChild();
if (pNode->isLeftChild()) {
if (nNode->isLeftChild()) {
//LL
/*
* gNode(f)
* / \ 变换后
* pNode(d) g ====> pNode(d)
* / \ / \
* nNode(b) e nNode(b) gNode(f)
* / \ / \ / \
* a c a c e g
*/
rotate(gNode, nNode, nNode->right, pNode, pNode->right, gNode);
} else {
//LR
/*
* gNode(f)
* / \ 变换后
* pNode(b) g ====> nNode(d)
* / \ / \
* a nNode(d) pNode(b) gNode(f)
* / \ / \ / \
* c e a c e g
*/
rotate(gNode, pNode, nNode->left, nNode, nNode->right, gNode);
}
} else {
if (nNode->isLeftChild()) {
//RL
/*
* gNode(b)
* / \ 变换后
* a pNode(f) ====> nNode(d)
* / \ / \
* nNode(d) g gNode(b) pNode(f)
* / \ / \ / \
* c e a c e g
*/
rotate(gNode, gNode, nNode->left, nNode, nNode->right, pNode);
} else {
//RR
/*
* gNode(b)
* / \ 变换后
* a pNode(d) ====> pNode(d)
* / \ / \
* c nNode(f) gNode(b) nNode(f)
* / \ / \ / \
* e g a c e g
*/
rotate(gNode, gNode, pNode->left, pNode, nNode->left, nNode);
}
}
} void afterAdd(NODE *node) {
//添加node之后的调整
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
//如果节点平衡，则对其更新高度
node->updateHeight();
} else {
//此时对第一个不平衡节点操作，使其平衡
rebalance(node);
//整棵树恢复平衡后,跳出循环
break;
}
node = node->parent;
}
} void add(Element e, int (*cmp_)(Element e1, Element e2)) {
//当树为空时，添加的节点作为树的根节点
if (root_ == nullptr) {
root_ = new NODE(e, nullptr);
size_++;
//插入一个根节点之后进行调整
afterAdd(root_);
return;
}
//当添加的节点不是第一个节点
NODE *parent = root_;
NODE *node = root_;
int cmp = ; //比较结果
while (node != nullptr) {
parent = node; //保存父节点
cmp = cmp_(e, node->e); //由函数指针来比较
if (cmp > ) {
node = node->right; //添加的元素大于节点中的元素
} else if (cmp < ) {
node = node->left; //添加的元素小于节点中的元素
} else {
node->e = e; //相等时就覆盖
return; //添加的元素等于节点中的元素,直接返回
}
}
//判断要插入父节点的哪个位置
NODE *newNode = new NODE(e, parent); //为新元素创建节点
if (cmp > ) {
parent->right = newNode; //添加的元素大于节点中的元素
} else {
parent->left = newNode; //添加的元素小于节点中的元素
}
size_++;
//添加一个新节点之后进行调整
afterAdd(newNode);
} void afterRemove(NODE *node) {
//删除node之后的调整
if (node == nullptr)
return;
node = node->parent;
while (node != nullptr) {
if (node->isBalanced()) {
//如果节点平衡，则对其更新高度
node->updateHeight();
} else {
//此时对不平衡节点操作，使其平衡
rebalance(node);
}
node = node->parent;
}
} void remove(NODE *node_) {
//删除某一节点
if (node_ == nullptr)
return;
size_--;
//优先删除度为2的节点
if (node_->hasTwoChildren()) {
NODE *pre = successor(node_); //找到node_的后继节点
node_->e = pre->e; //用后继节点的值覆盖度为2的节点的值
//删除后继节点(后继节点的度只能为1或0)
node_ = pre;
}
//此时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的根节点
root_ = replacement;
else if (node_->parent->left == node_)
node_->parent->left = replacement;
else
node_->parent->right = replacement;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
delete node_;
} else if (node_->parent == nullptr) { //node_是叶子节点，也是根节点
root_ = nullptr;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
delete node_;
} else { //node_是叶子节点，但不是根节点
if (node_->parent->left == node_)
node_->parent->left = nullptr;
else
node_->parent->right = nullptr;
//所有删除操作准备完成，准备释放节点内存前进行平衡操作
afterRemove(node_);
delete node_;
}
} void preorderTraversal(NODE *node, bool &stop, bool (*visitor)(Element e)) {
//递归实现前序遍历
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)) {
//递归实现中序遍历
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)) {
//递归实现后序遍历
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) {
//某一节点的高度
return node->height;
} bool isComplete(NODE *node) {
if (node == nullptr)
return false;
using namespace std;
queue<NODE*> q;
q.push(node);
bool leaf = false; //判断接下来的节点是否为叶子节点
while (!q.empty()) {
NODE *node = q.front();
if (leaf && !node->isLeaf()) //判断叶子节点
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_(), root_(nullptr), cmp_(cmp) {
//树的构造函数
}template<typename Element>
BinarySearchTree<Element>::~BinarySearchTree() {
// 析构函数
clear();
}template<typename Element>
inline int BinarySearchTree<Element>::size() {
//返回元素个数
return size_;
}template<typename Element>
inline bool BinarySearchTree<Element>::isEmpty() {
//判断是否为空树
return size_ == ;
}#endif /* SRC_BINARYSEARCHTREE_H_ */

/*
* 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) {
//比较函数,相同返回0,e1<e2返回-1,e1>e2返回1
return e1 == e2 ? : (e1 < e2 ? - : );
}template<typename Elemnet>
bool visitor(Elemnet e) {
cout << e << " ";
cout << endl;
return false; //若返回true，则在遍历时会退出
}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);
clock_t start = clock();
for (int i = ; i < ; i++) {
a.add(i);
}
for (int i = ; i < ; 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;
}