您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

红黑树底层原理及Linux内核红黑树算法深度研究

时间:2021-06-24 10:49:23  来源:  作者:Linux天神

1. 红黑树

1.1 红黑树概述

红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL树就被放到了博物馆里,据说是红黑树有更好的效率,更高的统计性能。这一点在我们了解了红黑树的实现原理后,就会有更加深切的体会。

红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。学过数据结构的人应该都已经领教过AVL树的复杂,但AVL树的复杂比起红黑树来说简直是小巫见大巫,红黑树才是真正的变态级数据结构。

由于STL中的关联式容器默认的底层实现都是红黑树,因此红黑树对于后续学习STL源码还是很重要的,有必要掌握红黑树的实现原理和源码实现。

红黑树是AVL树的变种,红黑树通过一些着色法则确保没有一条路径会比其它路径长出两倍,因而达到接近平衡的目的。所谓红黑树,不仅是一个二叉搜索树,而且必须满足一下规则:

  •  1、每个节点不是红色就是黑色。
  •  2、根节点为黑色。
  •  3、如果节点为红色,其子节点必须为黑色。
  •  4、任意一个节点到到NULL(树尾端)的任何路径,所含之黑色节点数必须相同。

上面的这些约束保证了这个树大致上是平衡的,这也决定了红黑树的插入、删除、查询等操作是比较快速的。 根据规则4,新增节点必须为红色;根据规则3,新增节点之父节点必须为黑色。当新增节点根据二叉搜索树的规则到达其插入点时,却未能符合上述条件时,就必须调整颜色并旋转树形,如下图:

红黑树底层原理及Linux内核红黑树算法深度研究

 

假设我们为上图分别插入节点3、8、35、75,根据二叉搜索树的规则,插入这四个节点后,我们会发现它们都破坏了红黑树的规则,因此我们必须调整树形,也就是旋转树形并改变节点的颜色。

1.2 红黑树上结点的插入

在讨论红黑树的插入操作之前必须要明白,任何一个即将插入的新结点的初始颜色都为红色。这一点很容易理解,因为插入黑点会增加某条路径上黑结点的数目,从而导致整棵树黑高度的不平衡。但如果新结点的父结点为红色时(如下图所示),将会违反红黑树的性质:一条路径上不能出现相邻的两个红色结点。这时就需要通过一系列操作来使红黑树保持平衡。

红黑树底层原理及Linux内核红黑树算法深度研究

 

为了清楚地表示插入操作以下在结点中使用“新”字表示一个新插入的结点;使用“父”字表示新插入点的父结点;使用“叔”字表示“父”结点的兄弟结点;使用“祖”字表示“父”结点的父结点。插入操作分为以下几种情况:

1.2.1 黑父

如下图所示,如果新节点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。

红黑树底层原理及Linux内核红黑树算法深度研究

 

1.2.2 红父

如果新节点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。

红黑树底层原理及Linux内核红黑树算法深度研究

 

1.2.2.1 红叔

当叔父结点为红色时,如下图所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上(迭代)进行平衡操作。

红黑树底层原理及Linux内核红黑树算法深度研究

 

需要注意的是,无论“父节点”在“叔节点”的左边还是右边,无论“新节点”是“父节点”的左孩子还是右孩子,它们的操作都是完全一样的(其实这种情况包括4种,只需调整颜色,不需要旋转树形)。

1.2.2.2 黑叔

当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能:

Case 1:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 2:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 3:

红黑树底层原理及Linux内核红黑树算法深度研究

 

Case 4:

红黑树底层原理及Linux内核红黑树算法深度研究

 

可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

其实红黑树的插入操作不是很难,甚至比AVL树的插入操作还更简单些。红黑树的插入操作源代码如下:

