程序员经验分享-hwhale

自平衡linux红黑树

2023-05-16

简介

实际应用中的自平衡搜索二叉树，除了AVL之外，红黑树也是备受宠爱。他不仅是linux中非线性结构的标准算法，而且是Java中TreeMap、TreeSet机制、C++中的STL这些经典工具背后的强大逻辑支撑。

与AVL不同，红黑树并不追求“绝对的平衡”，在毫无平衡性的BST和绝对平衡的AVL之间，红黑树聪明的做了折中，它的左右子树的高度差可以大于1，但任何一棵子树的高度不会大于另一棵兄弟子树高度的两倍。

正是红黑树放弃了AVL的绝对平衡的苛刻要求，让它获得了更加完美的性能表现。
复杂的逻辑并不意味着效率低，事实上红黑树的插入、删除、旋转、查找等操作都被控制在O（log2n）之中，对数级别的时间复杂度，使得红黑树尤其适用于数据无序程度高、数据量庞大且需要快速定位节点的场合。

AVL树是用树的高度差不大1这个绝对的条件来保证整棵树的平衡性的，而红黑树又是靠什么来保持二叉树的平衡性的？答案如下：
（1）树中的节点都是有颜色的，要么是红色，要么是黑色
（2）树的根节点是黑色的
（3）空节点的颜色算是黑色
（4）不能有连续的红色节点
（5）从任意一个节点开始到叶子的路径包含的黑色节点的个数相等
如果一棵二叉树满足以上条件，就会使得它不可能出现：一条路径的长度是另一条路径的两倍以上。

树的节点成员如下：

