2、3树
一颗标准的二叉查找树中的节点为2-节点（含有一个键和两条链接）引入3-节点（含有两个键和三条链接）。2-节点和3-节点的每条链接都对应着其中保存的键所分割产生的一个区间。
2-3查找树定义：
- 2-节点，含有一个键（及其对应值）和两条链接，左链接指向2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点。
- 3-节点，含有两个键（及其对应值）和三条链接，左链接指向2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。
指向一颗空树的链接称为空链接。一颗完美平衡的2-3查找树中所有的空链接到根节点的距离都应该是相同的。
在一颗大小为N的2-3树中，查找和插入操作访问的节点必然不超过lgN个
红黑二叉查找树
红黑树是对2-3树的一种实现，红黑树是用标准的二叉查找树和一些额外的信息（替换3-节点）来表示2-3树。
树中的链接分为两种类型：红链接将两个2-节点连接起来构成一个3-节点，黑链接则是2-3树中的普通链接。
红黑树的另一种定义：
含有红黑链接并满足下列条件的二叉查找树
- 红链接均为左链接
- 没有任何一个节点同时和两条红链接相连
- 该树是完美黑色平衡的，即任意空链接到根节点的路径上的黑链接数量相同
方便起见，因为每个节点都只会有一条指向自己的链接（从它的父节点指向它），我们将链接的颜色保存在表示该节点的Node数据类型的Boolean变量color中。如果指向它的链接是红色的，那么该变量为true，黑色的则为false。约定空链接为黑色。
红黑树的性质：
- 一颗大小为N的红黑树的高度不会超过2lgN
- 一颗大小为N的红黑树中，根节点到任意节点的平均路径长度为~1.00lgN
- 在一颗红黑树中，以下操作在最坏的情况下所需的时间是对数级别的：查找、插入、查找最大/小键、floor()、ceiling()、rank()、select()、删除最小/大键、删除和范围查询
红黑树
原文：https://www.cnblogs.com/z-dk/p/14496302.html