// 元素插入操作  insert_unique()
// 插入新值:节点键值不允许重复,若重复则插入无效
// 注意,返回值是个pair,第一个元素是个红黑树迭代器,指向新增节点
// 第二个元素表示插入成功与否
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)
{
    rb_tree_node* y = header;    // 根节点root的父节点
    rb_tree_node* x = root();    // 从根节点开始
    bool comp = true;
    while(x != 0)
    {
        y = x;
        comp = key_compare(KeyOfValue()(v) , key(x));    // v键值小于目前节点之键值?
        x = comp ? left(x) : right(x);   // 遇“大”则往左,遇“小于或等于”则往右
    }
    // 离开while循环之后,y所指即插入点之父节点(此时的它必为叶节点)
    iterator j = iterator(y);     // 令迭代器j指向插入点之父节点y
    if(comp)     // 如果离开while循环时comp为真(表示遇“大”,将插入于左侧)
    {
        if(j == begin())    // 如果插入点之父节点为最左节点
            return pair<iterator , bool>(_insert(x , y , z) , true);
        else     // 否则(插入点之父节点不为最左节点)
            --j;   // 调整j,回头准备测试
    }
    if(key_compare(key(j.node) , KeyOfValue()(v) ))
        // 新键值不与既有节点之键值重复,于是以下执行安插操作
        return pair<iterator , bool>(_insert(x , y , z) , true);
    // 以上,x为新值插入点,y为插入点之父节点,v为新值
 
    // 进行至此,表示新值一定与树中键值重复,那么就不应该插入新值
    return pair<iterator , bool>(j , false);
}
 
// 真正地插入执行程序 _insert()
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)
{
    // 参数x_ 为新值插入点,参数y_为插入点之父节点,参数v为新值
    link_type x = (link_type) x_;
    link_type y = (link_type) y_;
    link_type z;
 
    // key_compare 是键值大小比较准则。应该会是个function object
    if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))
    {
        z = create_node(v);    // 产生一个新节点
        left(y) = z;           // 这使得当y即为header时,leftmost() = z
        if(y == header)
        {
            root() = z;
            rightmost() = z;
        }
        else if(y == leftmost())     // 如果y为最左节点
            leftmost() = z;          // 维护leftmost(),使它永远指向最左节点
    }
    else
    {
        z = create_node(v);        // 产生一个新节点
        right(y) = z;              // 令新节点成为插入点之父节点y的右子节点
        if(y == rightmost())
            rightmost() = z;       // 维护rightmost(),使它永远指向最右节点
    }
    parent(z) = y;      // 设定新节点的父节点
    left(z) = 0;        // 设定新节点的左子节点
    right(z) = 0;       // 设定新节点的右子节点
    // 新节点的颜色将在_rb_tree_rebalance()设定(并调整)
    _rb_tree_rebalance(z , header->parent);      // 参数一为新增节点,参数二为根节点root
    ++node_count;       // 节点数累加
    return iterator(z);  // 返回一个迭代器,指向新增节点
}
 
 
// 全局函数
// 重新令树形平衡(改变颜色及旋转树形)
// 参数一为新增节点,参数二为根节点root
inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    x->color = _rb_tree_red;    //新节点必为红
    while(x != root && x->parent->color == _rb_tree_red)    // 父节点为红
    {
        if(x->parent == x->parent->parent->left)      // 父节点为祖父节点之左子节点
        {
            _rb_tree_node_base* y = x->parent->parent->right;    // 令y为伯父节点
            if(y && y->color == _rb_tree_red)    // 伯父节点存在,且为红
            {
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色
                x = x->parent->parent;
            }
            else    // 无伯父节点,或伯父节点为黑色
            {
                if(x == x->parent->right)   // 如果新节点为父节点之右子节点
                {
                    x = x->parent;
                    _rb_tree_rotate_left(x , root);    // 第一个参数为左旋点
                }
                x->parent->color = _rb_tree_black;     // 改变颜色
                x->parent->parent->color = _rb_tree_red;
                _rb_tree_rotate_right(x->parent->parent , root);    // 第一个参数为右旋点
            }
        }
        else          // 父节点为祖父节点之右子节点
        {
            _rb_tree_node_base* y = x->parent->parent->left;    // 令y为伯父节点
            if(y && y->color == _rb_tree_red)    // 有伯父节点,且为红
            {
                x->parent->color = _rb_tree_black;           // 更改父节点为黑色
                y->color = _rb_tree_black;                   // 更改伯父节点为黑色
                x->parent->parent->color = _rb_tree_red;     // 更改祖父节点为红色
                x = x->parent->parent;          // 准备继续往上层检查
            }
            else    // 无伯父节点,或伯父节点为黑色
            {
                if(x == x->parent->left)        // 如果新节点为父节点之左子节点
                {
                    x = x->parent;
                    _rb_tree_rotate_right(x , root);    // 第一个参数为右旋点
                }
                x->parent->color = _rb_tree_black;     // 改变颜色
                x->parent->parent->color = _rb_tree_red;
                _rb_tree_rotate_left(x->parent->parent , root);    // 第一个参数为左旋点
            }
        }
    }//while
    root->color = _rb_tree_black;    // 根节点永远为黑色
}
 
 
// 左旋函数
inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    // x 为旋转点
    _rb_tree_node_base* y = x->right;          // 令y为旋转点的右子节点
    x->right = y->left;
    if(y->left != 0)
        y->left->parent = x;           // 别忘了回马枪设定父节点
    y->parent = x->parent;
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)
    if(x == root)    // x为根节点
        root = y;
    else if(x == x->parent->left)         // x为其父节点的左子节点
        x->parent->left = y;
    else                                  // x为其父节点的右子节点
        x->parent->right = y;
    y->left = x;
    x->parent = y;
}
 
 
// 右旋函数
inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
    // x 为旋转点
    _rb_tree_node_base* y = x->left;          // 令y为旋转点的左子节点
    x->left = y->right;
    if(y->right != 0)
        y->right->parent = x;           // 别忘了回马枪设定父节点
    y->parent = x->parent;
 
    // 令y完全顶替x的地位(必须将x对其父节点的关系完全接收过来)
    if(x == root)
        root = y;
    else if(x == x->parent->right)         // x为其父节点的右子节点
        x->parent->right = y;
    else                                  // x为其父节点的左子节点
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

 

