平衡二叉树与红黑树的区别_平衡二叉树怎么构造

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

一、红黑树的性质：

   红黑树是一颗二叉搜索树，通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因而是近似于平衡的。
  树的每个结点包含5个属性，color，key，left，right，p。如果一个结点没有子结点或父结点，则该结点的响应指针属性的指为NIL。我们可以把这些NIL视为指向二叉搜索树的叶结点（外部节点）的指针，把带关键字的结点视为树的内部结点。
    一颗红黑树是满足下面红黑性质的二叉搜索树：
      1.每个结点或是红色的，或是黑色的。
      2.根结点是黑色的。
      3.每个叶子结点（NIL）是黑色的。
      4.如果一个结点是红的，那么它的两个子结点都是黑的。
      5.对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑结点。
——引用自《算法导论》 第十三章 红黑树 红黑树的性质

  红黑树的平衡通过旋转实现，任何不平衡都会在三次旋转之内解决。查找，插入，删除的时间复杂度均为O(log(N))

二、红黑树的主要用途，和其他树的比较：

  1.主要用途是搜索
  2.AVL和红黑树都是二叉搜索树的变体。
  3.AVL树是严格维持平衡的，红黑树是黑平衡的。但是维持平衡又需要额外的操作，这也加大了数据结构的时间复杂度，所以红黑树可以看做是二叉搜索树和AVL树的一个折中，可以尽量维持树的平衡，又不用话过多的时间来维持数据结构的性质。
  4.AVL和红黑树适合内部存储使用
    红黑树的统计性能要好于AVL，但极端性能略差。
  5.AVL树适合用于插入删除次数比较少，但查找多的情况。
    用于搜索时，插入删除次数多的情况下我们就用红黑树
    windows对进程地址空间的管理用到了AVL树
  6.B树适合外部存储使用
    B树，B+树：多路查找树，一般用于数据库中做索引，因为它们分支多，层数少。因为磁盘I/O是非常耗时的，大量数据存储在磁盘中，我们要有效的减少磁盘I/O次数避免磁盘频繁的查找。AVL和红黑树的问题在于，树的层高过高，在磁盘查询的时候，需要先到对应的扇区，找到下一层节点的位置，再到下一层扇区，找到节点，再继续查找。对于1024个数据，二叉树则需要10层，查询要遍历的扇区过多。
    B+树是B树的变种树，有n棵子树的节点中含有n个关键字，每个关键字不保存数据，只用来索引，数据都保存在叶子节点。是为文件系统而生的。
B+树相对B树磁盘读写代价更低：因为B+树非叶子结点只存储键值，单个节点占空间小，索引块能够存储更多的节点，从磁盘读索引时所需的索引块更少，所以索引查找时I/O次数较B-Tree索引少，效率更高。而且B+Tree在叶子节点存放的记录以链表的形式链接，范围查找或遍历效率更高。Mysql InnoDB用的就是B+Tree索引。
  6.Trie树，又名单词查找树，常用来操作字符串，它是不同字符串的相同前缀只保存一份。相对直接保存字符串肯定是节省空间的，但是它保存大量字符串时会很耗费内存（是内存）。
