红黑树的实现原理和应用场景

红黑树的实现原理和应用场景；

有如图所示的表，现在希望查询的结果将列成行

建表语句如下：

CREATE TABLE `TEST_TB_GRADE2` (

`ID` int(10) NOT NULL AUTO_INCREMENT,

`USER_NAME` varchar(20) DEFAULT NULL,

`CN_SCORE` float DEFAULT NULL,

`MATH_SCORE` float DEFAULT NULL,

`EN_SCORE` float DEFAULT '0',

PRIMARY KEY (`ID`)

) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;12345678

insert into TEST_TB_GRADE2(USER_NAME, CN_SCORE, MATH_SCORE, EN_SCORE) values

("张三", 34, 58, 58),

("李四", 45, 87, 45),

("王五", 76, 34, 89);1234

select user_name, '语文' COURSE , CN_SCORE as SCORE from test_tb_grade2

union select user_name, '数学' COURSE, MATH_SCORE as SCORE from test_tb_grade2

union select user_name, '英语' COURSE, EN_SCORE as SCORE from test_tb_grade2

order by user_name,COURSE;1234红黑树(一棵自平衡的排序二叉树)五大特性：

1）每个结点要么是红的，要么是黑的。 

2）根结点是黑的。 

3）每个叶结点，即空结点是黑的。 

4）如果一个结点是红的，那么它的俩个儿子都是黑的。 

5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

场景

1）广泛用于C++的STL中,map和set都是用红黑树实现的.

2）著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存 区域都

存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址 虚拟存储区域,

右指针指向相邻的高地址虚拟地址空间.

3）IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查.

4）ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.

5）java中的TreeSet,TreeMap