2. 红黑树

linux内核红黑树的算法都定义在


linux-2.6.38.8/include/linux/rbtree.h和linux-2.6.38.8/lib/rbtree.c两个文件中。

2.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))));

这里的巧妙之处是使用成员rb_parent_color同时存储两种数据,一是其双亲结点的地址,另一是此结点的着色。__attribute__((aligned(sizeof(long))))属性保证了红黑树中的每个结点的首地址都是32位对齐的(在32位机上),也就是说每个结点首地址的bit[1]和bit[0]都是0,因此就可以使用bit[0]来存储结点的颜色属性而不干扰到其双亲结点首地址的存储。

操作rb_parent_color的函数:

#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) //设置黑色属性
 
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;
}
 

初始化新结点:

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;   //设置其双亲结点的首地址(根结点的双亲结点为NULL),且颜色属性设为黑色
    node->rb_left = node->rb_right = NULL;   //初始化新结点的左右子树
 
    *rb_link = node;  //指向新结点
}
 

指向红黑树根结点的指针:

struct rb_root
{
    struct rb_node *rb_node;
};
 
 
#define RB_ROOT (struct rb_root) { NULL, }  //初始化指向红黑树根结点的指针
#define rb_entry(ptr, type, member) container_of(ptr, type, member) //用来获得包含struct rb_node的结构体的首地址
 
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //判断树是否为空
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)  //判断node的双亲结点是否为自身
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //设置双亲结点为自身

2.2 插入

首先像二叉查找树一样插入一个新结点,然后根据情况作出相应的调整,以使其满足红黑树的颜色属性(其实质是维持红黑树的平衡)。

函数rb_insert_color使用while循环不断地判断双亲结点是否存在,且颜色属性为红色。

若判断条件为真,则分成两部分执行后续的操作:

(1)、当双亲结点是祖父结点左子树的根时,则:

