AVL树学习笔记（二）：实现代码

以下代码为学习用，没有优化操作，不适合生产环境

/** avl.h
*
* Created on: Oct 11, 2014
* Author: root
*/
#ifndef AVL_H_
#define AVL_H_
class avl_node 
public:
avl_node();
int key;
int value;
unsigned long left_height;
unsigned long right_height;
unsigned long height;
avl_node *parent;
avl_node *left;
avl_node *right;
;
class avl_tree 
protected:
avl_node *root;
char ptr_buf[128][1024];
void left_rotate(avl_node *node);
void right_rotate(avl_node *node);
void cal_height(avl_node *node);
void rewind();
public:
avl_tree();
~avl_tree();
avl_node* getRoot();
avl_node* insert(avl_node *root, int key, int value);
avl_node* remove(avl_node *root, int key);
avl_node* remove(avl_node *root, avl_node *node);
avl_node* search(avl_node *root, int key);
int heightLR(avl_node *root);
void clear(avl_node *root);
void print(avl_node *root,int h=-1);
void printAll();
void clearBuffer();
;
#endif /* AVL_H_ */

/*
* avl.cpp
*
* Created on: Oct 11, 2014
* Author: root
*/
#include "avl.h"
//For test;
#include
#include
avl_node::avl_node() 
this->height = 0;
this->left_height = 0;
this->right_height = 0;
this->parent = 0;
this->left = 0;
this->right = 0;
this->key = 0;
this->value = 0;

avl_tree::avl_tree() 
this->root = 0;
for (int i = 0; i < 128; i++) 
this->ptr_buf[i][0] = 0;


avl_tree::~avl_tree() 
clear(this->root);

void avl_tree::clearBuffer() 
for (int i = 0; i < 128; i++) 
memset(this->ptr_buf[i], 0, 1024);


void avl_tree::clear(avl_node *root) 
if (!root) 
root = this->root;

if (!root) 
return;

if (root->left) 
clear(root->left);

if (root->right) 
clear(root->right);

delete root;
if (this->root == root) 
this->root = 0;


void avl_tree::left_rotate(avl_node *node) 
if (!root) 
root = this->root;

if (!root) 
return;

//printf("L %d,", node->key);
avl_node *ol = node->right->left;
node->right->parent = node->parent;
if (node->parent) 
if (node == node->parent->left) 
node->parent->left = node->right;
 else 
node->parent->right = node->right;


node->parent = node->right;
node->parent->left = node;
if (ol) 
node->right = ol;
ol->parent = node;
cal_height(ol);
 else 
node->right = 0;

cal_height(node->parent);
cal_height(node);

void avl_tree::right_rotate(avl_node *node) 
if (!root) 
root = this->root;

if (!root) 
return;

//printf("R %d,", node->key);
avl_node *oor = node->left->right;
node->left->parent = node->parent;
if (node->parent) 
if (node == node->parent->left) 
node->parent->left = node->left;
 else 
node->parent->right = node->left;


node->parent = node->left;
node->parent->right = node;
if (oor) 
node->left = oor;
oor->parent = node;
cal_height(oor);
 else 
node->left = 0;

cal_height(node->parent);
cal_height(node);

int avl_tree::heightLR(avl_node *root) 
if (!root) 
root = this->root;

if (!root) 
return 0;

return root->left_height - root->right_height;

void avl_tree::cal_height(avl_node *node) 
node->height = 0;
node->left_height = 0;
node->right_height = 0;
if (node->left) 
cal_height(node->left);
node->left_height = node->left->height + 1;

if (node->right) 
cal_height(node->right);
node->right_height = node->right->height + 1;

node->height =
node->left_height > node->right_height ?
node->left_height : node->right_height;

void avl_tree::rewind() 
while (this->root->parent) 
this->root = this->root->parent;


avl_node* avl_tree::getRoot() 
return this->root;

avl_node* avl_tree::insert(avl_node *root, int key, int value) 
if (!key) 
return 0;

if (!root) 
root = this->root;

if (!root) 
this->root = new avl_node();
this->root->key = key;
this->root->value = value;
return this->root;

if (root->key > key) 
if (root->left) 
return insert(root->left, key, value);
 else 
avl_node *node = new avl_node();
node->parent = root;
root->left = node;
node->key = key;
node->value = value;
cal_height(this->root);
if (heightLR(root->parent) > 1) 
//Left lost balance;
if (root == root->parent->left) 
right_rotate(root->parent);
 else 
left_rotate(root);
right_rotate(node->parent);


while (root) 
cal_height(root);
if (heightLR(root) > 1) 
right_rotate(root);