类似的有：前缀树(prefix tree)，后缀树(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解决耗费内存问题），以及前面说的double array trie。
前缀树：字符串快速检索，字符串排序，最长公共前缀，自动匹配前缀显示后缀。
后缀树：查找字符串s1在s2中，字符串s1在s2中出现的次数，字符串s1,s2最长公共部分，最长回文串。

三、运用场景

总结了部分红黑树的实际应用
  1.sk_buffer
  2.epoll保存socket，epoll在内核中的实现，用红黑树管理事件块。
  3.Nginx中，用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器。
    timer_add
    timer_delete
    timer_trigger 触发
  4.java中的TreeSet，TreeMap
  5.STL中的map和set
  6.著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

①sk_buffer
sk_buff( socket buffer )结构是linux TCP/IP stack中，用于管理Data Buffer的结构，它管理和控制接收或发送数据包的信息。
为了提高网络处理的性能，应尽量避免数据包的拷贝。目前Linux协议栈在接收数据的时候，需要拷贝2次。数据包进入网卡驱动后拷贝一次，从内核空间递交给用户空间的应用时再拷贝一次。
@TODO

1.1 sk_buffer的组成
packet data ： 通过网卡收发的报文，包括链路层，网络层，传输层的协议头和携带的应用数据，包括headroom ， data ， tail room三部分。
skb_shared_info： 作为 packet data的补充，用于存储ip分片，其中sk_buf *frag_list 是一系列子skbuff链表，而frag[]是由一组单独的page组成的数据缓冲区。
data buffer：用于存储packet data的缓冲区，分为以上2部分。
sk_buff：缓冲区控制结构sk_buff。
整个sk_buff结构图如图：

1.2 sk_buffer的结构

struct sk_buff { 
   
struct sk_buff		*next;
struck sk_buff		*prev;
struct sock		*sk;
struct skb_timeval  	tstamp; /* Time we arrived，记录接收或发送报文的时间戳*/
struct net_device	*dev; /*通过该设备接收或发送，记录网络接口的信息和完成操作*/
struct net_device    *input_dev;  /*接收数据的网络设备*/
struct net_device    *curlayer_input_dev;
struct net_device    *l2tp_input_dev;
union { 
   
struct tcphdr   *th;
struct udphdr  *uh;
struct icmphdr*icmph;
struct igmphdr       *igmph;
struct iphdr     *ipiph;
struct ipv6hdr*ipv6h;
unsigned char  *raw;
} h; //传输层报头
union { 
   
struct iphdr     *iph;
struct ipv6hdr*ipv6h;
struct arphdr   *arph;
unsigned char  *raw;
} nh; //网络层报头
union { 
   
unsigned char        *raw;
} mac; //链路层报头

.
.
.
unsigned int           len, //len缓冲区中数据部分的长度。
data_len, //data_len只计算分片中数据的长度
mac_len, //mac头的长度
csum; //校验和
__u32            priority;
__u8              local_df:1,
cloned:1, //表示该结构是另一个sk_buff克隆的
ip_summed:2,
nohdr:1,
nfctinfo:3;
__u8              pkt_type:3,
fclone:2,
ipvs_property:1;
__be16                  protocol;
__u32 flag; /*packet flags*/
.
.
.
/* These elements must be at the end, see alloc_skb() for details. */
unsigned int             truesize; //这是缓冲区的总长度，包括sk_buff结构和数据部分
atomic_t         		users;
unsigned char         *head, //指向缓冲区的头部
*data,// 指向实际数据的头部
*tail, //指向实际数据的尾部
*end;//指向缓冲区的尾部
};

引用自 https://www.cnblogs.com/tzh36/p/5424564.html 后续待修改
引用自 http://www.doc88.com/p-17346276334.html 后续待修改

1.3
struct sk_buff *next, struct sk_buff *prev
有些sk_buff成员变量的作用是方便查找，或者是连接数据结构本身. 内核可以把sk_buff组织成一个双向链表。当然，这个链表的结构要比常见的双向链表的结构复杂一点。就像任何一个双向链表一样，sk_buff中有两个指针next和prev，其中，next指向下一个节点，而prev指向上一个节点。但是，这个链表还有另一个需求：每个sk_buff结构都必须能够很快找到链表头节点。为了满足这个需求，在第一个节点前面会插入另一个结构sk_buff_head，这是一个辅助节点，它的定义如下。

/**************** * 作用：sk_buff链表的表头; * @next: 链表的下一个元素; * @prev: 链表的前一个元素; * @qlen: sk_buff结构的数量; * @lock: 自旋锁; **************/
struct sk_buff_head
{ 
   
	struct sk_buff *next;
	struct sk_buff *prev;
	
	__u32 qlen;
	spinlock_t lock;
};

sk_buff和sk_buff_head的前两个元素是一样的：next和prev指针。这使得它们可以放到同一个链表中，尽管sk_buff_head要比sk_buff小得多。另外，相同的函数可以同样应用于sk_buff和sk_buff_head
②.epoll保存socket，用红黑树管理事件块
@TODO

③Nginx中红黑树管理timer
nginx中的定时器是放在一个全局的叫做ngx_event_timer_rbtree的红黑树中的，通过ngx_add_timer来添加定时器，等超时定时事件执行完后就从红黑树中移除该定时器，所以想要达到循环定时的目的，那就需要每次在执行定时操作后再次通过ngx_add_timer添加到定时列表中。
nginx通过红黑树来维护所有的timer节点，在worker进程的每一次循环中都会调用ngx_process_events_and_timers函数，在该函数中就会调用处理定时器的函数ngx_event_expire_timers，每次该函数都不断的从红黑树中取出时间值最小的，查看他们是否已经超时，然后执行他们的函数，直到取出的节点的时间没有超时为止。
—————————
nginx定时器实现的源码有下面几个接口
3.1.1初始化定时器
来看一下ngx_event_timer_init这个函数是怎么实现的, 在 src/event/ngx_event_timer.c 中

ngx_int_t 
ngx_event_timer_init(ngx_log_t *log) { 
   
    ngx_rbtree_init(&ngx_event_timer_rbtree, &ngx_event_timer_sentinel,
                    ngx_rbtree_insert_timer_value);//初始化了一个红黑树
    return NGX_OK;
}

调用ngx_rbtree_init初始化一颗红黑树，其中前两个参数是全局变量

ngx_rbtree_t              ngx_event_timer_rbtree;   //红黑树
static ngx_rbtree_node_t  ngx_event_timer_sentinel; //哨兵结点

ngx_rbtree_insert_timer_value 是ngx_rbtree_t中的用于插入定时器的处理函数，支持自定义：

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
    
// 红黑树中的结点
struct ngx_rbtree_node_s { 
   
    ngx_rbtree_key_t       key; //用于保存定时时间戳
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};
​
// 红黑树
struct ngx_rbtree_s { 
   
    ngx_rbtree_node_t     *root;//根结点
    ngx_rbtree_node_t     *sentinel;//哨兵结点
    ngx_rbtree_insert_pt   insert; //插入结点处理函数
};

3.1.2添加计时器
添加前会判断新的定时器与现在的定时器是否间隔很短，如果时间时隔小于NGX_TIMER_LAZY_DELAY所定义的毫秒数，则无需向红黑树添加，仍旧使用原有的定时器，提高性能。

#define NGX_TIMER_LAZY_DELAY 300 //时间差：300毫秒
​
static ngx_inline void 
ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer)
{ 
   
    ngx_msec_t      key;
    ngx_msec_int_t  diff;
​
    // 计算新key值
    key = ngx_current_msec + timer;
​
    //已注册有定时事件
    if (ev->timer_set) { 
   
         /* 如果新的key值与现有的key值相差小于NGX_TIMER_LAZY_DELAY定义的毫秒数 /* 则不对rbtee做任何操作，直接退出，继续使用现有的key值。 diff = (ngx_msec_int_t) (key - ev->timer.key); if (ngx_abs(diff) < NGX_TIMER_LAZY_DELAY) { return; } ​ //相差大于NGX_TIMER_LAZY_DELAY定义的毫秒数，先将rbtree结点删除 ngx_del_timer(ev); } ​ //使用新的key值。 ev->timer.key = key; //向红黑树中注册新的定时事件，并将time_set置1 ngx_rbtree_insert(&ngx_event_timer_rbtree, &ev->timer); ​ ev->timer_set = 1; } 

3.1.3删除定时器
先从红黑树中删除节点，再将timer_set标志位置0

static ngx_inline void 
ngx_event_del_timer(ngx_event_t *ev)
{ 
   
    ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);
    ev->timer_set = 0;
}

3.1.4查找定时器
从红黑树中找到key值最小的结点，并根据超时与否，返回不同的值

ngx_msec_t 
ngx_event_find_timer(void)
{ 
   
    ngx_msec_int_t      timer;
    ngx_rbtree_node_t  *node, *root, *sentinel;
​
    // 没有定时器，直接返回-1
    if (ngx_event_timer_rbtree.root == &ngx_event_timer_sentinel) { 
   
        return NGX_TIMER_INFINITE;
    }
​
    root = ngx_event_timer_rbtree.root;
    sentinel = ngx_event_timer_rbtree.sentinel;
​
    // 从树上找到key值最小的结点
    node = ngx_rbtree_min(root, sentinel);
​
    // 定时器中的key与当前时间戳比较，如果小于当前时间戳，说明已超时了，反之则未超时
    timer = (ngx_msec_int_t) (node->key - ngx_current_msec);
​
    // 超时返回0，否则返回即将到达当前时间点的的数值
    return (ngx_msec_t) (timer > 0 ? timer : 0);
}
其中，查找最小key结点使用了ngx_rbtree_min函数，查找树的最左边结点。
static ngx_inline ngx_rbtree_node_t * ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{ 
   
    while (node->left != sentinel) { 
   
        node = node->left;
    }
​
    return node;
}

3.2超时处理
循环查找树种已超时结点，删除超时结点，并调用超时处理函数，知道第一个还未超时的结点，退出。

void ngx_event_expire_timers(void)
{ 
   
    ngx_event_t        *ev;
    ngx_rbtree_node_t  *node, *root, *sentinel;
​
    sentinel = ngx_event_timer_rbtree.sentinel;
​
    for ( ;; ) { 
   
        root = ngx_event_timer_rbtree.root;
​
        //没有直接返回
        if (root == sentinel) { 
   
            return;
        }
​
        // 查找key值最小的结点
        node = ngx_rbtree_min(root, sentinel);
​
        /* node->key > ngx_current_msec */
​
        // 循环查找最小结点，直到遇到第一个还未到时间的结点，退出循环
        if ((ngx_msec_int_t) (node->key - ngx_current_msec) > 0) { 
   
            return;
        }
​
        //根据成员地址和偏移，得出成员所在结构体的地址
        ev = (ngx_event_t *) ((char *) node - offsetof(ngx_event_t, timer));
​
        // 删除定时器结点
        ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->timer);
​
        //标志位置0
        ev->timer_set = 0;
        
        // 已超时标志位置1
        ev->timedout = 1;
​
        // 调用超时事件处理函数
        ev->handler(ev);
    }
}