a、存在叔父结点,且颜色属性为红色。

红黑树底层原理及Linux内核红黑树算法深度研究

 

b、当node是其双亲结点右子树的根时,则左旋,然后执行第c步。

红黑树底层原理及Linux内核红黑树算法深度研究

 

c、当node是其双亲结点左子树的根时。

红黑树底层原理及Linux内核红黑树算法深度研究

 

(2)当双亲结点是祖父结点右子树的根时的操作与第(1)步大致相同,这里略过不谈。

若为假,则始终设置根结点的颜色属性为黑色。

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)) //双亲结点不为NULL,且颜色属性为红色
    {
        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;  //node指向祖父结点 
                    continue; //继续下一个while循环
                }
            }
 
            if (parent->rb_right == node)  //当node是其双亲结点右子树的根时
            {
                register struct rb_node *tmp;
                __rb_rotate_left(parent, root); //左旋
                tmp = parent;  //调整parent和node指针的指向
                parent = node;
                node = tmp;
            }
 
            rb_set_black(parent); //设置双亲结点为黑色
            rb_set_red(gparent); //设置祖父结点为红色
            __rb_rotate_right(gparent, root); //右旋
        } else { // !(parent == gparent->rb_left)
            {
                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);
        } //end if (parent == gparent->rb_left)
    } //end while ((parent = rb_parent(node)) && rb_is_red(parent))
 
    rb_set_black(root->rb_node);
}

 

2.3 删除

像二叉查找树的删除操作一样,首先需要找到所需删除的结点,然后根据该结点左右子树的有无分为三种情形:

红黑树底层原理及Linux内核红黑树算法深度研究

 

若node结点的颜色属性为黑色,则需要调用__rb_erase_color函数来进行调整。

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;
    }  //end else
 
    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函数来进行调整
        __rb_erase_color(child, parent, root);
}

2.4 遍历

rb_first和rb_next函数可组成中序遍历,即以升序遍历红黑树中的所有结点。

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;
}
 
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;
}
 


Tags:红黑树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
1. 红黑树1.1 红黑树概述红黑树和我们以前学过的AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。不过自从红黑树出来后,AVL...【详细内容】
2021-06-24  Tags: 红黑树  点击:(119)  评论:(0)  加入收藏
前言本文咱们了解一下红黑树的设计,相比 jdk1.7 的 HashMap 而言,jdk1.8 最重要的就是引入了红黑树的设计,当冲突的链表长度超过 8 个的时候,链表结构就会转为红黑树结构。01、...【详细内容】
2021-01-18  Tags: 红黑树  点击:(173)  评论:(0)  加入收藏
絮叨学校短学期刚结束了,离学校开学还有很多天,一直呆在寝室玩游戏岂不是浪费了大好时光,于是心血来潮想看看HashMap的源码。虽然我没有经历过面试,但是java程序员都知道,HashMap...【详细内容】
2020-09-27  Tags: 红黑树  点击:(59)  评论:(0)  加入收藏
本文将通过图文的方式讲解红黑树的知识点,并且不会涉及到任何代码,相信我,在懂得红黑树实现原理前,看代码会一头雾水的,当原理懂了,代码也就按部就班写而已,没任何难度。 阅读本文...【详细内容】
2020-03-18  Tags: 红黑树  点击:(38)  评论:(0)  加入收藏
红黑树是二叉搜索树的增强版,我们知道优化二叉搜索树的核心是优化二叉搜索树的高度,也就是使树尽可能地平衡,红黑树就是解决这个问题的,它能够尽可能地平衡二叉搜索树的高度,保证...【详细内容】
2020-01-03  Tags: 红黑树  点击:(44)  评论:(0)  加入收藏
整篇文章的思路是这样的,红黑树其实就是一种数据结构,设计它的目的就是为了高效地进行增删改查,所以我们文章的顺序也会按照这个思路来进行。我们先从二叉查找树逐渐引入到红黑...【详细内容】
2019-09-23  Tags: 红黑树  点击:(90)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条