2-3 树
2-3 树是最简单的 B 树，2-3 树一颗绝对平衡的树，2-3 树满足二分搜索树的基本性质，在2-3 树中有两种节点，一种存放一个元素，另外一种存在两个元素。
2-3 树添加元素
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。 它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树和2-3树是等价的。 红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树特点
1.每个节点或者是红色的，或者是黑色的 2.根节点是黑色的 3.每一个叶子节点(最后的空节点)是黑色的 4.如果一个节点是红色的，那么他的孩子节点都是黑色的 5.从任意-一个节点到叶子节点，经过的黑色节点是一样的
红黑树和AVL树比较
1.两者都是平衡二叉树，但AVL是平衡二叉树，红黑树是黑平衡 2.红黑树的旋转次数低于AVL树，在插入和删除频繁的场景下，红黑树的性能优于AVL树。在查询频繁的场景下，AVL树的性能优于红黑树。
红黑树 和 2-3 树等价
2-3 树转换成红黑树
红黑树添加元素
java实现
public class RBTree<K
extends Comparable<K>, V
> {
private static final boolean RED
= true;
private static final boolean BLACK
= false;
private Node root
;
private int size
;
public RBTree() {
this.root
= null
;
this.size
= 0;
}
public int getSize() {
return this.size
;
}
public boolean isEmpty() {
return this.size
== 0;
}
private boolean isRed(Node node
) {
if (node
== null
) {
return this.BLACK
;
}
return node
.color
;
}
private Node
_leftRotate(Node node
) {
Node x
= node
.right
;
node
.right
= x
.left
;
x
.left
= node
;
x
.color
= node
.color
;
node
.color
= RED
;
return x
;
}
private Node
_rightRotate(Node node
) {
Node x
= node
.left
;
node
.left
= x
.right
;
x
.right
= node
;
x
.color
= node
.color
;
node
.color
= RED
;
return x
;
}
private void _flipColors(Node node
) {
node
.color
= RED
;
node
.left
.color
= BLACK
;
node
.right
.color
= BLACK
;
}
public void add(K key
, V value
) {
this.root
= _add(this.root
, key
, value
);
this.root
.color
= BLACK
;
}
private Node
_add(Node node
, K key
, V value
) {
if (node
== null
) {
this.size
++;
return new Node(key
, value
);
}
if (key
.compareTo(node
.key
) < 0) {
node
.left
= _add(node
.left
, key
, value
);
} else if (key
.compareTo(node
.key
) > 0) {
node
.right
= _add(node
.right
, key
, value
);
} else {
node
.value
= value
;
}
if (isRed(node
.right
) && !isRed(node
.left
)) {
node
= _leftRotate(node
);
}
if (isRed(node
.left
) && isRed(node
.left
.left
)) {
node
= _rightRotate(node
);
}
if (isRed(node
.left
) && isRed(node
.right
)) {
_flipColors(node
);
}
return node
;
}
private Node
_getNode(Node node
, K key
) {
if (node
== null
) {
return null
;
}
if (key
.equals(node
.key
)) {
return node
;
} else if (key
.compareTo(node
.key
) < 0) {
return _getNode(node
.left
, key
);
} else {
return _getNode(node
.right
, key
);
}
}
public boolean contains(K key
) {
return _getNode(this.root
, key
) != null
;
}
public V
get(K key
) {
Node node
= _getNode(this.root
, key
);
return node
== null
? null
: node
.value
;
}
public void set(K key
, V value
) {
Node node
= _getNode(this.root
, key
);
if (node
== null
) {
throw new IllegalArgumentException(key
+ " doesn't exist!");
}
node
.value
= value
;
}
private Node
_minimum(Node node
) {
if (node
.left
== null
) {
return node
;
}
return _minimum(node
.left
);
}
private Node
_removeMin(Node node
) {
if (node
.left
== null
) {
Node right
= node
.right
;
node
.right
= null
;
this.size
--;
return right
;
}
node
.left
= _removeMin(node
.left
);
return node
;
}
public V
remove(K key
) {
Node node
= _getNode(this.root
, key
);
if (node
!= null
) {
this.root
= _remove(this.root
, key
);
return node
.value
;
}
return null
;
}
private Node
_remove(Node node
, K key
) {
if (node
== null
) {
return null
;
}
if (key
.compareTo(node
.key
) < 0) {
node
.left
= _remove(node
.left
, key
);
return node
;
} else if (key
.compareTo(node
.key
) > 0) {
node
.right
= _remove(node
.right
, key
);
return node
;
} else {
if (node
.left
== null
) {
Node right
= node
.right
;
node
.right
= null
;
this.size
--;
return right
;
}
if (node
.right
== null
) {
Node left
= node
.left
;
node
.left
= null
;
this.size
--;
return left
;
}
Node min
= _minimum(node
.right
);
min
.right
= _removeMin(node
.right
);
min
.left
= node
.left
;
node
.left
= node
.right
= null
;
return min
;
}
}
private class Node {
public K key
;
public V value
;
public Node left
, right
;
public boolean color
;
public Node(K key
, V value
) {
this.key
= key
;
this.value
= value
;
this.left
= null
;
this.right
= null
;
this.color
= RED
;
}
}
}
