C语言实现简单的红黑树

#include
#include//红黑布尔常量 
#define RED true
#define BLACK falseint N=0;typedef int Key;
typedef int Value;//红黑树的结点
typedef struct Node{Key key;Value value;struct Node *left,*right;bool color;
} Node,*RedBlackTree;//初始化函数 
void InitRedBlackTree(RedBlackTree &tree){tree=NULL;
} //获取树中节点个数
int size(){return N;
} 
//判断红
bool isRed(Node *x){if(x==NULL){return false;}return x->color==RED;
} 
//判断黑
bool isBlack(Node *x){if(x==NULL){return true; }return x->color==BLACK;
} 
//左旋转
Node *rotateLeft(Node* h){Node *x = h->right;h->right = x->left;x->left = h;x->color = h->color;h->color = RED;return x;
}
//右旋转
Node *rotateRight(Node* h){Node *x = h->left;h->left = x->right;x->right = h;x->color = h->color;h->color = RED;return x;
}
//颜色反转
void flipColors(Node *&h){h->color = RED;h->left->color = BLACK;h->right->color = BLACK;
}
//put函数 
Node* put(Node *&h,Key key,Value value){if(h == NULL){N++;Node *s = (Node*)malloc(sizeof(Node));s->key=key;s->value=value;s->color=RED;s->left=NULL;s->right=NULL;return s;}if(keykey){h->left = put(h->left,key,value);}else if(key>h->key){h->right = put(h->right,key,value);}else{h->value = value;}//当当前节点h的左子节点为黑色,右子节点为红色,则左旋if(isBlack(h->left)&&isRed(h->right)){h = rotateLeft(h);} //当当前节点的左子节点 和 左子节点的左子节点 都为红色,需要右旋 if(isRed(h->left)&&isRed(h->left->left)) {h = rotateRight(h);}//当当前节点的左子节点和右子节点全都为红色,需要颜色翻转if(isRed(h->left)&&isRed(h->right)){flipColors(h);} return h;
}
//重载的put,插入之后返回结点需要保存一下,并且根节点的颜色要一直为黑色
void put(Key key,Value value,Node *&root){root = put(root,key,value);root->color = BLACK;
}
//get函数,和二叉查找树一样,没多少区别,递归一下
Value get(Node *x,Key key){if(x == NULL){return NULL;}if(keykey){return get(x->left,key);}else if(key>x->key){return get(x->right,key);}else{return x->value;}
}
//主函数
int main(){//初始化RedBlackTree root;InitRedBlackTree(root);//添加put(1,10,root);put(2,20,root);put(3,30,root); //获取   printf("get(1)->%d\n",get(root,1));printf("get(2)->%d\n",get(root,2));printf("get(3)->%d\n",get(root,3));//删除功能还没学会,过两天吸收完了再学return 0;
} 

下面还有java版本的,因为考研要求用c写,我才用c练习一遍,平时写java居多,这个java版本的是黑马程序员的数据结构课程里的代码,浅记录一下

/*** 红黑树代码 传入键值的类型,并且键继承Comparable 接口具有比较功能* @param * @param */
public class RedBlackTree, Value>{//红链接标识public static final boolean RED = true;//黑链接标识public static final boolean BLACK = false;//记录根节点private Node root;//记录树中的元素个数private int N;private class Node {//存储键public Key key;//存储值private Value value;//记录左子节点public Node left;//记录右子节点public Node right;//由其父节点只想他的链接颜色public boolean color;public Node(Key key, Value value, Node left, Node right, boolean color) {this.key = key;this.value = value;this.left = left;this.right = right;this.color = color;}}//获取树中节点个数public int size() {return N;}/*** 判断当前节点的父指向链接是否为红色** @param x* @return*/private boolean isRed(Node x) {//先判空,空连接默认为黑色if (x == null) {return false;}return x.color == RED;}/*** 判断当前节点的父指向链接是否为黑色** @param x* @return*/private boolean isBlack(Node x) {//先判空,空连接默认为黑色if (x == null) {return true;}return x.color == BLACK;}/*** 左旋转** @param h* @return*/private Node rotateLeft(Node h) {//获取h节点的右子节点，表示为xNode x = h.right;//让x节点的左子节点成为h节点的右子节点h.right = x.left;//让h成为x节点的左子节点x.left = h;//让x节点的color属性等于h节点的color属性x.color = h.color;//让h节点的color属性变为红色h.color = RED;return x;}/*** 右旋转** @param h* @return*/private Node rotateRight(Node h) {//获取h节点的左子节点，表示为xNode x = h.left;//让x节点的右子节点成为h节点的左子节点h.left = x.right;//让h节点成为x节点的右子节点x.right = h;//让x节点的color属性等于h节点的color属性x.color = h.color;//让h节点的color属性为红色h.color = RED;return x;}/*** 颜色反转** @param h*/private void flipColors(Node h) {//当前节点变为红色h.color = RED;//左子节点和右子节点变为黑色h.left.color = BLACK;h.right.color = BLACK;}/*** 在整个树上进行插入操作** @param key* @param value*/public void put(Key key, Value value) {root = put(root, key, value);//根节点总是黑色root.color = BLACK;}/*** 在指定的树中，完成插入操作，并且返回添加后的新树** @param h* @param key* @param value* @return*/private Node put(Node h, Key key, Value value) {//判空，为空则直接返回一个红色的节点if (h == null) {//数量+1N++;return new Node(key, value, null, null, RED);}//不为空则比较h节点的键和key的大小int cmp = key.compareTo(h.key);if (cmp < 0) {//继续往左h.left = put(h.left, key, value);} else if (cmp > 0) {//继续往右h.right = put(h.right, key, value);} else {//发生值的替换h.value = value;}//进行左旋:当当前节点h的左子节点为黑色，右子节点为红色，则左旋if (isBlack(h.left) && isRed(h.right)) {h = rotateLeft(h);}//进行右旋:当当前节点的左子节点 和 左子节点的左子节点 都为红色，需要右旋if (isRed(h.left) && isRed(h.left.left)) {h = rotateRight(h);}//颜色反转:当前节点的左子节点和右子节点都为红色，需要颜色反转if (isRed(h.left) && isRed(h.right)) {flipColors(h);}return h;}/*** 根据key 获取value** @param key* @return*/public Value get(Key key) {return get(root, key);}/*** 从指定的树x中查找key 对应的值** @param x* @param key* @return*/public Value get(Node x, Key key) {//判空，空则没有值if (x == null) {return null;}//比较x节点的键的大小int cmp = key.compareTo(x.key);if (cmp < 0) {return get(x.left, key);} else if (cmp > 0) {return get(x.right, key);} else {return x.value;}}
}

主函数自己写,就new 一下put,get自己试一试;

红黑树的左旋右旋和颜色反转是精髓 我再去理解理解

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！