typedef struct _tree_node
{
	tn_datatype data;
	struct _tree_node *lchild;	//左孩子指针
	struct _tree_node *rchild;	//右孩子指针
	
	int height;	//树的高度
	
	struct _tree_node *parent;	//指向父节点的指针
	int color;	//节点的颜色
#endif

对比AVL的节点设计，我们增加了树的父节点指针和颜色成员color，以及以该节点为根的子树的高度。

下面给出红黑树的算法实现。

算法实现

红黑树的公共操作文件rb_common.c，该文件主要提供旋转操作的接口，比如左旋、右旋、左右旋、右左旋，源代码如下：

rb_common.c

//

//  Description: 红黑树的各种算法
//
//

#ifndef RB
#define RB
#endif

#include "drawtree.h"
#include "head4tree.h"
#include "head4rb.h"


// ================= 3，旋转操作 ================ //

void rb_rotate_left(linktree *proot, linktree n)
{
	linktree gp = grandparent(n);
	linktree p = n->parent;


	p->rchild = n->lchild;
	if(n->lchild != NULL)
		n->lchild->parent = p;


	n->lchild = p;
	p->parent = n;


	if(*proot == p)
		*proot = n;


	n->parent = gp;
	if(gp != NULL)
	{
		if(p == gp->lchild)
			gp->lchild = n;
		else
			gp->rchild = n;
	}
}

void rb_rotate_right(linktree *proot, linktree n)
{
	linktree gp = grandparent(n);
	linktree p = n->parent;

	p->lchild = n->rchild;
	if(n->rchild != NULL)
		n->rchild->parent = p;

	n->rchild = p;
	p->parent = n;

	if(*proot == p)
		*proot = n;

	n->parent = gp;

	if(gp != NULL)
	{
		if(p == gp->lchild)
			gp->lchild = n;
		else
			gp->rchild = n;
	}
}

void rb_rotate_leftright(linktree *proot, linktree n)
{
	rb_rotate_left (proot, n);
	rb_rotate_right(proot, n);
}

void rb_rotate_rightleft(linktree *proot, linktree n)
{
	rb_rotate_right(proot, n);
	rb_rotate_left (proot, n);
}

红黑树节点插入算法实现源码如下rb_insert.c：

//
//  Description: 红黑树节点添加算法实现源码
//
//

#ifndef RB
#define RB
#endif

#include "drawtree.h"
#include "head4tree.h"
#include "head4rb.h"

void insert_fixup(linktree *proot, linktree new)
{
	if(new->parent == NULL)
	{
		new->color = BLACK;
		*proot = new;
		return;
	}

	if(new->parent->color == BLACK) // 1: 黑父
		return;
	else
		insert_case1(proot, new);
}

void insert_case1(linktree *proot, linktree new)
{
	if(uncle(new) != NULL && uncle(new)->color == RED) // 2: 红父 + 红叔
	{
		new->parent->color = BLACK;
		uncle(new)->color = BLACK;
		grandparent(new)->color = RED;

		insert_fixup(proot, grandparent(new));
	}
	else
		insert_case2(proot, new);
}


void insert_case2(linktree *proot, linktree new) // 3: 红父 + 黑叔
{

	if(new == new->parent->rchild &&
			new->parent == grandparent(new)->lchild)
	{
		rb_rotate_left(proot, new);
		new = new->lchild;
	}

	else if(new == new->parent->lchild &&
			new->parent == grandparent(new)->rchild)
	{
		rb_rotate_right(proot, new);
		new = new->rchild;
	}

	insert_case3(proot, new);
}


void insert_case3(linktree *proot, linktree new) // 3: 红父 + 黑叔
{
	new->parent->color = BLACK;
	grandparent(new)->color = RED;

	if(new == new->parent->lchild &&
			new->parent == grandparent(new)->lchild)
	{
		rb_rotate_right(proot, new->parent);
	}
	else
		rb_rotate_left(proot, new->parent);
}

linktree bst_insert(linktree root, linktree new)
{
	if(root == NULL)
		return new;

	new->parent = root;
	if(new->data < root->data)
	{
		root->lchild = bst_insert(root->lchild, new);
	}

	else if(new->data > root->data)
	{
		root->rchild = bst_insert(root->rchild, new);
	}
	else
	{
		printf("%d exist.\n", new->data);
	}

	return root;
}

void rb_insert(linktree *proot, linktree new)
{
	*proot = bst_insert(*proot, new);
	insert_fixup(proot, new);
}

红黑树节点删除算法实现源码如下rb_delete.c：

//

//  Description: 红黑树节点删除算法实现源码
//

//

#ifndef RB
#define RB
#endif

#include "drawtree.h"
#include "head4tree.h"
#include "head4rb.h"

linktree rb_find(linktree root, tn_datatype data)
{
	if(root == NULL)
		return NULL;

	if(data < root->data)
		return rb_find(root->lchild, data);
	else if(data > root->data)
		return rb_find(root->rchild, data);

	return root;
}

void delete_fixup(linktree *proot, linktree new, linktree parent)
{
	printf("%s\n", __FUNCTION__);

	linktree ln, rn; // left nephew & right nephew
	linktree s, gp;  // sibling & grandparent
	ln = rn = s = gp = NULL;

	if(new == NULL && parent == NULL) // 原来的old是树都唯一节点
	{
		*proot = NULL;
		return;
	}
	else if(new != NULL && parent == NULL) // 原来的old是根节点
	{
		*proot = new;
		return;
	}
	else if(parent != NULL)
	{
		s = parent->lchild ? parent->lchild : parent->rchild;
		gp = parent->parent;

		if(s != NULL)
		{
			ln = s->lchild;
			rn = s->rchild;
		}
	}

	//1，红兄
	if(Color(s) == RED)
	{
		if(new == parent->lchild)
		{
			rb_rotate_left(proot, s);
			parent->color = RED;
			s->color = BLACK;

			delete_fixup(proot, new, parent);
		}
		if(new == parent->rchild)
		{
			rb_rotate_right(proot, s);
			parent->color = RED;
			s->color = BLACK;

			delete_fixup(proot, new, parent);
		}
	}

	//2，黑兄
	if(Color(s) == BLACK)
	{

		//2.1，黑兄，二黑侄，红父
		if(Color(parent) == RED &&
		   Color(ln) == BLACK &&
		   Color(rn) == BLACK)
		{
			parent->color = BLACK;
			if(s != NULL)
				s->color = RED;
			return;
		}

		//2.2，黑兄，二黑侄，黑父
		if(Color(parent) == BLACK &&
		   Color(ln) == BLACK &&
		   Color(rn) == BLACK)
		{
			if(s != NULL)
			{
				s->color = RED;
			}

			delete_fixup(proot, parent, parent->parent);
		}

		//2.3，黑兄，同边红侄（同为左孩子）
		if(Color(ln) == RED && new == parent->lchild)
		{
			rb_rotate_right(proot, ln);
			rb_rotate_left(proot, ln);

			ln->color = parent->color;
			parent->color = BLACK;
		}
		// (同为右孩子)
		else if(Color(rn) == RED && new == parent->rchild)
		{
			rb_rotate_left(proot, rn);
			rb_rotate_right(proot, rn);

			rn->color = parent->color;
			parent->color = BLACK;
		}
		// 对边红侄(左右)
		else if(Color(ln) == RED && new == parent->rchild)
		{
			rb_rotate_right(proot, s);
			s->color = parent->color;

			parent->color = BLACK;
			ln->color = BLACK;
		}
		// 对边红侄(右左)
		else if(Color(rn) == RED && new == parent->lchild)
		{
			rb_rotate_left(proot, s);
			s->color = parent->color;

			parent->color = BLACK;
			rn->color = BLACK;
		}
	}
}

void real_delete(linktree *proot, linktree old)
{
	printf("%s\n", __FUNCTION__);

	// old不可能为NULL，new可能为NULL
	linktree new = old->lchild ? old->lchild : old->rchild;
	linktree parent = old->parent;

	if(old->parent != NULL)
	{
		if(old == old->parent->lchild)
			old->parent->lchild = new;
		else
			old->parent->rchild = new;

		old->parent = NULL;
	}
	if(new != NULL)
		new->parent = old->parent;


	if(Color(old) == BLACK && Color(new) == RED)
	{
		new->color = BLACK;
	}
	else if(Color(old) == BLACK && Color(new) == BLACK)
	{
		delete_fixup(proot, new, parent);
	}

	free(old);
}

void rb_delete(linktree *proot, tn_datatype data)
{
	linktree tmp = rb_find(*proot, data);
	if(tmp == NULL)
	{
		printf("%d is NOT exist.\n", data);
		return;
	}

	linktree n = tmp;
	if(tmp->lchild != NULL)
	{
		n = tmp->lchild;
		for(;n->rchild != NULL; n = n->rchild);
		tmp->data = n->data;
	}
	else if(tmp->rchild != NULL)
	{
		n = tmp->rchild;
		for(;n->lchild != NULL; n = n->lchild);
		tmp->data = n->data;
	}

	real_delete(proot, n); // n has ONE red-child at most
}

上述算法实现用到的头文件如下所示：

commonheader.h

#ifndef _COMMONHEADER_H_
#define _COMMONHEADER_H_

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>
#include <strings.h>
#include <time.h>
#include <errno.h>

#include <sys/stat.h>
#include <sys/types.h>
#include <fcntl.h>

#include <sys/ipc.h>
#include <sys/sem.h>
#include <sys/shm.h>
#include <sys/msg.h>
#include <semaphore.h>
#include <fcntl.h>

#include <pthread.h>

#endif

head4queue.h

//
//  Description: 本文件为队列核心头文件。
//               任何使用本队列算法的程序，在包含本头文件之前都需要
//               将如下宏定义成队列节点需要表达的数据类型：
//
//                     QUEUE_NODE_DATATYPE
//
//               否则队列的节点数据类型一律默认为 int
//

#ifndef _HEAD4QUEUE_H__
#define _HEAD4QUEUE_H__

#include "commonheader.h"

#ifndef QUEUE_NODE_DATATYPE 
#define QUEUE_NODE_DATATYPE int 
#endif

typedef QUEUE_NODE_DATATYPE qn_datatype;

struct _queue_node
{
	qn_datatype data;
	struct _queue_node *next;

};

typedef struct _queuenode
{
	struct _queue_node *front;
	struct _queue_node *rear;
#ifdef QUEUE_SIZE
	int size;
#endif
}queuenode, *linkqueue;

bool is_empty_q(linkqueue);
bool out_queue(linkqueue, qn_datatype *);
bool en_queue(linkqueue, qn_datatype);
linkqueue init_queue(void);

#ifdef QUEUE_SIZE
int queue_size(linkqueue *);
#endif

#endif

head4rb.h

//

//  Description: 红黑树的各种算法头文件
//

//

#ifndef _HEAD4RB_H_
#define _HEAD4RB_H_

#ifndef RB
#define RB
#endif
#include "head4tree.h"

static linktree grandparent(linktree n)
{
	if(n == NULL || n->parent == NULL)
		return NULL;

	return n->parent->parent;
}

static linktree uncle(linktree n)
{
	linktree gp = grandparent(n);

	if(gp == NULL)
		return NULL;

	return n->parent == gp->lchild ?
		gp->rchild : gp->lchild;
}

static linktree sibling(linktree n)
{
	if(n == NULL || n->parent == NULL)
	{
		return NULL;
	}

	if(n == n->parent->lchild)
		return n->parent->rchild;
	else
		return n->parent->lchild;
}

static linktree left_nephew(linktree n)
{
	return sibling(n)==NULL ? NULL : sibling(n)->lchild;
}

static linktree right_nephew(linktree n)
{
	return sibling(n)==NULL ? NULL : sibling(n)->rchild;
}

static int Color(linktree n)
{
	return n==NULL ? BLACK : n->color;
}


void rotate_left(linktree *proot, linktree n);
void rotate_right(linktree *proot, linktree n);

linktree rb_find(linktree root, tn_datatype data);
linktree bst_insert(linktree root, linktree new);

void insert_case1(linktree *proot, linktree new);
void insert_case2(linktree *proot, linktree new);
void insert_case3(linktree *proot, linktree new);
void rb_insert(linktree *proot, linktree new);
void insert_fixup(linktree *proot, linktree new);

void rb_delete(linktree *proot, tn_datatype data);
void real_delete(linktree *proot, linktree old);
void delete_fixup(linktree *proot, linktree new, linktree parent);

#endif

head4tree.h

//

//  Description: 本文件为二叉树核心头文件。
//               任何使用本二叉树结构算法的程序，在包含本头文件之前
//               都需要将如下宏定义成二叉树节点需要表达的数据类型：
//
//                     TREE_NODE_DATATYPE
//
//               否则二叉树的节点数据类型一律默认为 int

//

#ifndef _HEAD4TREE_H_
#define _HEAD4TREE_H_

/*
 * Any application applying this linked-tree data structure should
 * define the macro "TREE_NODE_DATATYPE" before include this head
 * file, otherwise, the macro will be defined to 'int' as follow.
 *
*/

#ifndef TREE_NODE_DATATYPE
#define TREE_NODE_DATATYPE int
#endif

#include "commonheader.h"

#define MAX(a, b) ({ \
		typeof(a) _a = a; \
		typeof(b) _b = b; \
		(void)(&_a == &_b);\
		_a > _b? _a : _b; \
		})

