- 浏览: 874132 次
文章分类
最新评论
随想录(用好红黑树)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
红黑树作为一种特殊类型的二叉树,在软件中有很多的用处。但是在网络上面,讲解红黑树的文章和博客很多,可是真正找一份可以信赖的、方便使用的红黑树代码却不多。本篇文章的目的就是介绍如何正确使用红黑树的代码。
本篇文章的红黑树代码主要来自linux kernel 2.6.7,其中实现文件保存在ib/rbtree.c,而头文件保存在include/linux/rbtree.h。当前的linux代码已经升级到3.0以上了,但是关于红黑树的代码内容却没有什么大的改变,这说明关于红黑树的代码是非常稳定的。
(1)红黑树的来源
a)双向链表是二叉树的最初来源,虽然二叉树也可以做到基本有序,但是查找起来十分麻烦
b)在双向链表的基础上,人们发明了二叉树,二叉树保证了数据可以像数组一样快速完成二分查找,极大地提高了查找效率
c)二叉树存在各个数据查找效率不一致的情况,为了做到数据查找效率一致,人们设计了二叉平衡树,左子树和右子树的高度绝对值之差要小于1
d)为了减少子树旋转的次数,人们设计了红黑树,进一步提高了数据插入和删除的效率
(2)红黑树的概念
a)红黑树的每个节点必须是红色或者是黑色
b)根节点到叶节点之间的路径不存在连续的红色节点
c)根节点到叶节点之间的黑色节点数相同
(3)红黑树的基本结构定义
#ifndef _RBTREE_H #define _RBTREE_H #include <stdio.h> struct rb_node { struct rb_node *rb_parent; int rb_color; #define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; }; struct rb_root { struct rb_node *rb_node; }; #define RB_ROOT { NULL } #define rb_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); /* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_next(struct rb_node *); extern struct rb_node *rb_prev(struct rb_node *); extern struct rb_node *rb_first(struct rb_root *); /* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); static void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { node->rb_parent = parent; node->rb_color = RB_RED; node->rb_left = node->rb_right = NULL; *rb_link = node; } #endif /* _RBTREE_H */
(4) 红黑树的实现
a) 完成内容
1、调整插入节点rb_node的颜色
2、在rb_root中删除指定rb_node
3、获取首节点
4、获取上一个节点
5、获取下一个节点
6、替换节点
b)实现源代码
#include "rbtree.h" static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) { struct rb_node *right = node->rb_right; if ((node->rb_right = right->rb_left)) right->rb_left->rb_parent = node; right->rb_left = node; if ((right->rb_parent = node->rb_parent)) { if (node == node->rb_parent->rb_left) node->rb_parent->rb_left = right; else node->rb_parent->rb_right = right; } else root->rb_node = right; node->rb_parent = right; } static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) { struct rb_node *left = node->rb_left; if ((node->rb_left = left->rb_right)) left->rb_right->rb_parent = node; left->rb_right = node; if ((left->rb_parent = node->rb_parent)) { if (node == node->rb_parent->rb_right) node->rb_parent->rb_right = left; else node->rb_parent->rb_left = left; } else root->rb_node = left; node->rb_parent = left; } void rb_insert_color(struct rb_node *node, struct rb_root *root) { struct rb_node *parent, *gparent; while ((parent = node->rb_parent) && parent->rb_color == RB_RED) { gparent = parent->rb_parent; if (parent == gparent->rb_left) { { register struct rb_node *uncle = gparent->rb_right; if (uncle && uncle->rb_color == RB_RED) { uncle->rb_color = RB_BLACK; parent->rb_color = RB_BLACK; gparent->rb_color = RB_RED; node = gparent; continue; } } if (parent->rb_right == node) { register struct rb_node *tmp; __rb_rotate_left(parent, root); tmp = parent; parent = node; node = tmp; } parent->rb_color = RB_BLACK; gparent->rb_color = RB_RED; __rb_rotate_right(gparent, root); } else { { register struct rb_node *uncle = gparent->rb_left; if (uncle && uncle->rb_color == RB_RED) { uncle->rb_color = RB_BLACK; parent->rb_color = RB_BLACK; gparent->rb_color = RB_RED; node = gparent; continue; } } if (parent->rb_left == node) { register struct rb_node *tmp; __rb_rotate_right(parent, root); tmp = parent; parent = node; node = tmp; } parent->rb_color = RB_BLACK; gparent->rb_color = RB_RED; __rb_rotate_left(gparent, root); } } root->rb_node->rb_color = RB_BLACK; } static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root) { struct rb_node *other; while ((!node || node->rb_color == RB_BLACK) && node != root->rb_node) { if (parent->rb_left == node) { other = parent->rb_right; if (other->rb_color == RB_RED) { other->rb_color = RB_BLACK; parent->rb_color = RB_RED; __rb_rotate_left(parent, root); other = parent->rb_right; } if ((!other->rb_left || other->rb_left->rb_color == RB_BLACK) && (!other->rb_right || other->rb_right->rb_color == RB_BLACK)) { other->rb_color = RB_RED; node = parent; parent = node->rb_parent; } else { if (!other->rb_right || other->rb_right->rb_color == RB_BLACK) { register struct rb_node *o_left; if ((o_left = other->rb_left)) o_left->rb_color = RB_BLACK; other->rb_color = RB_RED; __rb_rotate_right(other, root); other = parent->rb_right; } other->rb_color = parent->rb_color; parent->rb_color = RB_BLACK; if (other->rb_right) other->rb_right->rb_color = RB_BLACK; __rb_rotate_left(parent, root); node = root->rb_node; break; } } else { other = parent->rb_left; if (other->rb_color == RB_RED) { other->rb_color = RB_BLACK; parent->rb_color = RB_RED; __rb_rotate_right(parent, root); other = parent->rb_left; } if ((!other->rb_left || other->rb_left->rb_color == RB_BLACK) && (!other->rb_right || other->rb_right->rb_color == RB_BLACK)) { other->rb_color = RB_RED; node = parent; parent = node->rb_parent; } else { if (!other->rb_left || other->rb_left->rb_color == RB_BLACK) { register struct rb_node *o_right; if ((o_right = other->rb_right)) o_right->rb_color = RB_BLACK; other->rb_color = RB_RED; __rb_rotate_left(other, root); other = parent->rb_left; } other->rb_color = parent->rb_color; parent->rb_color = RB_BLACK; if (other->rb_left) other->rb_left->rb_color = RB_BLACK; __rb_rotate_right(parent, root); node = root->rb_node; break; } } } if (node) node->rb_color = RB_BLACK; } void rb_erase(struct rb_node *node, struct rb_root *root) { struct rb_node *child, *parent; int color; if (!node->rb_left) child = node->rb_right; else if (!node->rb_right) child = node->rb_left; else { struct rb_node *old = node, *left; node = node->rb_right; while ((left = node->rb_left)) node = left; child = node->rb_right; parent = node->rb_parent; color = node->rb_color; if (child) child->rb_parent = parent; if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; } else root->rb_node = child; if (node->rb_parent == old) parent = node; node->rb_parent = old->rb_parent; node->rb_color = old->rb_color; node->rb_right = old->rb_right; node->rb_left = old->rb_left; if (old->rb_parent) { if (old->rb_parent->rb_left == old) old->rb_parent->rb_left = node; else old->rb_parent->rb_right = node; } else root->rb_node = node; old->rb_left->rb_parent = node; if (old->rb_right) old->rb_right->rb_parent = node; goto color; } parent = node->rb_parent; color = node->rb_color; if (child) child->rb_parent = parent; if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; } else root->rb_node = child; color: if (color == RB_BLACK) __rb_erase_color(child, parent, root); } /* * This function returns the first node (in sort order) of the tree. */ struct rb_node *rb_first(struct rb_root *root) { struct rb_node *n; n = root->rb_node; if (!n) return 0; while (n->rb_left) n = n->rb_left; return n; } struct rb_node *rb_next(struct rb_node *node) { /* If we have a right-hand child, go down and then left as far as we can. */ if (node->rb_right) { node = node->rb_right; while (node->rb_left) node=node->rb_left; return node; } /* No right-hand children. Everything down and left is smaller than us, so any 'next' node must be in the general direction of our parent. Go up the tree; any time the ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */ while (node->rb_parent && node == node->rb_parent->rb_right) node = node->rb_parent; return node->rb_parent; } struct rb_node *rb_prev(struct rb_node *node) { /* If we have a left-hand child, go down and then right as far as we can. */ if (node->rb_left) { node = node->rb_left; while (node->rb_right) node=node->rb_right; return node; } /* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */ while (node->rb_parent && node == node->rb_parent->rb_left) node = node->rb_parent; return node->rb_parent; } void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root) { struct rb_node *parent = victim->rb_parent; /* Set the surrounding nodes to point to the replacement */ if (parent) { if (victim == parent->rb_left) parent->rb_left = new; else parent->rb_right = new; } else { root->rb_node = new; } if (victim->rb_left) victim->rb_left->rb_parent = new; if (victim->rb_right) victim->rb_right->rb_parent = new; /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; }
(5)利用红黑树代码实现数据的插入和删除
a)定义自己的根节点和数据节点
struct _tree { int number; struct rb_root root; }; struct _data { int value; struct rb_node node; };
b)查找数据
static struct _data * rb_search_value(struct _tree * tree, int value) { struct rb_node * n = tree->root.rb_node; struct _data * pData; while (n) { pData = rb_entry(n, struct _data, node); if (value < pData->value) n = n->rb_left; else if (value > pData -> value) n = n->rb_right; else return pData; } return NULL; }
c)插入数据
static struct _data * __rb_insert_data(struct _tree* tree, int value, struct rb_node * _node) { struct rb_node ** p = &tree->root.rb_node; struct rb_node * parent = NULL; struct _data * pData; while (*p) { parent = *p; pData = rb_entry(parent, struct _data, node); if (value < pData->value) p = &(*p)->rb_left; else if (value > pData->value) p = &(*p)->rb_right; else return pData; } rb_link_node(_node, parent, p); return NULL; } static struct _data * rb_insert_data(struct _tree * tree,int value, struct rb_node * _node) { struct _data * ret; if ((ret = __rb_insert_data(tree, value, _node))) goto out; rb_insert_color(_node, &tree->root); tree->number ++; out: return ret; }
static void rb_remove_data(struct rb_node* node, struct _tree* tree) { rb_erase(node, &tree->root); tree->number --; }
e)打印数据
static void _print(struct rb_node* _node) { struct _data* pData; if(_node) { _print(_node->rb_left); pData = rb_entry(_node, struct _data, node); printf("data = %d\n", pData->value); _print(_node->rb_right); } } static void print(struct _tree * tree) { _print(tree->root.rb_node); }
f)测试数据
void test() { struct _tree root_tree = {0, RB_ROOT}; struct _data data = {10, {0}}; rb_insert_data(&root_tree, 10, &data.node); assert(root_tree.root.rb_node == &data.node); assert(1 == root_tree.number); assert(NULL == rb_prev(&data.node)); assert(NULL == rb_next(&data.node)); rb_remove_data(&data.node, &root_tree); assert(root_tree.root.rb_node == NULL); assert(0 == root_tree.number); }
相关推荐
软件随想录 软件随想录 软件随想录 软件随想录 软件随想录
"代码随想录-大厂八股文-面试" 从标题和描述中,我们可以看出这篇文章主要讲述的是代码随想录的大厂八股文面试相关知识点。下面将对这些知识点进行详细的解释和总结。 首先,代码随想录是一种常用的编程技巧,旨在...
代码随想录知识星球精华(最强⼋股⽂) 这份PDF总结了 代码随想录知识星球 的全部精华内容,覆盖了⼏乎程序员学习必备的内容。 知识星球⾥很多录友拿到了⼤⼚offer,包括科班 和 ⾮科班的,⽽他们的每⽇学习总结都是...
代码随想录-八股文 PDF 代码随想录-八股文 PDF 是一个涵盖了程序员学习必备的内容的知识星球精华,总结了包括 C++、Java、Go 在内的多种编程语言,数据结构和算法、操作系统、数据库、计算机网络、设计模式、Linux ...
代码随想录算法PDF.rar
代码随想录算法PDF.zip
代码随想录贪心算法知识,非常管用
代码随想录 面试大厂八股文 手撕代码必备神器
软件随想录全集
代码随想录的pdf版本,不知道为啥放在电脑上面光删除不掉,所以网上保存一下下!
「代码随想录」动态规划专题精讲(v1.2).pdf
付费渠道买的,请珍惜
"代码随想录知识星球精华(最强八股文)第三版" 本资源摘要信息中,我们将根据给定的文件信息,生成相关知识点。 标题和描述中的知识点 * 代码随想录知识星球精华(最强八股文)第三版:这是一个关于编程的知识...
"代码随想录二叉树专题精讲" 本资源是关于二叉树的专题讲解,涵盖了二叉树的基本概念、avl树、红黑树、堆、trie树等多种二叉树结构的实现和应用。 知识点一:二叉树的基本概念 二叉树是一种特殊的树状结构,它的每...
"代码随想录知识星球精华-大厂面试八股文v1.1.pdf" 本资源主要是关于大厂面试的八股文,涵盖了C++、Java、Go、Linux等多方面的知识点,对于程序员来说非常实用。以下是对该资源的详细知识点解析: 1. C++基础知识...
软件随想录_扫描版_5.79M
软件随想录
本文主要介绍代码随想录的刷题笔记记录,方便读者更好地利用该网站进行学习。 ## 刷题笔记记录的作用 刷题笔记记录是代码随想录提供的一个功能,用于记录用户在刷题过程中的解题思路和方法。它可以帮助用户更好地...
软件随想录.pdf 个人收集电子书,仅用学习使用,不可用于商业用途,如有版权问题,请联系删除!
计算机教育_软件随想录_给计算机专业学子的建议知识.pdf