|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
纯C实现了AVL树, 非递归算法
实现了简单的范型, 这个AVL树是当作字典(即保持(key, value)对)用的(类似C++标准库的std::map), 也就是用AVL树实现了映射
测试插入4000000个数据(别数有几个0了, 是四百万), 生成的(key, value)对是随机的(但是可以保证4000000个数据中每一对数据的key都是唯一的), 插入4000000个数据后树的高度(在我测试过的情况中)为25左右
然后删除2000000个数据, 查找2000000个数据
所花时间大概在9秒到10秒之间(我看的手表计时......没有用time.h中的函数计时, 不是很准, 大家可以自己测试)
下面贴完整代码吧, 注释应该是够了, 可能没有太注意排版, 100多行代码全部塞一个函数里......凑合着看......
实现整个AVL树用了446行代码, 删除算法很多书都没有(我看的这本书有, 不过整个AVL树书上只是讲了思路, 没有代码), 连小甲鱼的视频里都没有哦, 而且非递归, 应该挺难得的吧......
贴代码:
注意stdbool.h VS貌似没有(微软貌似从来没有对C/C++标准很重视......stdbool.h是C99的内容), bool类型要自己定义#ifndef AVL_TREE_H
#define AVL_TREE_H
#include <stddef.h>
#include <stdbool.h>
struct AVLTreeHandle;
typedef struct AVLTreeHandle * AVLTree;
AVLTree CreateAVLTree(int (*cmp_key)(const void *, const void *),
size_t key_width, size_t value_width);
bool InsertAVLTree(AVLTree avl, const void *key, const void *value);
bool DeleteAVLTree(AVLTree avl, const void *key, void *value);
void * SearchAVLTree(AVLTree avl, const void *key);
bool IsAVLTreeEmpty(AVLTree avl);
void ClearAVLTree(AVLTree avl);
void DestroyAVLTree(AVLTree avl);
#endif
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <assert.h>
#include "avl_tree.h"
#define NONE -1
#define LEFT 0
#define RIGHT 1
#define LL 2
#define LR 3
#define RL 4
#define RR 5
typedef struct AVLTreeNode {
int8_t bf;
void *key;
void *value;
struct AVLTreeNode *parent;
struct AVLTreeNode *left_child;
struct AVLTreeNode *right_child;
} AVLTreeNode;
struct AVLTreeHandle {
int (*cmp_key)(const void *, const void *);
size_t key_width,
value_width;
AVLTreeNode *root;
};
static void LLRotate(AVLTreeNode *x);
static void LRRotate(AVLTreeNode *x);
static void RLRotate(AVLTreeNode *x);
static void RRRotate(AVLTreeNode *x);
static void DestroyTree(AVLTreeNode *root);
static AVLTreeNode * FindPrev(AVLTreeNode *root);
AVLTree CreateAVLTree(int (*cmp_key)(const void *, const void *),
size_t key_width, size_t value_width)
{
struct AVLTreeHandle *new = malloc(sizeof (struct AVLTreeHandle));
assert(new);
new->cmp_key = cmp_key;
new->key_width = key_width;
new->value_width = value_width;
new->root = NULL;
return new;
}
bool InsertAVLTree(AVLTree avl, const void *key, const void *value)
{
AVLTreeNode *p = avl->root;
AVLTreeNode *pp = NULL;
AVLTreeNode *x = NULL;
int non_balanced_type, cmp_result;
/*********************************************
* x是在插入的路径上, 在插入前最后一个bf值为 *
* 1或-1的节点 *
*********************************************/
while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0) {
pp = p;
if (pp->bf == 1 || pp->bf == -1) {
x = pp;
non_balanced_type = NONE;
}
if (cmp_result < 0) {
p = p->left_child;
if (x != NULL) {
/* 根据插入路径确定不平衡类型 */
switch (non_balanced_type) {
case NONE: non_balanced_type = LEFT; break;
case LEFT: non_balanced_type = LL; break;
case RIGHT: non_balanced_type = RL; break;
}
}
}
else {
p = p->right_child;
if (x != NULL) {
/* 根据插入路径确定不平衡类型 */
switch (non_balanced_type) {
case NONE: non_balanced_type = RIGHT; break;
case LEFT: non_balanced_type = LR; break;
case RIGHT: non_balanced_type = RR; break;
}
}
}
}
/* 键在原AVL树中不存在 */
if (p == NULL) {
AVLTreeNode *new = malloc(sizeof (AVLTreeNode));
bool insert_left, insert_right, is_balanced;
int b;
assert(new);
new->key = malloc(avl->key_width);
assert(new->key);
new->value = malloc(avl->value_width);
assert(new->value);
new->parent = pp;
new->left_child = NULL;
new->right_child = NULL;
memcpy(new->key, key, avl->key_width);
memcpy(new->value, value, avl->value_width);
new->bf = 0;
/* 原树为空 */
if (pp == NULL) {
avl->root = new;
return true;
}
insert_left = non_balanced_type == LL || non_balanced_type == LR || non_balanced_type == LEFT;
insert_right = non_balanced_type == RR || non_balanced_type == RL || non_balanced_type == RIGHT;
is_balanced = (x != NULL) && ((x->bf == 1 && insert_right) || (x->bf == -1 && insert_left));
if (cmp_result < 0) {
pp->left_child = new;
++pp->bf;
}
else {
pp->right_child = new;
--pp->bf;
}
/*************************************************************************************
* 当插入路径上的节点在插入前平衡因子都为0的话, 修改从根节点到pp的父节点的平衡因子, *
* 否则修改从x到pp父节点的平衡因子(pp的平衡因子已经修改过) *
*************************************************************************************/
p = (x == NULL) ? avl->root : x;
while (p != pp) {
if (avl->cmp_key(key, p->key) < 0) {
++p->bf;
p = p->left_child;
}
else {
--p->bf;
p = p->right_child;
}
}
/* 树在插入后仍然保持平衡 */
if (x == NULL || is_balanced)
return true;
/* 插入后树不平衡 */
/* 根据不平衡类型执行对应旋转 */
switch (non_balanced_type) {
case LL: LLRotate(x);
x->right_child->bf = 0;
break;
case LR: b = x->left_child->right_child->bf;
LRRotate(x);
x->left_child->bf = (b == -1) ? 1 : 0;
x->right_child->bf = (b == 1) ? -1 : 0;
break;
case RL: b = x->right_child->left_child->bf;
RLRotate(x);
x->left_child->bf = (b == -1) ? 1 : 0;
x->right_child->bf = (b == 1) ? -1 : 0;
break;
case RR: RRRotate(x);
x->left_child->bf = 0;
break;
default: assert(0); break;
}
x->bf = 0;
return true;
}
return false;
}
bool DeleteAVLTree(AVLTree avl, const void *key, void *value)
{
AVLTreeNode *p = avl->root, /* p指向要删除的节点 */
*q = NULL, /* q指向p的父节点 */
*c; /* c在下面会说明 */
int cmp_result;
bool lower = false;
while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0) {
q = p;
p = (cmp_result < 0) ? p->left_child : p->right_child;
}
/* 没有找到关键字为key的节点 */
if (p == NULL)
return false;
memcpy(value, p->value, avl->value_width);
/* 欲删除节点有两个孩子 */
if (p->left_child != NULL && p->right_child != NULL) {
AVLTreeNode *prev = FindPrev(p);
void *p_key = p->key, *p_value = p->value;
p->key = prev->key;
p->value = prev->value;
prev->key = p_key;
prev->value = p_value;
p = prev;
q = prev->parent;
}
/* c指向p唯一非空的子树(如果p为叶子节点c为NULL) */
c = (p->left_child != NULL) ? p->left_child : p->right_child;
if (p == avl->root) {
avl->root = c;
q = NULL;
} else if (p == q->left_child) {
q->left_child = c;
--q->bf;
} else {
q->right_child = c;
++q->bf;
}
if (c != NULL)
c->parent = q;
free(p->key);
free(p->value);
free(p);
while (q != NULL) {
if (lower) {
if (p == q->left_child)
--q->bf;
else
++q->bf;
}
if (q->bf == 0)
lower = true;
else if (q->bf == 1 || q->bf == -1)
break;
else {
/* 树出现不平衡 */
/* 除了R0型不平衡和L0型不平衡外, 其他不平衡矫正后都会使子树的高度减小 */
int b;
if (q->bf == 2) {
/* R型不平衡 */
int lbf = q->left_child->bf;
if (lbf == 0) {
/* R0型不平衡 */
LLRotate(q);
q->bf = -1;
q->right_child->bf = 1;
break;
} else if (lbf == 1) {
/* R1型不平衡 */
LLRotate(q);
q->bf = 0;
q->right_child->bf = 0;
} else {
/* R-1型不平衡 */
b = q->left_child->right_child->bf;
LRRotate(q);
q->bf = 0;
q->left_child->bf = (b == -1) ? 1 : 0;
q->right_child->bf = (b == 1) ? -1 : 0;
}
} else {
/* L型不平衡 */
int rbf = q->right_child->bf;
if (rbf == 0) {
/* L0型不平衡 */
RRRotate(q);
q->bf = 1;
q->left_child->bf = -1;
break;
} else if (rbf == 1) {
/* L1型不平衡 */
b = q->right_child->left_child->bf;
RLRotate(q);
q->bf = 0;
q->left_child->bf = (b == -1) ? 1 : 0;
q->right_child->bf = (b == 1) ? -1 : 0;
} else {
/* L-1型不平衡 */
RRRotate(q);
q->bf = 0;
q->left_child->bf = 0;
}
}
lower = true;
}
/* 上升一层 */
p = q;
q = q->parent;
}
return true;
}
void * SearchAVLTree(AVLTree avl, const void *key)
{
AVLTreeNode *p = avl->root;
int cmp_result;
while (p != NULL && (cmp_result = avl->cmp_key(key, p->key)) != 0)
p = (cmp_result < 0) ? p->left_child : p->right_child;
return (p == NULL) ? NULL : p->value;
}
bool IsAVLTreeEmpty(AVLTree avl)
{
return avl->root == NULL;
}
void ClearAVLTree(AVLTree avl)
{
DestroyTree(avl->root);
avl->root = NULL;
}
void DestroyAVLTree(AVLTree avl)
{
DestroyTree(avl->root);
free(avl);
}
static void LLRotate(AVLTreeNode *x)
{
/* X(2) Y(0)
* / \ / \
* Y(1) Xr ----> Yl X(0)
* / \ h h+1 / \
* Yl Yr Yr Xr
* h+1 h h h
*/
AVLTreeNode *y = x->left_child, *xr = x->right_child;
void *x_key = x->key, *x_value = x->value;
/* X(2) X(-2)
* / \ / \
* Y(1) Xr ----> Yl Y(1)
* / \ h h+1 / \
* Yl Yr Yl Yr
* h+1 h h+1 h
*/
x->left_child = y->left_child;
if (y->left_child != NULL)
y->left_child->parent = x;
x->right_child = y;
/* X(-2) Y(0)
* / \ / \
* Yl Y(1) ----> Yl X(0)
* h+1 / \ h+1 / \
* Yl Yr Yr Xr
* h+1 h h h
*/
x->key = y->key;
x->value = y->value;
y->key = x_key;
y->value = x_value;
y->left_child = y->right_child;
y->right_child = xr;
if (xr != NULL)
xr->parent = y;
}
static void LRRotate(AVLTreeNode *x)
{
RRRotate(x->left_child);
LLRotate(x);
}
static void RLRotate(AVLTreeNode *x)
{
LLRotate(x->right_child);
RRRotate(x);
}
static void RRRotate(AVLTreeNode *x)
{
/* X(-2) Y(0)
* / \ / \
* Xl Y(-1) ----> X(0) Yr
* h / \ / \ h+1
* Yl Yr Xl Yl
* h h+1 h h
*/
AVLTreeNode *y = x->right_child;
AVLTreeNode *xl = x->left_child;
void *x_key = x->key, *x_value = x->value;
/* X(-2) Y(0)
* / \ / \
* Xl Y(-1) ----> X(0) Yr
* h / \ / \ h+1
* Yl Yr Xl Yl
* h h+1 h h
*/
x->right_child = y->right_child;
if (y->right_child != NULL)
y->right_child->parent = x;
x->left_child = y;
y->right_child = y->left_child;
y->left_child = xl;
if (xl != NULL)
xl->parent = y;
x->key = y->key;
x->value = y->value;
y->key = x_key;
y->value = x_value;
}
static void DestroyTree(AVLTreeNode *root)
{
if (root != NULL) {
DestroyTree(root->left_child);
DestroyTree(root->right_child);
free(root->key);
free(root->value);
free(root);
}
}
static AVLTreeNode * FindPrev(AVLTreeNode *root)
{
for (root = root->left_child; root->right_child != NULL;
root = root->right_child)
;
return root;
}
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2015-2-15 13:21:55
置顶卡
千斤顶
显身卡
楼主
发表于 2015-2-15 13:33:29