typedef TREE_NODE_DATATYPE tn_datatype;

#ifdef RB
#define RED   0
#define BLACK 1
#endif

typedef struct _tree_node
{
	tn_datatype data;
	struct _tree_node *lchild;
	struct _tree_node *rchild;

#ifdef AVL
	int height;
#endif

#ifdef RB
	struct _tree_node *parent;
	int color;
#endif
}treenode, *linktree;

void pre_travel(linktree, void (*handler)(linktree));
void mid_travel(linktree, void (*handler)(linktree));
void post_travel(linktree, void (*handler)(linktree));
void level_travel(linktree, void (*handler)(linktree));

linktree bst_insert(linktree root, linktree new);
linktree bst_remove(linktree root, tn_datatype data);
linktree bst_find(linktree root, tn_datatype data);

#ifdef AVL
linktree avl_insert(linktree root, linktree new);
linktree avl_remove(linktree root, tn_datatype data);

linktree avl_rotate_left (linktree root);
linktree avl_rotate_right(linktree root);
linktree avl_rotate_leftright(linktree root);
linktree avl_rotate_rightleft(linktree root);

static int height(linktree root)
{
	return root==NULL ? 0 : root->height;
}
#endif

static linktree new_node(tn_datatype data)
{
	linktree new = malloc(sizeof(treenode));
	if(new != NULL)
	{
		new->data = data;
		new->lchild = NULL;
		new->rchild = NULL;

		#ifdef AVL
		new->height = 1;
		#endif

		#ifdef RB
		new->parent = NULL;
		new->color = RED;
		#endif
	}
	return new;
}

