精华内容
下载资源
问答
  • rbtree

    2008-03-08 01:59:52
    rbtree java
  • RBTree

    2017-11-02 09:23:29
    RBTree:是一棵二叉搜索树,每个节点增加一个存储位来表示节点的颜色,通过任何一条路径的从根节点到叶子简单路径上的颜色来约束,红黑树保证了最长路径不超过最短路径的两倍,因而近乎平衡。 RBTree满足的性质:1....

     

    RBTree:是一二叉搜索树,每个节点增加一个存储位来表示节点的颜色,通过任何一条路径的从根节点到叶子简单路径上的颜色来约束,红黑树保证了最长路径不超过最短路径的两倍,因而近乎平衡。

    RBTree满足的性质:1.每个节点的颜色不是黑色就是红色

                                      2.根节点的颜色一定是黑色

                                      3.如果一个节点是红色的,则他的两个子节点是黑色的,即没有连续的红节点

                                     4.对每个节点,从该节点到其所有后代叶子结点的简单路径上,均包含相同数目的黑色节点,即每条路径的黑色节点数目相同

     

    当满足上述的性质时,红黑树自然可以保证最长的路径不超过最短路径的两倍,因为最长的路径一定是在每个黑节点后面跟了一个红节点,而最短路径一定只有黑色节点,这样就保证了上述的结论。

    最长路径:黑->红->黑->红->黑->红

    最短路径:黑->黑->黑

     

     

    为了满足上述的性质,我们再插入时,选择每次都默认插入的是红色的节点,因为我们不想破坏第四条性质,因为维护起来相当的麻烦,当你变了一条路径的黑色节点数目是有可能整棵树都要做出调整,因为你改变的这条路径可能是一条子树,那么就很麻烦了,你需要把其他所有路径的都要改变黑色数目来维护这条性质,这样的工作实在是很难,需要注意很多的地方。但是我们插入默认是红色节点也会破坏它的第三条性质,但是这里第三条的性质比起第四条还是简单了许多的,所以我们选择破坏第三条,而不是第四条。这时当我们插入红节点时就可能会出现连续的红节点这样的情况,这里我们需要做出调整来满足其第三条性质。下面是其几种情况:

    第一种情况:grandfather为黑,parent为红,uncle存在且为红,这时我们需要将parent和uncle变黑,再grandfather变红,这样就没有连续的红色节点,同时使这棵树的黑色节点数没有改变,这样就很好的使这棵RBTree得到了维护,但是我们还需要向上调整,因为这棵树可能只是一颗子树。

     

    第二种情况:cur为红,parent为红,grandfather为黑,uncle存在且为黑或者uncle不存在,parent为grandfather的左孩子,cur也是parent的左孩子,则这时需要以grandfather为轴进行一个右单旋,同时将parent变为黑grandfather变为红,这样黑色的节点数目还是没有改变的。

    uncle存在且为黑或者uncle不存在的情况:

    第三种情况:其实第二种可以说是第三种的一种特殊情况,也就是AVL的双旋和单选的问题,cur为红,parent为红,grandfather为黑,uncle存在且为黑或者uncle不存在,parent是grandfather的左孩子,cur是parent的有孩子,这是就是一双旋,现以parent为轴进行左单选,不调整颜色,再以grandfather为轴进行右单旋,同样的parent变为黑色,grandfather变为红色。

     

    上面就是RBTree破坏第三条维持第四条之后的调整部分。

    下面是我的代码部分:

     

    #pragma once
    #include<iostream>
    using namespace std;
    enum Color
    {
    	RED,
    	BLEAK,
    };
    
    template<class K,class V>
    struct RBTreeNode
    {
    	K _key;
    	V _value;
    	Color _col;
    	RBTreeNode<K, V>* _left;
    	RBTreeNode<K, V>* _right;
    	RBTreeNode<K, V>* _parent;
    
    
    	RBTreeNode(const K& key, const V& value)
    		:_left(NULL)
    		, _right(NULL)
    		, _parent(NULL)
    		, _key(key)
    		, _value(value)
    		, _col(RED)
    	{
    	}
    	
    };
    
    template<class K, class V>
    class RBTree
    {
    	typedef RBTreeNode<K, V> Node;
    public:
    	RBTree()
    		:_root(NULL)
    	{
    	}
    
    	bool Insert(const K& key,const V& value)
    	{
    		if (_root == NULL)
    		{
    			_root = new Node(key, value);
    			_root->_col = BLEAK;
    			return true;
    		}
    
    		Node *parent = NULL;
    		Node *cur = _root;
    		while (cur)
    		{
    			if (cur->_key > key)
    			{
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->_key < key)
    			{
    				parent = cur;
    				cur = cur->_right;
    			}
    			else//相同的节点插不进去
    			{
    				return false;
    			}
    		}
    		//此时的cur就是我们要找到的位置
    		cur = new Node(key,value);
    		if (parent->_key > key)
    		{
    			parent->_left = cur;
    			cur->_parent = parent;
    		}
    		else
    		{
    			parent->_right = cur;
    			cur->_parent = parent;
    		}
    
    		//到了这里我们已经插入了节点,这里开始判断是不是RBTree
    		while (parent && parent->_col == RED)
    		{
    			Node* grandfather = parent->_parent;
    
    			//如果parent是grandfather的左,那么uncle是grandfather的右
    			if (parent == grandfather->_left)
    			{
    				Node *uncle = grandfather->_right;
    				if (uncle && uncle->_col == RED)         //叔叔存在且为红
    				{
    					grandfather->_col = RED;
    					parent->_col = uncle->_col = BLEAK;
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else                                    //叔叔不存在/存在是黑色的
    				{
    					if (cur == parent->_right)
    					{
    						RotateL(parent);
    						swap(parent, cur);
    					}
    					RotateR(grandfather);
    					grandfather->_col = RED;
    					parent->_col = BLEAK;
    					break;
    				}
    
    			}
    			else  //parent=grandfather->_right
    			{
    				Node *uncle = grandfather->_left;
    				if (uncle && uncle->_col == RED)
    				{
    					grandfather->_col = RED;
    					parent->_col = uncle->_col = BLEAK;
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				else //叔叔不存在/存在是黑色的
    				{
    					if (cur == parent->_left)
    					{
    						RotateR(parent);
    						swap(parent,cur);
    					}
    					RotateL(grandfather);
    					grandfather->_col = RED;
    					parent->_col = BLEAK;
    					break;
    				}
    			}
    		}
    		//在调整后最后可能把根节点变红,所以我们在所有操作做完后,我们最后将root变为黑色
    		_root->_col = BLEAK;                       
    		return true;
    	}
    
    	//右单旋
    	void RotateR(Node *cur)
    	{
    		Node *parent = cur->_parent;
    		Node *subL = cur->_left;
    		Node *subLR = subL->_right;
    
    		if (cur == _root)
    		{
    			_root = subL;
    			subL->_parent = NULL;
    			subL->_right = cur;
    		}
    		else
    		{
    			if (cur == parent->_left)
    			{
    				parent->_left = subL;
    			}
    			else
    			{
    				parent->_right = subL;
    			}
    			subL->_parent = parent;
    			subL->_right = cur;
    		}
    
    		cur->_parent = subL;
    		cur->_left = subLR;
    
    		if (subLR)
    			subLR->_parent = cur;
    	}
    
    	//左单选
    	void RotateL(Node *cur)
    	{
    	
    		Node* parent = cur->_parent;
    		Node* subR = cur->_right;
    		Node *subRL = subR->_left;
    
    		//当cur==_root
    		if (cur == _root)
    		{
    			_root = subR;
    			subR->_parent = NULL;
    			subR->_left = cur;
    		}
    		else  //这时候有parent了
    		{
    			if (parent->_left == cur)
    			{
    				parent->_left = subR;
    			}
    			else
    			{
    				parent->_right = subR;
    			}
    			subR->_parent = parent;
    			subR->_left = cur;
    		}
    
    		cur->_right = subRL;
    		cur->_parent = subR;
    		
    		if (subRL)
    			subRL->_parent = cur;
    	}
    
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout << endl;
    	}
    	void _InOrder(Node* root)
    	{
    		if (root == NULL)
    		{
    			return;
    		}
    		_InOrder(root->_left);
    		//cout << root->_key << "->" << root->_value << " ";
    		cout << root->_key <<" ";
    
    		_InOrder(root->_right);
    
    	}
    
    	bool Isbalance()
    	{
    		size_t k = 0;
    		size_t blackNum = 0;
    		Node* cur = _root;
    		while (cur)
    		{
    			if (cur->_col == BLEAK)
    				++k;
    
    			cur = cur->_left;
    		}
    
    		return _Isbalance(_root,blackNum,k); 
    	}
    
    	bool _Isbalance(Node *root, size_t blackNum, const size_t k)   //这里blackNum不能给引用
    	{
    		//判断黑色节点是否相同
    		if (root == NULL)                                         //这里是找到空节点,不是叶子节点
    		{
    			if (blackNum == k)
    			{
    				return true;
    			}
    			else
    			{
    				cout << "黑色节点的个数不相同"<<endl;
    				return false;
    			}
    		}
    
    		if (root->_col == RED && root->_parent->_col == RED)
    		{
    			cout << "连续的红节点" << endl;
    			return false;
    		}
    		if (root->_col == BLEAK)
    			++blackNum;
    
    		//跑起来
    		return( _Isbalance(root->_left,blackNum,k)   
    			&& _Isbalance(root->_right,blackNum,k));
    	}
    protected:
    	Node* _root;
    };
    
    //测试RBTree
    void TestRBTree()
    {
    	RBTree<int, int > RBTree;
    
    	int a[] = {16,3,7,11,9,26,18,14,15};
    	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    	for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
    	{
    		RBTree.Insert(a[i], i);
    		cout << "RBTree.Isbalence() -> " << RBTree.Isbalance() << endl;
    	}
    	//RBTree.Insert(16,1);
    	//RBTree.Insert(3, 1);
    	//RBTree.Insert(7, 1);
    	//RBTree.Insert(11, 1);
    	//RBTree.Insert(9, 1);
    	//RBTree.Insert(26, 1);
    	//RBTree.Insert(18, 1);
    	//RBTree.Insert(14, 1);
    	//RBTree.Insert(15, 1);
    
    
    
    
    	RBTree.InOrder();
    }

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • rbtree2.zip

    2016-06-13 16:15:08
    linux rbtree移植
  • rbtree使用

    2016-02-02 23:59:00
    应用rbtree简单操作. 从linux内核源码中获取并修改得到. 留下备用 main.c #include <stdio.h> #include <stdlib.h> #include "rbtree.h" struct mytype { struct rb_node node; char *...

    应用rbtree简单操作.  从linux内核源码中获取并修改得到. 留下备用

    main.c

    #include <stdio.h>
    #include <stdlib.h>
    
    #include    "rbtree.h"
    
    struct mytype {
        struct rb_node node;
        char *keystring;
    };
    
    struct rb_root mytree = RB_ROOT;
    
    /** Same as binary sort tree**/
    struct mytype *my_search(struct rb_root *root, char *string)
    {
        struct rb_node *node = root->rb_node;
        while (node) {
            struct mytype *data = container_of(node, struct mytype, node);
            int result;
    
            result = strcmp(string, data->keystring);
    
            if (result < 0)
                node = node->rb_left;
            else if (result > 0)
                node = node->rb_right;
            else
                return data;
        } 
        return NULL;
    }
    
    int my_insert(struct rb_root *root, struct mytype *data)
    {
        struct rb_node **new = &(root->rb_node), *parent = NULL;
    
        /* Figure out where to put new node */
        while (*new) {
            struct mytype *this = container_of(*new, struct mytype, node);
            int result = strcmp(data->keystring, this->keystring);
    
            parent = *new;
            if (result < 0)
                new = &((*new)->rb_left);
            else if (result > 0)
                new = &((*new)->rb_right);
            else
                return 0;
        }
    
        /* Add new node and rebalance tree. */
        rb_link_node(&(data->node), parent, new);
    #if 1
        rb_insert_color(&(data->node), root);
    #endif
        return 1;
    }
    
    #if 0
    /** remove **/
    struct mytype *data = mysearch(mytree, "walrus");
    
    if (data) {
        rb_erase(data->node, mytree);
        myfree(data);
    }
    #endif
    
    #if 0
    void rb_replace_node(struct rb_node *old, struct rb_node *new,
            struct rb_root *tree);
    #endif
    
    #if 0
    struct rb_node *rb_first(struct rb_root *tree);
    struct rb_node *rb_last(struct rb_root *tree);
    struct rb_node *rb_next(struct rb_node *node);
    struct rb_node *rb_prev(struct rb_node *node);
    #endif
    
    char *array[] = {
        "aaaaa",
        "bbb",
        "333",
        "c",
        "dddd",
        "111",
        "eeeeeeeee",
        "ffffghi",
        "222",
        "gggabcd",
        "12345"
        "abcdefg"
    };
    
    #define TAB_SIZE(array) (sizeof(array)/sizeof(array[0])) 
    
    int main(int argc, char* argv[])
    {
        struct rb_node *node;
        struct mytype *mynode;
        int i;
    
        for(i = 0; i < TAB_SIZE(array); i++) {
            mynode = malloc(sizeof(struct mytype));
            mynode->keystring = (char *)array[i];
            printf("kerstring is %s\n", mynode->keystring);
            my_insert(&mytree, mynode); 
        }
    
        printf("*********** 升序 ****************************\n");
        i = 0;
        for(node = rb_first(&mytree); node; node = rb_next(node)) {
            printf("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
            i++;
        }
        printf("------------降序---------------------------\n");
        i = 0;
        for(node = rb_last(&mytree); node; node = rb_prev(node)) {
            printf("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
            i++;
        }
    
        printf("------------删除后升序---------------------------\n");
        mynode = my_search(&mytree, "eeeeeeeee");
        if(mynode) {
            rb_erase(&(mynode->node), &mytree);
            free(mynode);
            printf("Erased eeeeeeeee node !\n");
        }
    
        for(node = rb_first(&mytree); node; node = rb_next(node)) {
            printf("i = %d, key = %s\n", i, (rb_entry(node, struct mytype, node))->keystring);
            i++;
        }
    
        return  0;
    }

    rbtree.c

    /*
      Red Black Trees
      (C) 1999  Andrea Arcangeli <andrea@suse.de>
      (C) 2002  David Woodhouse <dwmw2@infradead.org>
      
      This program is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published by
      the Free Software Foundation; either version 2 of the License, or
      (at your option) any later version.
    
      This program is distributed in the hope that it will be useful,
      but WITHOUT ANY WARRANTY; without even the implied warranty of
      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      GNU General Public License for more details.
    
      You should have received a copy of the GNU General Public License
      along with this program; if not, write to the Free Software
      Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
    
      linux/lib/rbtree.c
    */
    
    //#include <linux/rbtree.h>
    //#include <linux/module.h>
    
    #include "rbtree.h"
    
    #if 0
    struct rb_node
    {
        unsigned long  rb_parent_color;
    #define    RB_RED        0
    #define    RB_BLACK    1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));
        /* The alignment might seem pointless, but allegedly CRIS needs it */
    
    struct rb_root
    {
        struct rb_node *rb_node;
    };
    
    #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
    #define rb_color(r)   ((r)->rb_parent_color & 1)
    #define rb_is_red(r)   (!rb_color(r))
    #define rb_is_black(r) rb_color(r)
    #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
    #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
    
    #endif
    
    static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    {
        rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
    }
    static inline void rb_set_color(struct rb_node *rb, int color)
    {
        rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
    }
    
    #if 0
    #define RB_ROOT    (struct rb_root) { NULL, }
    #define    rb_entry(ptr, type, member) container_of(ptr, type, member)
    
    #define RB_EMPTY_ROOT(root)    ((root)->rb_node == NULL)
    #define RB_EMPTY_NODE(node)    (rb_parent(node) == node)
    #define RB_CLEAR_NODE(node)    (rb_set_parent(node, node))
    
    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(const struct rb_node *);
    extern struct rb_node *rb_prev(const struct rb_node *);
    extern struct rb_node *rb_first(const struct rb_root *);
    extern struct rb_node *rb_last(const 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 inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                    struct rb_node ** rb_link)
    {
        node->rb_parent_color = (unsigned long )parent;
        node->rb_left = node->rb_right = NULL;
    
        *rb_link = node;
    }
    
    #endif
    
    /****************************************************************
     *
     ****************************************************************/
    static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *right = node->rb_right;
        struct rb_node *parent = rb_parent(node);
    
        if ((node->rb_right = right->rb_left))
            rb_set_parent(right->rb_left, node);
        right->rb_left = node;
    
        rb_set_parent(right, parent);
    
        if (parent)
        {
            if (node == parent->rb_left)
                parent->rb_left = right;
            else
                parent->rb_right = right;
        }
        else
            root->rb_node = right;
        rb_set_parent(node, right);
    }
    
    static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *left = node->rb_left;
        struct rb_node *parent = rb_parent(node);
    
        if ((node->rb_left = left->rb_right))
            rb_set_parent(left->rb_right, node);
        left->rb_right = node;
    
        rb_set_parent(left, parent);
    
        if (parent)
        {
            if (node == parent->rb_right)
                parent->rb_right = left;
            else
                parent->rb_left = left;
        }
        else
            root->rb_node = left;
        rb_set_parent(node, left);
    }
    
    void rb_insert_color(struct rb_node *node, struct rb_root *root)
    {
        struct rb_node *parent, *gparent;
    
        while ((parent = rb_parent(node)) && rb_is_red(parent))
        {
            gparent = rb_parent(parent);
    
            if (parent == gparent->rb_left)
            {
                {
                    register struct rb_node *uncle = gparent->rb_right;
                    if (uncle && rb_is_red(uncle))
                    {
                        rb_set_black(uncle);
                        rb_set_black(parent);
                        rb_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }
    
                if (parent->rb_right == node)
                {
                    register struct rb_node *tmp;
                    __rb_rotate_left(parent, root);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
    
                rb_set_black(parent);
                rb_set_red(gparent);
                __rb_rotate_right(gparent, root);
            } else {
                {
                    register struct rb_node *uncle = gparent->rb_left;
                    if (uncle && rb_is_red(uncle))
                    {
                        rb_set_black(uncle);
                        rb_set_black(parent);
                        rb_set_red(gparent);
                        node = gparent;
                        continue;
                    }
                }
    
                if (parent->rb_left == node)
                {
                    register struct rb_node *tmp;
                    __rb_rotate_right(parent, root);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }
    
                rb_set_black(parent);
                rb_set_red(gparent);
                __rb_rotate_left(gparent, root);
            }
        }
    
        rb_set_black(root->rb_node);
    }
    //EXPORT_SYMBOL(rb_insert_color);
    
    static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
                     struct rb_root *root)
    {
        struct rb_node *other;
    
        while ((!node || rb_is_black(node)) && node != root->rb_node)
        {
            if (parent->rb_left == node)
            {
                other = parent->rb_right;
                if (rb_is_red(other))
                {
                    rb_set_black(other);
                    rb_set_red(parent);
                    __rb_rotate_left(parent, root);
                    other = parent->rb_right;
                }
                if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                    (!other->rb_right || rb_is_black(other->rb_right)))
                {
                    rb_set_red(other);
                    node = parent;
                    parent = rb_parent(node);
                }
                else
                {
                    if (!other->rb_right || rb_is_black(other->rb_right))
                    {
                        rb_set_black(other->rb_left);
                        rb_set_red(other);
                        __rb_rotate_right(other, root);
                        other = parent->rb_right;
                    }
                    rb_set_color(other, rb_color(parent));
                    rb_set_black(parent);
                    rb_set_black(other->rb_right);
                    __rb_rotate_left(parent, root);
                    node = root->rb_node;
                    break;
                }
            }
            else
            {
                other = parent->rb_left;
                if (rb_is_red(other))
                {
                    rb_set_black(other);
                    rb_set_red(parent);
                    __rb_rotate_right(parent, root);
                    other = parent->rb_left;
                }
                if ((!other->rb_left || rb_is_black(other->rb_left)) &&
                    (!other->rb_right || rb_is_black(other->rb_right)))
                {
                    rb_set_red(other);
                    node = parent;
                    parent = rb_parent(node);
                }
                else
                {
                    if (!other->rb_left || rb_is_black(other->rb_left))
                    {
                        rb_set_black(other->rb_right);
                        rb_set_red(other);
                        __rb_rotate_left(other, root);
                        other = parent->rb_left;
                    }
                    rb_set_color(other, rb_color(parent));
                    rb_set_black(parent);
                    rb_set_black(other->rb_left);
                    __rb_rotate_right(parent, root);
                    node = root->rb_node;
                    break;
                }
            }
        }
        if (node)
            rb_set_black(node);
    }
    
    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) != NULL)
                node = left;
    
            if (rb_parent(old)) {
                if (rb_parent(old)->rb_left == old)
                    rb_parent(old)->rb_left = node;
                else
                    rb_parent(old)->rb_right = node;
            } else
                root->rb_node = node;
    
            child = node->rb_right;
            parent = rb_parent(node);
            color = rb_color(node);
    
            if (parent == old) {
                parent = node;
            } else {
                if (child)
                    rb_set_parent(child, parent);
                parent->rb_left = child;
    
                node->rb_right = old->rb_right;
                rb_set_parent(old->rb_right, node);
            }
    
            node->rb_parent_color = old->rb_parent_color;
            node->rb_left = old->rb_left;
            rb_set_parent(old->rb_left, node);
    
            goto color;
        }
    
        parent = rb_parent(node);
        color = rb_color(node);
    
        if (child)
            rb_set_parent(child, 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);
    }
    //EXPORT_SYMBOL(rb_erase);
    
    /*
     * This function returns the first node (in sort order) of the tree.
     */
    struct rb_node *rb_first(const struct rb_root *root)
    {
        struct rb_node    *n;
    
        n = root->rb_node;
        if (!n)
            return NULL;
        while (n->rb_left)
            n = n->rb_left;
        return n;
    }
    //EXPORT_SYMBOL(rb_first);
    
    struct rb_node *rb_last(const struct rb_root *root)
    {
        struct rb_node    *n;
    
        n = root->rb_node;
        if (!n)
            return NULL;
        while (n->rb_right)
            n = n->rb_right;
        return n;
    }
    //EXPORT_SYMBOL(rb_last);
    
    struct rb_node *rb_next(const struct rb_node *node)
    {
        struct rb_node *parent;
    
        if (rb_parent(node) == node)
            return NULL;
    
        /* 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 (struct rb_node *)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 ((parent = rb_parent(node)) && node == parent->rb_right)
            node = parent;
    
        return parent;
    }
    //EXPORT_SYMBOL(rb_next);
    
    struct rb_node *rb_prev(const struct rb_node *node)
    {
        struct rb_node *parent;
    
        if (rb_parent(node) == node)
            return NULL;
    
        /* 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 (struct rb_node *)node;
        }
    
        /* No left-hand children. Go up till we find an ancestor which
           is a right-hand child of its parent */
        while ((parent = rb_parent(node)) && node == parent->rb_left)
            node = parent;
    
        return parent;
    }
    //EXPORT_SYMBOL(rb_prev);
    
    void rb_replace_node(struct rb_node *victim, struct rb_node *new,
                 struct rb_root *root)
    {
        struct rb_node *parent = rb_parent(victim);
    
        /* 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)
            rb_set_parent(victim->rb_left, new);
        if (victim->rb_right)
            rb_set_parent(victim->rb_right, new);
    
        /* Copy the pointers/colour from the victim to the replacement */
        *new = *victim;
    }
    //EXPORT_SYMBOL(rb_replace_node);

    rbtree.h

    #ifndef    __PRBTREE_H__
    #define    __PRBTREE_H__
    
    //#include "ptype.h"
    
    #ifndef NULL
        #if defined(__cplusplus)
            #define NULL 0
        #else
            #define NULL ((void *)0)
        #endif
    #endif
    
    #ifdef __compiler_offsetof
    #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
    #else
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    #endif
    
    #define container_of(ptr, type, member) ({            \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})
    
    #if 1
    struct rb_node
    {
        unsigned long  rb_parent_color;
    #define    RB_RED        0
    #define    RB_BLACK    1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
    } __attribute__((aligned(sizeof(long))));
        /* The alignment might seem pointless, but allegedly CRIS needs it */
    
    struct rb_root
    {
        struct rb_node *rb_node;
    };
    
    //#define RB_ROOT    (struct rb_root) {NULL, 0}
    #define RB_ROOT    (struct rb_root) {NULL}
    
    
    #endif
    
    #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
    #define rb_color(r)   ((r)->rb_parent_color & 1)
    #define rb_is_red(r)   (!rb_color(r))
    #define rb_is_black(r) rb_color(r)
    #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
    #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
    
    #if 0
    static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    {
        rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
    }
    static inline void rb_set_color(struct rb_node *rb, int color)
    {
        rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
    }
    #endif
    
    #define    rb_entry(ptr, type, member) container_of(ptr, type, member)
    
    #define RB_EMPTY_ROOT(root)    ((root)->rb_node == NULL)
    #define RB_EMPTY_NODE(node)    (rb_parent(node) == node)
    #define RB_CLEAR_NODE(node)    (rb_set_parent(node, node))
    
    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(const struct rb_node *);
    extern struct rb_node *rb_prev(const struct rb_node *);
    extern struct rb_node *rb_first(const struct rb_root *);
    extern struct rb_node *rb_last(const 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 inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                    struct rb_node ** rb_link)
    {
        node->rb_parent_color = (unsigned long )parent;
        node->rb_left = node->rb_right = NULL;
    
        *rb_link = node;
    }
    
    #endif    /* _LINUX_RBTREE_H */

    编译链接执行, 输出如下:

     

    转载于:https://www.cnblogs.com/zhanglong71/p/5178796.html

    展开全文
  • Linux 内核中提供了一个通用红黑树的实现(位于文件rbtree.h、rbtree.c和rbtree.txt),这里是ubuntu内核5.2.2版本的源码,用于算法研究和移植使用。
  • 红黑树RBTree

    2018-02-06 09:15:12
    #pragma once //简单方法实现红黑树的插入以及删除(并...class RBTree; typedef enum{RED=0,BLACK}COLOR; template class RBNode { friend class RBTree; public: RBNode():data(Type()),leftChild(NULL),rightChi
    #pragma once
    //简单方法实现红黑树的插入以及删除(并调整红黑树平衡)
    template<class Type>
    class RBTree;
    
    typedef enum{RED=0,BLACK}COLOR;
    template <class Type>
    class RBNode
    {
    	friend class RBTree<Type>;
    public:
    	RBNode():data(Type()),leftChild(NULL),rightChild(NULL),parent(NULL),color(RED)
    	{}
    	RBNode(Type d,RBNode<Type>* left=NULL,RBNode<Type>* right = NULL,RBNode<Type>* pr = NULL)
    		:data(d),leftChild(left),rightChild(right),parent(pr),color(RED)
    	{}
    	~RBNode()
    	{}
    private:
    
    	Type data;
    	RBNode<Type>* leftChild;
    	RBNode<Type>* rightChild;
    	RBNode<Type>* parent;//追踪当前父节点
    	COLOR color;
    };
    
    template<class Type>
    class RBTree
    {
    public:
    	RBTree():root(NULL)
    	{}
    	~RBTree()
    	{}
    public:
    	bool insert(const Type &x)
    	{
    		return insert(root,x);
    	}
    	bool remove(const Type& key)
    	{
    		remove(root,key);
    	}
    protected:
    	bool remove(RBNode<Type> *&t,const Type& key)//删除节点
    	{
    		RBNode<Type> *p = t;
    		while(p!=NULL)
    		{
    			if(key == p->data)
    				return false;
    			if(key < p->data)
    				p = p->leftChild;
    			else
    				p = p->rightChild;
    		}
    		if(p == NULL)
    			return false;
    		
    		if(p->leftChild!=NULL && p->rightChild!=NULL)
    		{
    			RBNode<Type>* q = p->leftChild;
    			while(q->rightChild!=NULL)
    				q=q->rightChild;
    			p->data = q->data;
    			p = q;//p指向要删除的结点
    
    		}
    		RBNode<Type>* u;
    		if(p->leftChild!=NULL)
    			u = p->leftChild;
    		else
    			u = p->rightChild;
    		if(u!=NULL)
    		{
    			u->parent = p->parent;
    		}
    		if(p->parent->leftChild == p)
    			p->parent->leftChild = u;
    		else
    			p->parent->rightChild = u;
    		///
    		if(p->color == BLACK)
    			_Delete_fixup(t,u);
    		delete p;
    		return true;
    	}
    	void _Delete_fixup(RBNode<Type> *&t,RBNode<Type> *u)
    	{
    
    	}
    	bool insert(RBNode<Type> *&t,const Type &v)//插入节点
    	{
    		RBNode<Type>* p = t;
    		RBNode<Type>* pr= NULL;
    			while(p!=NULL)
    		{
    			if(p->data == v)
    				return false;
    			pr = p;
    			if(p->data > v)
    				p = p->leftChild;
    			else
    				p = p->rightChild;
    		}
    		RBNode<Type>* x = new RBNode<Type> (v);
    		x->parent = pr;
    		if(pr == NULL)
    		{
    			t= x;
    			x->color = BLACK;
    			return true;
    		}
    		if(pr->data > x->data)
    			pr->leftChild = x;
    		else
    			pr->rightChild = x;
    		_Insert_fixup(t,x);//用于调整红黑树平衡
    		return true;
    	}
    protected:
    	void _Insert_fixup(RBNode<Type> *&t,RBNode<Type> *x)//用于调整红黑树平衡
    	{
    		RBNode<Type> *s = NULL;//当前x节点的伯父结点
    		while(x->parent->color == RED)
    		{
    			if(x->parent == x->parent->parent->leftChild)
    			{
    				s = x->parent->parent->rightChild;
    				if((x==x->parent->leftChild&&s==NULL) || (x==x->parent->leftChild&&s!=NULL&&s->color==BLACK))
    					//x为外侧插入(左)
    				{
    					//情况1.改变P与G颜色,G右旋转
    					x->parent->color = BLACK;
    					s->parent->color = RED;
    					RotateR(s->parent);//右转
    				}
    				else if((x==x->parent->rightChild&&s==NULL) ||(x==x->parent->rightChild&&s!=NULL&&s->color==BLACK))
    				{
    					//情况2.改变G与X颜色,先左后右旋转
    					x->color=BLACK;
    					x->parent->parent->color = RED;
    					RotateL(x->parent);
    					RotateR(x->parent);
    				}
    				else if(x==x->parent->leftChild&&s!=NULL&&s->color==RED)
    				{
    					//情况3.S为RED
    					x->color = BLACK;
    					RotateR(x->parent->parent);
    					//情况4.GG结点颜色如果是红色,得继续向上走,继续转换
    					if(x->parent->parent!=NULL&&x->parent->parent->color == RED)
    					{
    						x = x->parent;
    						continue;//继续while循环,调整红黑树平衡
    
    					}
    				}
    				break;
    			}
    			else//(x->parent = x->parent->parent->rightChild)与上分支是成镜像的
    			{
    				s = x->parent->parent->leftChild;
    				if((x == x->parent->rightChild&&s==NULL) || (x==x->parent->rightChild&&s!=NULL&s->color ==BLACK))
    				{
    					//x为外侧插入,右转,改变P与G颜色
    					x->parent->color = BLACK;
    					x->parent->parent->color = RED;
    					RotateL(x->parent->parent);
    				}
    				else if((x==x->parent->leftChild&&s==NULL) || (x==x->parent->leftChild&&s!=NULL&&s->color==BLACK))
    				{
    					//x为内侧插入,先右后左插入,改变G与X颜色
    					x->parent->parent->color = RED;
    					x->color = BLACK;
    					RotateR(x->parent);
    					RotateL(x->parent);
    				}
    				else if(x==x->parent->rightChild&&s!=NULL&&s->color==RED)
    				{
    					
    					x->color = BLACK;
    					RotateL(x->parent->parent);
    					//GG结点为红色的情况
    					if(x->parent->parent!=NULL&&s->parent->parent->color==RED)
    					{
    						x = s->parent;
    						continue;
    					}
    				}
    				break;
    			}
    		}
    		t->color = BLACK;
    	}
    protected:
    	void RotateR(RBNode<Type>* ptr)
    	{
    		RBNode<Type>* subR = ptr;
    		ptr = subR->leftChild;
    
    		if(ptr->rightChild!=NULL)
    			ptr->rightChild->parent=subR;
    		ptr->parent = subR->parent;
    
    		if(subR->parent == NULL)
    		{
    			root = ptr;
    		}
    		else
    		{
    			//链接GG结点
    			if(subR == subR->parent->leftChild)
    				subR->parent->leftChild = ptr;
    			else
    				subR->parent->rightChild = ptr;
    		}
    
    		subR->leftChild = ptr->rightChild;
    		ptr->rightChild = subR;
    		subR->parent = ptr;
    
    	}
    	void RotateL(RBNode<Type>* ptr)
    	{
    		RBNode<Type>* subL = ptr;
    		ptr = subL->rightChild;
    		subL->rightChild = ptr->leftChild;
    
    		if(ptr->rightChild!=NULL)
    			ptr->leftChild->parent = subL;
    		ptr->parent = subL->parent;
    		if(subL->parent==NULL)
    		{
    			root = ptr;
    		}
    		else
    		{
    			//链接GG结点
    			if(subL == subL->parent->leftChild)
    				subL->parent->leftChild = ptr;
    			else
    				subL->parent->rightChild = ptr; 
    		}
    	  
          ptr->leftChild = subL;
    	  subL->parent = ptr;
    		
    	}
    private:
    	RBNode<Type>* root;
    
    };

    展开全文
  • Linux kernel rbtree

    2018-01-16 18:35:00
    Linux kernel rbtree 因编写内核模块时需要用到rbtree来记录异步request,研究分析了一下kernel rbtree的使用方法,记录于此。本文主要参考了内核文档rbtree.txt rbtree简介 Red-black trees(rbtree)是一种自平衡...

    Linux kernel rbtree

    因编写内核模块时需要用到rbtree来记录异步request,研究分析了一下kernel rbtree的使用方法,记录于此。本文主要参考了内核文档rbtree.txt

    rbtree简介

    Red-black trees(rbtree)是一种自平衡的二叉搜索树,用于存储可分类的key/value数据对。它不同于radix trees或者hash tables。
    radix trees用于有效存储稀疏数组(使用长整型索引进行节点的插入、查询和删除),其索引值太大无法用数组直接存储。
    hash tables用于散列索引缩小查询的范围,但它没有做排序,因此不能快速的定位。

    Red-black trees和AVL trees很相似,但是提供了最坏情况下更快的实时插入和删除性能。插入最多2次rotations、删除最多3次rotations即可完成tree的重平衡。不过相比AVL trees,其查询时间稍慢(O(log n))。

    Linux内核大量使用rbtree,如:I/O调度算法deadline和CFQ使用rbtree来跟踪request;高精度定时器代码使用rbtree来组织定时任务;ext3文件系统使用rbtree来跟踪目录entry;等等。

    rbtree使用方法

    内核rbtree的实现在文件"lib/rbtree.c",使用rbtree需要包含头文件:

    #include <linux/rbtree.h>

    为了提高性能,linux rbtree比传统的tree实现了更少的中间层。rbtree的节点结构体struct rb_node直接嵌入到使用者的data structure(传统的方法是通过指针指向了data structure)。rbtree的插入和查询函数由使用者通过调用linux rbtree提供的基础函数自己实现(传统的方法是提供回调函数指针)。并且btree的锁也由使用者自己管理。

    创建rbtree

    在data数据结构里定义struct rb_node:

    struct mytype {
        struct rb_node node;
        char *keystring;
    };

    当处理rbtree的节点时,通过container_of()宏定义找到data数据结构指针。keystring为rbtree的key,可以定义为字符串或者整型,它将用于用户自定义的排序和查找。

    然后定义rbtree的root节点:

    struct rb_root mytree = RB_ROOT;

    查找rbtree

    使用者自己实现rbtree的查找函数,通过如下方法:从root开始,比较key的值,然后根据需要查找left节点或者right节点。

    struct mytype *my_search(struct rb_root *root, char *string)
    {
        struct rb_node *node = root->rb_node;
        while (node) {
            struct mytype *data = container_of(node, struct mytype, node);
            int result;
            result = strcmp(string, data->keystring);
            if (result < 0)
                node = node->rb_left;
            else if (result > 0)
                node = node->rb_right;
            else
                return data;
        }
        return NULL;
    }

    插入新节点

    使用者自己实现rbtree的插入函数,先找到插入的位置(该位置为NULL),然后插入新的节点并执行rbtree的重平衡。在查找到插入位置时,需要其parent节点的link用于rbtree的重平衡。

    int my_insert(struct rb_root *root, struct mytype *data)
    {
        struct rb_node **new = &(root->rb_node), *parent = NULL;
        /* Figure out where to put new node */
        while (*new) {
            struct mytype *this = container_of(*new, struct mytype, node);
            int result = strcmp(data->keystring, this->keystring);
            parent = *new;
            if (result < 0)
                new = &((*new)->rb_left);
            else if (result > 0)
                new = &((*new)->rb_right);
            else
                return FALSE;
        }
        /* Add new node and rebalance tree. */
        rb_link_node(&data->node, parent, new);
        rb_insert_color(&data->node, root);
        return TRUE;
    }

    删除/覆盖节点

    通过如下函数删除和覆盖一个节点:

    void rb_erase(struct rb_node *victim, struct rb_root *tree);
    void rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *tree);

    覆盖一个节点并不会重平衡rbtree,因此必须保证new和old的key是一样的,否者会导致异常。
    删除一个节点代码示例:

    struct mytype *data = mysearch(&mytree, "walrus");
    if (data) {
        rb_erase(&data->node, &mytree);
        myfree(data);
    }

    按顺序遍历rbtree

    如下4个函数用于顺序遍历rbtree:

    struct rb_node *rb_first(struct rb_root *tree);
    struct rb_node *rb_last(struct rb_root *tree);
    struct rb_node *rb_next(struct rb_node *node);
    struct rb_node *rb_prev(struct rb_node *node);

    代码示例:

    struct rb_node *node;
    for (node = rb_first(&mytree); node; node = rb_next(node))
        printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

    转载于:https://www.cnblogs.com/jimbo17/p/8298163.html

    展开全文
  • ISS code RBTree

    2019-12-09 21:30:17
    以下根据ISS code RBTree实现总结,点击可以放大
  • rbtree 红黑树源码 c++ stl的map与set其底层都是以红黑树为支撑。这里实现了红黑树的插入,删除算法。以及插入及删除后引起的不满足红黑树属质所做的调整算法。 代码中有具体的注释信息。
  • rbtree:Go的红黑树-源码

    2021-05-04 02:46:14
    rbtree 请参阅分支以获取有争议的红黑树。 软件包rbtree实现了“算法简介”中引入的红黑树。 在当前语言规范下,有以下模式可以实现通用容器: 排序包使用的模式 type Interface interface { Compare ( ...
  • nginx之ngx_rbtree

    2020-08-12 21:10:35
    nginx实现了一个红黑树的容器提供使用,定义在ngx_rbtree里面,这个容器相对简单,提供了插入,删除,初始化等方法。 ngx_rbtree.h: //ngx_rbtree_key为unsigned int或者int类型 typedef ngx_uint_t ngx_rbtree_key_...
  • RBTree——红黑树

    2018-07-28 18:23:35
    RBTree RBTree:红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子简单路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,因而...
  • 认识红黑树RBTree

    2020-12-24 23:23:00
    红黑树RBTree—早有耳闻。之前大学学数据结构的时候,学了平衡二叉树,红黑树不太有印象,工作中没有需要自己开发,也就没有细去了解,本来想等有需要自己写的时候再看,今天忍不住,还是去查了些资料了解了解,也挺...
  • RBTree on Linux

    2013-06-23 15:27:50
    linux下内核中本来就有rbtree的实现。在做语义分析的时候,完全可以将所有的符号表组织成一个红黑树。   以下复制于linux内核中的rbtree.h以及rbtree.c   rbtree.h   #ifndef _LINUX_RBTREE_H #define _...
  • 11.数据结构RBTree

    2021-07-16 23:27:44
    RBTree ​ 红黑树是一种适度平衡的二叉搜索树,排列规则有利于插入和查找,并且会自动保持平衡。没有任何分支过深。 ​ 是一种半线性结构,按照正常的遍历规则,得到的是排序状态(sorted) ​ 不应该使用迭代器去修改...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,477
精华内容 2,590
关键字:

rbtree