二叉平衡树，大神帮忙找找虫子
最新想弄个动态属性保存的二叉树结构，想网上移植个标准c红黑树实现，结果都没成功。自己实现红黑树都要晕了，情况判断太多了，还费力不讨好。由于我对插入属性速度要求低就想自己实现个简单的平衡树
思路就是在树节点中维护 左深度ld 和 右深度rd 两个属性来调整树的平衡
当ld和rd的差值大于2就对该节点进行左旋或右旋操作(为什么是大于二呢？就是左右旋转操作的最小深度都达到了2，小2就矛盾了)
因此插入删除操作的时间复杂度就会是O(2lg(n))，查询操作的复杂度为O(lg(n)+2)
自己测了好多数据，也没发现问题，大家帮忙测测，有问题提一下，谢谢了
下面就上代码了
ztl_tree.h
程序代码：
#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
typedef unsigned char byte;
typedef struct ztl_tree_node ztl_tree_node_t;
typedef ztl_tree_node_t* ztl_tree_node_p;
struct ztl_tree_node{
unsigned long k;
size_t v;
ztl_tree_node_p l;
ztl_tree_node_p r;
ztl_tree_node_p p;
byte ld;
byte rd;
};
typedef struct ztl_tree ztl_tree_t;
typedef ztl_tree_t* ztl_tree_p;
struct ztl_tree{
int size;
ztl_tree_node_p root;
};
ztl_tree_p ztl_tree_init();
void ztl_tree_deep(ztl_tree_p tree, ztl_tree_node_p node);
void ztl_tree_adjust(ztl_tree_p tree, ztl_tree_node_p node);
void ztl_tree_add(ztl_tree_p tree, unsigned long key, size_t value);
ztl_tree_node_p ztl_tree_behind_node(ztl_tree_p tree, ztl_tree_node_p node);
size_t ztl_tree_remove(ztl_tree_p tree, unsigned long key);
ztl_tree_node_p ztl_tree_get_node(ztl_tree_p tree, unsigned long key);
size_t ztl_tree_get(ztl_tree_p tree, unsigned long key);
void ztl_tree_iterate(ztl_tree_p tree, ztl_tree_node_p node);
void ztl_tree_destory_it(ztl_tree_p tree, ztl_tree_node_p node);
void ztl_tree_destory(ztl_tree_p tree);
/** fun impl **/
ztl_tree_p ztl_tree_init()
{
ztl_tree_p tree = calloc(1,sizeof(ztl_tree_t));
tree->size=0;
tree->root=0;
return tree;
}
/**节点深度值维护*/
void ztl_tree_deep(ztl_tree_p tree, ztl_tree_node_p node)
{
if(!node)return;
if(node->l){
byte mxd = node->l->ld > node->l->rd ? node->l->ld : node->l->rd;
node->ld = mxd+1;
}else{
node->ld = 0;
}
if(node->r){
byte mxd = node->r->ld > node->r->rd ? node->r->ld : node->r->rd;
node->rd = mxd+1;
}else{
node->rd = 0;
}
}
/**节点调整*/
void ztl_tree_adjust(ztl_tree_p tree, ztl_tree_node_p node)
{ //printf("ztl_tree_adjust.......\n");
if(!node)return;
ztl_tree_deep(tree, node);
int dif = node->ld - node->rd;
if(dif > 2){//右旋
if(node->p){
if(node == node->p->l){
node->p->l = node->l;
}else{
node->p->r = node->l;
}
node->l->p = node->p;
}else{
node->l->p = 0;
tree->root = node->l;
}
ztl_tree_node_p nlr = node->l->r;
node->l->r = node;
node->p = node->l;
node->l = nlr;
if(nlr) nlr->p = node;
ztl_tree_deep(tree, node);
ztl_tree_deep(tree, node->p);
node = node->p;
}else if(dif < -2){//左旋
if(node->p){
if(node == node->p->l){
node->p->l = node->r;
}else{
node->p->r = node->r;
}
node->r->p = node->p;
}else{
node->r->p = 0;
tree->root = node->r;
}
ztl_tree_node_p nrl = node->r->l;
node->r->l = node;
node->p = node->r;
node->r = nrl;
if(nrl)nrl->p = node;
ztl_tree_deep(tree, node);
ztl_tree_deep(tree, node->p);
node = node->p;
}
ztl_tree_adjust(tree, node->p);
}
void ztl_tree_add(ztl_tree_p tree, unsigned long key, size_t value)
{
ztl_tree_node_p nnod = calloc(1, sizeof(ztl_tree_node_t));
nnod->k = key;
nnod->v = value;
if(tree->root){ //printf("11111111111.......start \n");
ztl_tree_node_p node = tree->root;
while(node){
if(key < node->k){
if(node->l){
node = node->l;
}else{
node->l = nnod;
nnod->p = node;
ztl_tree_adjust(tree, nnod);
tree->size++;
return;
}
}else if(key > node->k){
if(node->r){
node = node->r;
}else{
node->r = nnod;
nnod->p = node;
ztl_tree_adjust(tree, nnod);
tree->size++;
return;
}
}else{
node->v = value;
return;
}
}
//printf("11111111111.......end\n");
}else{ //printf("222222222.......start\n");
tree->root = nnod;
tree->size = 1;
}
}
/**后继节点*/
ztl_tree_node_p ztl_tree_behind_node(ztl_tree_p tree, ztl_tree_node_p node){
if(!node) return 0;
ztl_tree_node_p cnod = node->r;
while(cnod){
if(cnod->l)cnod = cnod->l;
else break;
}
return cnod;
}
size_t ztl_tree_remove(ztl_tree_p tree, unsigned long key)
{
ztl_tree_node_p node = ztl_tree_get_node(tree, key);
if(!node) return -1;
ztl_tree_node_p bnod = ztl_tree_behind_node(tree, node);
if(bnod){//删除节点有右分支
ztl_tree_node_p bpnod = bnod->p;
//父关系维护
if(node->p){
if(node == node->p->l){
node->p->l = bnod;
}else{
node->p->r = bnod;
}
bnod->p = node->p;
}else{
bnod->p = 0;
tree->root = bnod;
}
//左边关系维护
bnod->l = node->l;
if(node->l)node->l->p = bnod;
//右边关系维护
if(bnod != node->r){//后继节点不等于右节点
bnod ->r = node->r;
node->r->p = bnod;
bpnod->l = 0;//后继节点父关系（后继结点必是左节点）
ztl_tree_adjust(tree, bpnod);
}else{//后继节点等于右节点(不需要维护右边的关系)
ztl_tree_adjust(tree, node->r);
}
}else{//删除节点没有右分支
if(node->l){//删除节点没有右分支，但有左分支
if(node->p){
if(node == node->p->l){
node->p->l = node->l;
}else{
node->p->r = node->l;
}
node->l->p = node->p;
}else{
node->l->p = 0;
tree->root = node->l;
}
ztl_tree_adjust(tree, node->l);
}else{//删除节点没有左右分支
if(node->p){
if(node == node->p->l){
node->p->l = 0;
}else{
node->p->r = 0;
}
ztl_tree_adjust(tree, node->p);
}else{
tree->root = 0;
}
}
}
size_t nv = node->v;
free(node);
tree->size--;
return nv;
}
void ztl_tree_iterate(ztl_tree_p tree, ztl_tree_node_p node)
{
if(node){
printf("key: %d, value: %d, deep: %d, %d\n", (int)node->k, (int)node->v, node->ld, node->rd);
ztl_tree_iterate(tree, node->l);
ztl_tree_iterate(tree, node->r);
}
}
int get_num = 0;
ztl_tree_node_p ztl_tree_get_node(ztl_tree_p tree, unsigned long key)
{
ztl_tree_node_p node = 0;
if(tree->root){
node = tree->root;
while(node){get_num++;
if(key < node->k){
if(node->l){
node = node->l;
}else{
node = 0;
}
}else if(key > node->k){
if(node->r){
node = node->r;
}else{
node = 0;
}
}else{
break;
}
}
}
return node;
}
size_t ztl_tree_get(ztl_tree_p tree, unsigned long key){
ztl_tree_node_p node = ztl_tree_get_node(tree, key);
if(node) return node->v;
return -1;
}
void ztl_tree_destory_it(ztl_tree_p tree, ztl_tree_node_p node)
{
if(node){
ztl_tree_destory_it(tree, node->l);
ztl_tree_destory_it(tree, node->r);
free(node);
}
}
void ztl_tree_destory(ztl_tree_p tree)
{
ztl_tree_destory_it(tree, tree->root);
free(tree);
}
main.c
程序代码：
#include "ztl_tree.h"
int main(int argc, char ** argv)
{
// int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80, 110,
// 11, 41, 31, 61, 91, 71, 21, 51, 81, 111,
// 12, 42, 32, 62, 92, 72, 22, 52, 82, 112,
// 13, 43, 33, 63, 93, 73, 23, 53, 83, 113,
// 14, 44, 34, 64, 94, 74, 24, 54, 84, 114
// 15, 45, 35, 65, 95, 75, 25, 55, 85, 115,
// 16, 46, 36, 66, 96, 76, 26, 56, 86, 116,
// 17, 47, 37, 67, 97, 77, 27, 57, 87, 117,
// 18, 48, 38, 68, 98, 78, 28, 58, 88, 118,
// 19, 49, 39, 69, 99, 79, 29, 59, 89, 119
// };
ztl_tree_p tree = ztl_tree_init();
for(int i=0; i<2; i++){
//printf("add to tree... %d\n", i);
// ztl_tree_add(tree, a[i], i);
ztl_tree_add(tree, i, i+1);
// ztl_tree_add(tree, rand()%200, i);
}
//ztl_tree_add(tree, 17, 999);
printf("tree Size: %d \n", tree->size);
// ztl_tree_iterate(tree, tree->root);
int dv = ztl_tree_remove(tree, 1);
printf("tree Size: %d, deleteVal: %d, treeRoot:%d \n", tree->size, dv, (int)tree->root);
int maxnum = 0;
for(int i=0; i<3; i++){
get_num = 0;
int gv = ztl_tree_get(tree, i);
maxnum = get_num>maxnum?get_num:maxnum;
printf("get Num: %d, value: %d \n", get_num, gv);
}
printf("\nmaxnum: %d\n", maxnum);
ztl_tree_destory(tree);
return 0;
}