#endif

测试程序

设计一个程序，实现以下功能：
（1）输入大于0的数，则插入节点
（2）输入小于0的数，则删除节点
（3）输入0，则退出程序
（4）退出程序之前用网页画出该二叉树

示例代码如下：

rb_test.c

//

//  Description: 使用红黑树操作接口实现的测试代码，测试结果用网页
//               展示。

//

#ifndef RB
#define RB
#endif

#include "drawtree.h"
#include "head4tree.h"
#include "head4rb.h"

int main(void)
{
	linktree root = NULL;

	printf("输入大于0的数插入节点\n");
	printf("输入小于0的数删除节点\n");
	printf("输入0退出程序\n");

	int n;
	while(1)
	{
		scanf("%d", &n);

		if(n < 0)
		{
			rb_delete(&root, -n);
		}
		else if(n > 0)
		{
			linktree new = new_node(n);
			rb_insert(&root, new);
		}
		else
			break;
	}
	draw(root);
	system("firefox *.html &");

	return 0;
}

注意：上述测试程序使用了draw函数，用来在网页上画出二叉树，该函数相关的实现源码放在我的以下博文的drawtree.c文件中：
draw tree

运行效果如下所示：

输入大于0的数插入节点
输入小于0的数删除节点
输入0退出程序
1
2
3
4
5
9

