//// AvlTree.h// HelloWorld// Created by feiyin001 on 17/1/9.// Copyright (c) 2017年 FableGame. All rights reserved.//#ifndef __HelloWorld__AvlTree__#define __HelloWorld__AvlTree__#include <iostream>namespace Fable{
int max(int a, int b) {
return a > b? a:b;
}
//二叉查找树，对于Comparable,必须实现了><=的比较 template<typename Comparable> class AvlTree {
public: //构造函数 AvlTree(){
}
//复制构造函数 AvlTree(const AvlTree& rhs) {
root = clone(rhs.root);
}
//析构函数 ~AvlTree() {
makeEmpty(root);
}
//复制赋值运算符 const AvlTree& operator=(const AvlTree& rhs) {
if (this != &rhs) {
makeEmpty(root);
//先清除 root = clone(rhs.root);
//再复制 }
return *this;
}
//查找最小的对象 const Comparable& findMin()const {
findMin(root);
}
//查找最大的对象 const Comparable& findMax()const {
findMax(root);
}
//是否包含了某个对象 bool contains(const Comparable& x)const {
return contains(x, root);
}
//树为空 bool isEmpty()const {
return root == nullptr;
}
//打印整棵树 void printTree()const {
printTree(root);
}
//清空树 void makeEmpty() {
makeEmpty(root);
}
//插入某个对象 void insert(const Comparable& x) {
insert(x, root);
}
//移除某个对象 void remove(const Comparable& x) {
remove(x, root);
}
private: struct AvlNode {
Comparable element;
AvlNode* left;
AvlNode* right;
int height;
AvlNode(const Comparable& theElement, AvlNode* lt, AvlNode* rt, int h = 0) :element(theElement), left(lt), right(rt), height(h){
}
}
;
typedef AvlNode* AvlNodePtr;
AvlNodePtr root;
//根结点 //顺时针旋转 void clockwiseRotate(AvlNodePtr& a) {
AvlNodePtr b = a->left;
//左叶子 a->left = b->right;
//a的左叶子变为b的右叶子，b本来的子结点都比a小的。 b->right = a;
//b的右结点指向a，b的高度上升了。 a->height = max(height(a->left), height(a->right)) + 1;
//重新计算a的高度 b->height = max(height(b->left), a->height) + 1;
//重新计算b的高度 a = b;
//a的位置现在是b，当前的根结点 }
//逆时针旋转 void antiClockWiseRotate(AvlNodePtr& a) {
AvlNodePtr b = a->right;
//右结点 a->right = b->left;
//a接收b的左结点 b->left = a;
//自己成为b的左结点 a->height = max(height(a->left), height(a->right)) + 1;
//计算高度 b->height = max(b->height, height(a->right)) + 1;
//计算高度 a = b;
//新的根结点 }
//对左边结点的双旋转 void doubleWithLeftChild(AvlNodePtr& k3) {
antiClockWiseRotate(k3->left);
//逆时针旋转左结点 clockwiseRotate(k3);
//顺时针旋转自身 }
//对右边结点的双旋转 void doubleWithRightChild(AvlNodePtr& k3) {
clockwiseRotate(k3->right);
//顺时针旋转有节点 antiClockWiseRotate(k3);
//逆时针旋转自身 }
//插入对象，这里使用了引用 void insert(const Comparable& x, AvlNodePtr& t) {
if (!t) {
t = new AvlNode(x, nullptr, nullptr);
}
else if (x < t->element) {
insert(x, t->left);
//比根结点小，插入左边 if (height(t->left) - height(t->right) == 2)//高度差达到2了 {
if (x < t->left->element)//插入左边 {
clockwiseRotate(t);
//顺时针旋转 }
else {
doubleWithLeftChild(t);
//双旋转 }
}
}
else if (x > t->element) {
insert(x, t->right);
//比根结点大，插入右边 if (height(t->right) - height(t->left) == 2)//高度差达到2 {
if (t->right->element < x)//插入右边 {
antiClockWiseRotate(t);
//旋转 }
else {
doubleWithRightChild(t);
//双旋转 }
}
}
else {
//相同的 }
t->height = max(height(t->left), height(t->right)) + 1;
//计算结点的高度 }
void removeMin(AvlNodePtr& x, AvlNodePtr& t)const {
if (!t) {
return;
//找不到 }
if (t->left) {
removeMin(t->left);
//使用了递归的方式 }
else {
//找到最小的结点了 x->element = t->element;
AvlNodePtr oldNode = t;
t = t->right;
delete oldNode;
//删除原来要删除的结点 }
if (t) {
t->height = max(height(t->left), height(t->right)) + 1;
//计算结点的高度 if(height(t->left) - height(t->right) == 2) {
//如果左儿子高度大于右儿子高度 if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度 {
clockwiseRotate(t);
//顺时针旋转 }
else {
doubleWithLeftChild(t);
//双旋转左子树 }
}
else {
if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树 {
antiClockWiseRotate(t);
//逆时针旋转 }
else {
doubleWithRright(t);
//双旋转右子树 }
}
}
}
//删除某个对象，这里必须要引用 void remove(const Comparable& x, AvlNodePtr& t)const {
if (!t) {
return;
//树为空 }
else if (x < t->element) {
remove(x, t->left);
//比根结点小，去左边查找 }
else if (x > t->element) {
remove(x, t->right);
//比根结点大，去右边查找 }
else if (!t->left && !t->right)//找到结点了，有两个叶子 {
removeMin(t, t->right);
//这里选择的方法是删除右子树的最小的结点 }
else {
AvlNodePtr oldNode = t;
t = (t->left) ? t->left : t->right;
//走到这里，t最多只有一个叶子，将t指向这个叶子 delete oldNode;
//删除原来要删除的结点 }
if (t) {
t->height = max(height(t->left), height(t->right)) + 1;
//计算结点的高度 if(height(t->left) - height(t->right) == 2) {
//如果左儿子高度大于右儿子高度 if(height(t->left->left) >= height(t->left->right))//并且左儿子的左子树高度大于左儿子的右子树高度 {
clockwiseRotate(t);
//顺时针旋转 }
else {
doubleWithLeftChild(t);
//双旋转左子树 }
}
else {
if(height(t->right->right) - height(t->right->left) == 2) //如果右子树大于左子树 {
antiClockWiseRotate(t);
//逆时针旋转 }
else {
doubleWithRright(t);
//双旋转右子树 }
}
}
}
//左边子树的结点肯定比当前根小的，所以一直往左边寻找 AvlNodePtr findMin(AvlNodePtr t)const {
if (!t) {
return nullptr;
//找不到 }
if (!t->left) {
return t;
}
return findMin(t->left);
//使用了递归的方式 }
//右边子树的结点肯定比当前根大，所以一直往右边找 AvlNodePtr findMax(AvlNodePtr t)const {
if (t) {
while (t->right)//使用了循环的方式 {
t = t->right;
}
}
return t;
}
//判断是否包含某个对象，因为要使用递归，所以还有一个public版本的 bool contains(const Comparable& x, AvlNodePtr t)const {
if (!t) {
return false;
//空结点了 }
else if (x < t->element) {
//根据二叉树的定义，比某个结点小的对象，肯定只能存在与这个结点的左边的子树 return contains(x, t->left);
}
else if (x > t->element) {
//根据二叉树的定义，比某个结点大的对象，肯定只能存在与这个结点的右边的子树 return contains(x, t->right);
}
else {
//相等，就是找到啦。 return true;
}
}
//清空子树 void makeEmpty(AvlNodePtr& t) {
if (t) {
makeEmpty(t->left);
//清空左边 makeEmpty(t->right);
//清空右边 delete t;
//释放自身 }
t = nullptr;
//置为空 }
//打印子树，这里没有使用复杂的排位，纯属打印 void printTree(AvlNodePtr t)const {
if (!t) {
return;
}
std::cout << t->element << std::endl;
//输出自身的对象 printTree(t->left);
//打印左子树 printTree(t->right);
//打印右子树 }
AvlNodePtr clone(AvlNodePtr t)const {
if (!t) {
return nullptr;
}
return new AvlNode(t->element, clone(t->left), clone(t->right));
}
int height(AvlNodePtr t)const {
return t == nullptr ? -1 : t->height;
}
}
;
}
#endif

//// AvlTree.cpp// HelloWorld// Created by feiyin001 on 17/1/9.// Copyright (c) 2017年 FableGame. All rights reserved.//#include "AvlTree.h"using namespace Fable;
int main(int argc, char* argv[]){
AvlTree<int> a;
for(int i = 0;
i < 100;
++i) {
a.insert(i);
}
return 0;
}