![]() |
#2
xyzdwf2021-08-26 14:47
两文件合在一起,可以在论坛中在线运行
![]() #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, node); 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, node); 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); } 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<71; 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, 39); printf("tree Size: %d, deleteVal: %d, treeRoot:\n", tree->size, dv); int maxnum = 0; for(int i=0; i<71; 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; } [此贴子已经被作者于2021-8-29 12:03编辑过] |
由于我对插入属性速度要求低就想自己实现个简单的平衡树
思路就是在树节点中维护 左深度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;
}