# 常见数据结构(二)-树(二叉树，红黑树，B树) 转

浮躁的码农

## Binary Search Tree(二分查找树)

A binary tree is either:

• Empty.
• Two disjoint binary trees (left and right).

Symmetric order.Each node has a key, and every node’s key is:

• Larger than all keys in its left subtree.
• Smaller than all keys in its right subtree.

``````private class Node {
private Key key;
private Value val;
private Node left, right;

public Node(Key key, Value val) {
this.key = key;
this.val = val;
}
}``````

• 查找：得到相应键的值，若无此键则返回null.
``````/* 查找 */
public Value get(Key key) {
Node x = root;
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x = x.left;
} else if (cmp > 0) {
x = x.right;
} else { // if (cmp == 0)
return x.val;
}
}
return null;
}``````
• 插入：如果小，往左；如果大，往右；如果null，插入；如果存在，覆盖。
``````/* 插入 */
public void put(Key key, Value val) {
root = put(root, key, val);
}

/* 辅助函数，递归调用 */
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val);
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else { // if (cmp == 0)
x.val = val;
}
return x;
}``````

• 删除：列出下面几种处理方法
• 将值置为null，在树中保留键
• 删除最小值：一直向左找到左子树为null的节点，用它的右子节点代替它。
• Hibbard deletion

2. 有一个子节点的节点，删除该节点并以子节点代替即可。
3. 有两个子节点的节点，找到该节点t的下一个节点x（即右子树的最小节点），在右子树删除这个节点，并将该节点x放到t的位置。
``````/* 删除 */
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if (cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) return x.left; // no right child
if (x.left == null) return x.right; // no left child
Node t = x;
x = min(t.right); // replace with successor
x.right = deleteMin(t.right);
x.left = t.left;
}
x.count = size(x.left) + size(x.right) + 1;
return x;
}``````

## 2-3 Search Trees(2-3树)

2-3树是二分查找树的变形，每个节点是下面两种情况之一：

• 2-node:一个键，两个分叉（smaller,larger）
• 3-node:两个键，三个分叉（smaller,between,larger）

• 向3-node插入一个键，临时成为一个4-node
• 将4-node中间的key移动到父节点
• 向上重复
• 如果到了顶端的根节点，且根节点是4-node,将其分成3个2-nodes.

• Worst case: lg N. [all 2-nodes]
• Best case: log3 N ≈ 0.631 lg N. [all 3-nodes]

## Red-Black BSTs(红黑树)

• No node has two red links connected to it.
• Every path from root to null link has the same number of black links.

``````private static final boolean RED = true;
private static final boolean BLACK = false;

private class Node {
Key key;
Value val;
Node left, right;
boolean color;// color of parent link
}

private boolean isRed(Node x) {
if (x == null) return false;
return x.color == RED;
}``````

### 左转-右转-变色

• left rotate
• right rotate
• flip colors

• 左转

``````/* left rotate */
private Node rotateLeft(Node h) {
assert isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}``````
• 右转

``````/* right rotate */
private Node rotateRight(Node h) {
assert isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}``````
• 变色

``````/* flip colors */
private void flipColors(Node h) {
assert !isRed(h);
assert isRed(h.left);
assert isRed(h.right);
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}``````

### 插入操作

1. 已有a和b时，c插入在b的右子节点，直接变色即可
2. 已有b和c时，a插入在b的左子节点，先右转把b滑上去，成1中的状态，再变色即可
3. 已有a和c时，b插入在a的右子节点，先左转把a滑下去，成2中的状态，再右转＋变色即可

``````private Node put(Node h, Key key, Value val) {
//insert at bottom (and color it red)
if (h == null) return new Node(key, val, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = put(h.left, key, val);
} else if (cmp > 0) {
h.right = put(h.right, key, val);
} else {
h.val = val;
}

if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);// lean left
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);//balance 4-node
if (isRed(h.left) && isRed(h.right)) flipColors(h);//split 4-node

return h;
}``````

• Every path from root to null link has same number of black links.
• Never two red links in-a-row.

## B-Trees(B树)

• At least 2 key-link pairs at root.
• At least M / 2 key-link pairs in other nodes.
• External nodes contain client keys.
• Internal nodes contain copies of keys to guide search.

• Start at root.
• Find interval for search key and take corresponding link.
• Search terminates in external node.

• Search for new key.
• Insert at bottom.
• Split nodes with M key-link pairs on the way up the tree.

### 浮躁的码农

JAVA中的数据结构 - 真正的去理解红黑树

2015/06/23
0
0
MySQL索引结构采用B+树的原因

edwardGe
08/26
0
0

snailclimb
05/08
0
0

kissjz
08/16
0
0

2017/12/14
0
0

springboot中filter的用法

xiaomin0322
16分钟前
3
0
java项目修改了更换了jdk版本报错进行修改

java项目原来用的是1.8版本的,改成1.7版本后,项目会报错,要进行的修改是 然后是clean一下项目,然后是选中项目的buildpath,然后是configurebuildpath,然后是看jdk是否进行修改...

myAll_myAll
28分钟前
3
0
Gartner 2018 数据库系列报告发布 巨杉数据库连续两年入选

30分钟前
1
0
Navicat闲置一段时间卡死问题的解决

joyStalker
30分钟前
1
0

1. What——什么是弱引用？ Java中的弱引用具体指的是java.lang.ref.WeakReference<T>类，我们首先来看一下官方文档对它做的说明： 弱引用对象的存在不会阻止它所指向的对象变被垃圾回收器回...

31分钟前
0
0