12
18
91
45
30
28
82
9
9 exist.
13
14
15
66
76
0

显示的网页如下：
123

总结

本文简单介绍了红黑树的概念、算法实现，并进行了实践。
后续我有时间再慢慢补充相关知识点和可能遇到的问题。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

自平衡linux红黑树 的相关文章

  • top 默认使用内存排序的命令

    linux下 xff0c top默认使用cpu来排序 xff0c 如果希望改用内存占用情况或其他项来排序 xff0c 可以通过 o选项 top o MEM 通过 man top 查看其用法 xff0c 里面描述了 o 选项 xff0c 用于

  • 寻找两个点云重叠部分

    目录 方法1 xff1a 方法1实验效果 xff1a 方法2 c 43 43 xff1a 方法2 python 方法2实验效果 xff1a 结论 xff1a 网上大部分寻找重叠区域都是对一个点云建立kdtree xff0c 然后在r半径内搜

  • 防火墙firewalld

    RHEL7中有几种防火墙共存 xff1a firewalld iptables ebtables等 基于iptables的防火墙默认不启动 xff0c 但仍然可以继续使用 RHEL7默认使用firewalld作为防火墙 xff0c 管理工具

  • 仿真平台sumo：随机生成车流的randomTrips.py的较便捷使用方法（新手用）

    Step1 xff1a 首先把需要的地图文件 xff08 net xml xff09 放入自己认为方便操作的文件夹中 此处我的地图文件为demo net 我将其放在一个桌面新建的文件夹里 xff0c 该文件夹叫sumo random 图1

  • 个人面试经验总结

    1 xff0c 海投 2 xff0c 一定要强调自己能留到该地 xff08 这个城市 这个公司 xff09 发展 3 xff0c 简历上出现的技能和项目面试前一天一定要复习 xff0c 因为面试官大部分问题会以简历为主 4 xff0c 要有

  • stm32通用定时器pwm输入模式

    简介 stm32通用定时器有多种输入模式 xff0c 其他包括了pwm输入模式 原理 pwm输入模式是在输入捕获的基础上使用两组输入捕获通道对同一个TIM引脚进行捕获 如下图所示 TIMx CH1引脚输入一个pwm信号 xff0c 经过输入

  • 集成学习中的Boosting和Bagging

    集成学习是一大类模型融合策略和方法的统称 xff0c 其中包含多种集成学习的思想 Boosting Boosting方法训练基分类器时采用串行的方式 xff0c 各个基分类器之间有依赖 它的基本思路是将基分类器层层叠加 xff0c 每一层在

  • Pixhawk与树莓派3的串口通信

    新建主题 msg文件夹下新建mytopic msg文件 char 4 datastr0 字符串的写法 存放发送过来的字符串 uint8 data 将字符串转换成整型 在msg文件夹中的cmkaelist文件中加入 新建pi uart模块 在

  • 树莓派---wiringPi串口使用（win10+树莓派3+usb转串口）

    参考 wiringPi使用手册wiringPi安装wiringPi串口的配置 准备 串口调试助手串口线驱动 在树莓派上用Qt写串口发送数据的程序 serialTEST pro QT 43 61 core QT 61 gui TARGET 6

  • Ubuntu下QT creator查看pixhawk工程

    打开Terminal span class hljs built in cd span src Firmware mkdir Firmware build span class hljs built in cd span Firmware

  • Ubuntu+DroneKit Python配置

    安装 sudo apt span class hljs attribute get span install python span class hljs attribute py span python span class hljs a

  • DroneKit示例分析1---状态的获取与设置

    能获取大部分无人机的状态信息 xff0c 但只有以下几个可以设置 Vehicle span class hljs preprocessor home span location Vehicle span class hljs preproc

  • Python+OpenCV感兴趣区域ROI提取

    Python 43 OpenCV感兴趣区域ROI提取 方法一 xff1a 使用轮廓 步骤1 span class hljs string 34 34 34 src为原图 34 34 34 span ROI 61 np zeros src s

  • 机器学习——数据标注工具使用

    LabelImg 源码编译教程 LabelImg github Windows Linux打包软件 使用方法 Steps Click Change default saved annotation folder in Menu File C

  • TensorFlow——训练自己的数据（一）数据处理

    参考 xff1a Tensorflow教程 猫狗大战数据集 贴一张自己画的思维导图 数据集准备 kaggle猫狗大战数据集 xff08 训练 xff09 xff0c 微软的不需要翻墙 12500张cat12500张dog 生成图片路径和标签

  • TensorFlow——训练自己的数据（三）模型训练

    参考 xff1a Tensorflow教程 猫狗大战数据集 文件training py 导入文件 span class hljs import span class hljs keyword import span os span span

  • TensorFlow——训练自己的数据（四）模型测试

    参考 xff1a Tensorflow教程 猫狗大战数据集 测试一张图片 获取一张图片 函数 xff1a def get one image train 输入参数 xff1a train 训练图片的路径返回参数 xff1a image xf

  • linux BST树算法实现

    简介 BST就是二叉搜索树 Binary Search Tree 的简称 xff0c 因此毫无疑问BST也是二叉树 xff0c 对于二叉树而言 xff0c 和线性表的实现一样 xff0c 我们也必须设计其数据节点 xff0c 而且也必须设计

  • TensorFlow——训练自己的数据——CIFAR10（一）数据准备

    参考教程 Tensorflow教程 xff1a 深度学习 图像分类 CIFAR10数据集 Reading Data 所用函数 span class hljs function span class hljs keyword def span

  • TensorFlow:Object_Detection_API在Windows10上的配置

    安装 假设已配置完tensorflow xff0c 并安装好Anaconda3 4 2 0 xff08 此版本为python3 5 xff09 从github下载models tensorflow models Protobuf 编译 pr