3.3Nginx定时器调用流程
3.3.1初始化
在nginx_event_process_init函数中调用了定时器初始化函数

static ngx_int_t ngx_event_process_init(ngx_cycle_t *cycle)
{ 
   
    ......
​
    if (ngx_event_timer_init(cycle->log) == NGX_ERROR) { 
   
        return NGX_ERROR;
    }
    ......
}

3.3.2设置事件的超时处理函数，并通过ngx_add_timer接口添加定时器事件
ngx_add_timer是一个宏定义，实际调用的是ngx_event_add_timer函数

#define ngx_add_timer ngx_event_add_timer
#define ngx_del_timer ngx_event_del_timer

摘取nginx添加定时器事件的代码片段：

    ngx_cleaner_event.handler = ngx_clean_old_cycles; //设置超时处理函数
        ngx_cleaner_event.log = cycle->log;
        ngx_cleaner_event.data = &dumb;
        dumb.fd = (ngx_socket_t) -1;
    }
​
   ......
​
    if (!ngx_cleaner_event.timer_set) { 
   
        ngx_add_timer(&ngx_cleaner_event, 30000); //添加定时器事件
        ngx_cleaner_event.timer_set = 1;
    }

3.3.3循环处理超时事件
nginx中有四个循环处理函数，分别运行于nginx不同的工作模式：
    ngx_single_process_cycle
    ngx_worker_process_cycle
    ngx_cache_manager_process_cycle
    ngx_worker_thread_cycle
