OneKdTree.h
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
class AvlTree;
class AvlNode{
friend class AvlTree;
int data;
int height;
AvlNode *left;
AvlNode *right;
AvlNode(int _data) :data(_data), height(0), left(NULL), right(NULL){}
};
class AvlTree{
AvlNode *root;
public:
AvlTree() :root(NULL){}
int Height(AvlNode *node){ return node == NULL ? -1 : node->height; }
void Insert(int _data){ _insert(root, _data); }
void Delete(int _data){ _delete(root, _data); }
bool Find(int _data);
void print(){ travel(root); cout << endl; }
void OneDRangeQuery(int low, int high);
private:
AvlTree(const AvlTree &);
AvlTree& operator=(const AvlTree&);
void LL(AvlNode* &node);
void RR(AvlNode* &node);
void RL(AvlNode* &node);
void LR(AvlNode* &node);
void _insert(AvlNode* &node,int _data);
void _delete(AvlNode* &node, int _data);
void travel(AvlNode *node);
AvlNode *FindMin(AvlNode *node);
AvlNode *FindParent(AvlNode *node, int _data);
void ParentRotate(AvlNode* &node, AvlNode* &parent);
void LeftHigherhanRight(AvlNode* &node);
void RightHigherhanLeft(AvlNode* &node);
AvlNode* FindSplitNode(int low, int high);
};
void AvlTree::OneDRangeQuery(int low, int high)
{
AvlNode *node = FindSplitNode(low, high);
if (node == NULL)
return;
if (node->left == NULL&&node->right == NULL){
if (node->data >= low && node->data <= high)
cout << node->data << " ";
}
else {
AvlNode *temp = node->left;
while (temp&&(temp->left != NULL || temp->right != NULL)){
if (temp->data >= low){
travel(temp->right);
temp = temp->left;
}
else {
temp = temp->right;
}
}
if (temp&&temp->data >= low&&temp->data <= high)
cout << temp->data << " ";
temp = node->right;
while (temp&&(temp->left != NULL || temp->right != NULL)){
if (temp->data <= high){
travel(temp->left);
temp = temp->right;
}
else {
temp = temp->left;
}
}
if (temp&&temp->data >= low&&temp->data <= high)
cout << temp->data << " ";
}
cout << endl;
}
AvlNode* AvlTree::FindSplitNode(int low, int high)
{
if (low > high)
return NULL;
AvlNode *node = root;
if (node == NULL)
return NULL;
while ((node->right != NULL || node->left != NULL) && (node->data >= high || node->data < low)){
if (node->data >= high)
node = node->left;
else
node = node->right;
}
return node;
}
void AvlTree::LeftHigherhanRight(AvlNode* &node)
{
if (Height(node->left) - Height(node->right) == 2){
if (node->left){
if (Height(node->left->right) > Height(node->left->left))
LR(node);
else
LL(node);
}
}
}
void AvlTree::RightHigherhanLeft(AvlNode* &node)
{//调用次数多,封装成函数
if (Height(node->right) - Height(node->left) == 2){
if (node->right){
if (Height(node->right->left)>Height(node->right->right))
RL(node);
else
RR(node);
}
}
}
void AvlTree::ParentRotate(AvlNode* &node, AvlNode* &parent)
{//旋转从node到parent路径上的每一个结点,使之平衡
if (parent == NULL)
return;
if (node->data > parent->data){
ParentRotate(node->left, parent);
}
else if (node->data<parent->data){
ParentRotate(node->right, parent);
}
LeftHigherhanRight(node);
RightHigherhanLeft(node);
}
AvlNode *AvlTree::FindParent(AvlNode *node, int _data)
{//找父亲结点
if (node == NULL || node->data == _data)
return NULL;
if ((node->left && node->left->data == _data) || (node->right&&node->right->data == _data))
return node;
else if (node->data>_data)
return FindParent(node->left, _data);
else if (node->data<_data)
return FindParent(node->right, _data);
}
AvlNode *AvlTree::FindMin(AvlNode *node)
{//找最小结点
if (node){
while (node->left)
node = node->left;
}
return node;
}
void AvlTree::_delete(AvlNode* &node, int _data)
{
if (node == NULL){
// cout << "the element is not exit" << endl;
return;
}
else {
if (_data < node->data){
_delete(node->left, _data);
RightHigherhanLeft(node);//右子树高于左子树,旋转
}
else if (_data > node->data){
_delete(node->right, _data);
LeftHigherhanRight(node);//左子树高于右子树,旋转
}
else {//定位到要删除的结点
AvlNode *temp = FindMin(node->right);
if (temp == NULL){//node没有右结点
temp = node;
node = node->left;
delete temp;
}
else{
if (temp == node->right){//node右结点没有左子树
node->right = temp->right;
node->data = temp->data;
delete temp;
LeftHigherhanRight(node);//删除后,可能左子树高于右子树
}
else{//node右结点有左子树
AvlNode *parent = FindParent(node, temp->data);//寻找父节点
node->data = temp->data;
parent->left = temp->right;
delete temp;
//parent may not balence
ParentRotate(node, parent);//使得node到parent路径上的每一个结点能够平衡
}
}
}
}
if (node != NULL)
node->height = std::max(Height(node->left), Height(node->right)) + 1;//更新高度
}
void AvlTree::_insert(AvlNode* &node, int _data)
{
if (node == NULL){
node = new AvlNode(_data);//找到插入点
}
else {
if (_data <= node->data){
_insert(node->left, _data);//插入到左子树后,判断其高度是否平衡
if (Height(node->left) - Height(node->right) == 2){
if (_data > node->left->data)
LR(node);
else
LL(node);
}
}
else if (_data > node->data){//插入到右子树后,判断其高度是否平衡
_insert(node->right, _data);
if (Height(node->right) - Height(node->left) == 2){
if (_data<node->right->data)
RL(node);
else
RR(node);
}
}
}
node->height = std::max(Height(node->left), Height(node->right)) + 1;//更新高度
}
void AvlTree::LL(AvlNode* &node)
{
AvlNode *temp = node->left;
node->left = temp->right;
temp->right = node;
node->height = std::max(Height(node->left), Height(node->right)) + 1;
temp->height = std::max(Height(temp->left), Height(temp->right)) + 1;
node = temp;
}
void AvlTree::RR(AvlNode* &node)
{
AvlNode *temp = node->right;
node->right = temp->left;
temp->left = node;
node->height = std::max(Height(node->left), Height(node->right)) + 1;
temp->height = std::max(Height(temp->left), Height(temp->right)) + 1;
node = temp;
}
void AvlTree::LR(AvlNode* &node)
{
RR(node->left);
LL(node);
}
void AvlTree::RL(AvlNode* &node)
{
LL(node->right);
RR(node);
}
void AvlTree::travel(AvlNode *node)
{
if (node){
if (node->right == NULL&&node->left == NULL){
cout << node->data << " ";
}
else {
travel(node->left);
travel(node->right);
}
}
}
test.cpp
#include <iostream>
#include <ctime>
#include <cstdlib>
#include "OneKdTree.h"
int main(void)
{
AvlTree tree;
tree.Insert(54);
tree.Insert(34);
tree.Insert(23);
tree.Insert(12);
tree.Insert(54);
tree.Insert(12);
tree.Insert(23);
tree.Insert(59);
tree.Insert(34);
tree.Insert(59);
tree.Insert(5);
tree.Insert(5);
tree.Insert(97);
tree.Insert(97);
tree.OneDRangeQuery(4, 97);
return 0;
}