随机推荐

  • TensorFlow Object Detection API 在Windows10和Ubuntu上的配置

    前言 好久没用博客了 xff0c 因为服务器原因重装了好几次 xff0c tensorflow也一直跟着重装 xff0c 这篇博文相比上一篇会更完善点 xff0c 用的版本也会新一些 主要记录在win10和ubuntu上配置Tensorfl

  • 那一年读过的技术经典书

    转载请注明 xff1a http blog csdn net xinzhangyanxiang article details 10199757 大学刚毕业 xff0c 总结起来读过的书并不算多 xff0c 而且主要集中在大四的时期读的 x

  • Bert: 双向预训练+微调

    最近要开始使用Transformer去做一些事情了 xff0c 特地把与此相关的知识点记录下来 xff0c 构建相关的 完整的知识结构体系 以下是要写的文章 xff0c 文章大部分都发布在公众号 雨石记 上 xff0c 欢迎关注公众号获取最

  • Federated Learning: 问题与优化算法

    工作原因 xff0c 听到和使用Federated Learning框架很多 xff0c 但是对框架内的算法和架构了解不够细致 xff0c 特读论文以记之 这个系列计划要写的文章包括 xff1a Federated Learning 问题与

  • DIN: 阿里点击率预估之深度兴趣网络

    广告推荐算法系列文章 xff1a 莫比乌斯 百度的下一代query ad匹配算法百度凤巢分布式层次GPU参数服务器架构DIN 阿里点击率预估之深度兴趣网络DIEN 阿里点击率预估之深度兴趣进化网络 本文的知识点来源于参考文献 1 xff0c

  • DIEN: 阿里点击率预估之深度兴趣进化网络

    广告推荐算法系列文章 xff1a 莫比乌斯 百度的下一代query ad匹配算法百度凤巢分布式层次GPU参数服务器架构DIN 阿里点击率预估之深度兴趣网络基于Delaunay图的快速最大内积搜索算法DIEN 阿里点击率预估之深度兴趣进化网络

  • 概率矩阵分解模型 PMF

    本文是论文 一种结合推荐对象间关联关系的社会化推荐算法 的笔记 xff08 上 xff09 因为对其中的概率矩阵分解 Probabilistic Matrix Factorization PMF 不够了解 xff0c 因而我先去脑补了PMF

  • 卷积神经网络

    卷积神经网络 转载请注明 xff1a http blog csdn net stdcoutzyx article details 41596663 自今年七月份以来 xff0c 一直在实验室负责卷积神经网络 xff08 Convolutio

  • linux系统非线性结构的遍历算法

    介绍 非线性结构的二叉搜索树 xff08 BST xff09 可以进行各种不同方式的遍历 xff0c 所谓遍历 xff0c 就是环游树中的每一个节点 xff0c 然后根据我们的需要对这些节点做某种处理 树的遍历方式主要有以下几种 xff08

  • DeepID人脸识别算法之三代

    DeepID人脸识别算法之三代 转载请注明 xff1a http blog csdn net stdcoutzyx article details 42091205 DeepID xff0c 目前最强人脸识别算法 xff0c 已经三代 如今

  • 理解dropout

    理解dropout 开篇明义 xff0c dropout是指在深度学习网络的训练过程中 xff0c 对于神经网络单元 xff0c 按照一定的概率将其暂时从网络中丢弃 注意是暂时 xff0c 对于随机梯度下降来说 xff0c 由于是随机丢弃

  • 深度卷积对抗生成网络(DCGAN)

    本文是参考文献 1 的论文笔记 卷积神经网络在有监督学习中的各项任务上都有很好的表现 xff0c 但在无监督学习领域 xff0c 却比较少 本文介绍的算法将有监督学习中的CNN和无监督学习中的GAN结合到了一起 在非CNN条件下 xff0c

  • 看图说话——CNN和LSTM的联合应用

    看图说话是深度学习波及的领域之一 其基本思想是利用卷积神经网络来做图像的特征提取 xff0c 利用LSTM来生成描述 但这算是深度学习中热门的两大模型为数不多的联合应用了 本文是参考文献 1 的笔记 xff0c 论文是比较早的论文 xff0

  • 机器学习经典书籍小结

    机器学习经典书籍小结 转载本博客请注明链接 xff1a http blog csdn net xinzhangyanxiang article details 9069045 博客第一篇文章 1 是转载的 xff0c 也算是开始写博客不经意

  • Microsoft Media foundation概述（附实例）

    Microsoft Media Foundation是微软新一代多媒体开发平台 xff0c 用以取代原来的Directshow xff0c 为了满足现在多媒体播放的高清晰 xff0c 高品质 xff0c 颜色管理 xff0c 以及充分利用硬

  • Dockerfile中 使用pip镜像源加速下载

    用dockerfile文件制作镜像 xff0c 提高pip下载速度 1 安装pip3 xff0c python3 RUN apt get update RUN apt get install y python3 5 RUN apt get

  • NVIDIA Jetson Nano主机的autoware的学习与demo运行-第7章-Autoware源码安装

    Autoware源码安装 建立workspace mkdir p autoware ai src cd autoware ai 这个是下载了一个名为autoware ai repos的文件 xff0c 是为了方便管理多个git库而开发 43

  • NVIDIA Jetson Nano主机的autoware的学习与demo运行-第8章-Autoware官方demo运行

    Autoware官方demo 个人学习者很少拥有齐全的传感器以及工控机 xff0c 所以我们可以用autoware ai官网提供的一些录制好的rosbag包及个人笔记本来跑些有趣的demo 安装了 Autoware 之后 xff0c 就可以

  • NVIDIA Jetson AGX Xavier主机刷机与SSD安装

    任务逻辑 当有个新的AGX主机到手上后 xff0c 主机是启动的是eMMC xff0c 大约30G存储 这个安装了系统后到后面随便弄一下就不够存储了 xff0c 所以我是想要在主机上安装一个SSD xff0c 然后将系统直接放到SSD上 x

  • 自平衡linux红黑树

    简介 实际应用中的自平衡搜索二叉树 xff0c 除了AVL之外 xff0c 红黑树也是备受宠爱 他不仅是linux中非线性结构的标准算法 xff0c 而且是Java中TreeMap TreeSet机制 C 43 43 中的STL这些经典工具

热门标签