以 ngx_single_process_cycle 为例：

void ngx_single_process_cycle(ngx_cycle_t *cycle)
{ 
   
    ......
​
    for ( ;; ) { 
   
        ngx_log_debug0(NGX_LOG_DEBUG_EVENT, cycle->log, 0, "worker cycle");
​
        ngx_process_events_and_timers(cycle);
​
        ......
    }
}

在for循环中中，调用了ngx_process_events_and_timers函数

void ngx_process_events_and_timers(ngx_cycle_t *cycle)
{ 
   
    ......
​
    if (delta) { 
   
        ngx_event_expire_timers(); //调用超时触发函数
    }
​
    ngx_event_process_posted(cycle, &ngx_posted_events);
}

PS：这一部分的介绍和代码取自 知乎「夜空」 我也没有在Nginx的源码中完整查找论证过，我看的nginx版本是1.14.2 ，后续可能会改动代码的部分引用和注释。

本篇文章引用了以下文章中的内容，

CSDN博主「mengfanteng」的文章 《AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中》
原文链接：https://blog.csdn.net/mtt_sky/article/details/51442452

知乎博主「夜空」的文章 《红黑树应用1-nginx timer》
原文链接：https://zhuanlan.zhihu.com/p/78042487

博客园博主 「唐稚骅」的文章 《Linux内核：sk_buff解析》
原文链接：https://www.cnblogs.com/tzh36/p/5424564.html

CSDN博主「繁华落尽梦一场」的原创文章
原文链接：https://blog.csdn.net/zhangqi_gsts/article/details/52461031

CSDN博主「Sunands」的原创文章
原文链接：https://blog.csdn.net/woaini2050/article/details/89639951