root = root->parent;

rewind();
return node;


if (root->key < key) 
if (root->right) 
return insert(root->right, key, value);
 else 
avl_node *node = new avl_node();
node->parent = root;
root->right = node;
node->key = key;
node->value = value;
cal_height(this->root);
if (heightLR(root->parent) < -1) 
//Right lost balance;
if (root == root->parent->right) 
left_rotate(root->parent);
 else 
right_rotate(root);
left_rotate(node->parent);


root = node;
while (root) 
cal_height(root);
if (heightLR(root) < -1) 
left_rotate(root);

root = root->parent;

rewind();
return node;


return 0;

avl_node* avl_tree::remove(avl_node *root, avl_node *node) 
if (!root) 
root = this->root;

if (!root) 
return 0;

if (root->key > node->key) 
return remove(root->left, node);

if (root->key < node->key) 
return remove(root->right, node);

if (root->key == node->key) 
if (root != this->root) 
//Normal node;
if (!node->left && !node->right) 
if (node == node->parent->left) 
root->parent->left = 0;
 else 
root->parent->right = 0;

 else 
if (!node->left) 
left_rotate(root);
return remove(root, root);

if (!node->right) 
right_rotate(root);
return remove(root, root);

if (node->left && node->right) 
if (node->left_height > node->right_height) 
right_rotate(root);
return remove(root, root);

if (node->left_height < node->right_height) 
left_rotate(root);
return remove(root, root);

if (node->left_height == node->right_height) 
left_rotate(root);
return remove(root, root);



 else 
//Remove root;
if (root->left && root->right) 
if (node->left_height > node->right_height) 
right_rotate(root);
rewind();
return remove(root, root);

if (node->left_height < node->right_height) 
left_rotate(root);
rewind();
return remove(root, root);

if (node->left_height == node->right_height) 
left_rotate(root);
rewind();
return remove(root, root);

return remove(root, root);
 else 
if (root->left) 
this->root = root->left;
return remove(root, root);

if (root->right) 
this->root = root->right;
return remove(root, root);

if (!root->left && !root->right) 
this->root = 0;



delete root;
rewind();
cal_height(this->root);
root = root->parent;
while (root) 
if (root->parent) 
if (root->parent->parent) 
cal_height(root->parent->parent);
if (heightLR(root->parent->parent) < -1) 
if (root == root->parent->right
&& root->parent
== root->parent->parent->right) 
left_rotate(root->parent->parent);

if (root == root->parent->left
&& root->parent
== root->parent->parent->right) 
right_rotate(root->parent);
left_rotate(root->parent);


if (heightLR(root->parent->parent) > 1) 
if (root == root->parent->left
&& root->parent == root->parent->parent->left) 
right_rotate(root->parent->parent);

if (root == root->parent->right
&& root->parent == root->parent->parent->left) 
left_rotate(root->parent);
right_rotate(root->parent);




cal_height(root);
if (heightLR(root) > 1) 
right_rotate(root);

if (heightLR(root) < -1) 
left_rotate(root);

root = root->parent;

rewind();

return 0;

avl_node* avl_tree::remove(avl_node *root, int key) 
avl_node *node = search(root, key);
if (node) 
return remove(root, node);

return 0;

avl_node* avl_tree::search(avl_node *root, int key) 
if (!root) 
root = this->root;

if (!root) 
return 0;

if (root->key == key) 
return root;

if (root->key > key) 
return search(root->left, key);

if (root->key < key) 
return search(root->right, key);

return 0;

void avl_tree::print(avl_node *root, int h) 
if (!root) 
root = this->root;

if (!root) 
return;

if (h == -1) 
h = root->height;

if (root->left) 
print(root->left, h - 1);

if (root->right) 
print(root->right, h - 1);

printf("Node:%d, Parent: %d, Height:%d,L:%d,R:%dn", root->key,
root->parent ? root->parent->key : 0, root->height,
root->left_height, root->right_height);
char buf[8];
sprintf(buf, " %d ", root->key);
strcat(this->ptr_buf[h], buf);

void avl_tree::printAll() 
clearBuffer();
print(0, -1);
for (int i = 127; i >= 0; i--) 
if (this->ptr_buf[i][0]) 
printf("* %sn", this->ptr_buf[i]);

/*
* main.cpp
*
* Created on: Oct 11, 2014
* Author: root
*/
#include "avl.h"
#include
//test avl tree;
int main(int argc,char **argv)
avl_tree t;
for(int i=1;i<=100;i++)
t.insert(0,i,i);

t.printAll();
printf("-----------------------n");
t.remove(t.getRoot(),64);
t.printAll();
return 0;