# 常见数据结构(二)-树(二叉树，红黑树，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

snailclimb
05/08
0
0

2017/12/14
0
0
Java关于数据结构的实现：树

2017/09/28
0
0

2016/11/29
0
0
JDK TreeMap Red-Black Tree

zuoer
2011/12/18
0
0

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb
2013/12/07
0
2
Java集合--TreeMap完全解析

4 TreeMap 上一篇，介绍了集合框架中的HashMap对象，主要讲述了HashMap的底层实现和基本操作。本篇，让我们继续来学习Map集合，今天的主角是TreeMap。 相比于HashMap来说，TreeMap理解起来更...

2017/09/10
0
0

06/13
0
0

brianway
2016/10/14
763
2

Jvm堆内存的划分结构和优化，垃圾回收详解（详细解答篇）

8分钟前
0
0
CentOS 7.4 设置系统字符编码

1.语言变量LANG在 /etc/locale 文件中。 2.可以通过/ect/profile 来修改LC_TYPE 变量的值 添加如下代码 export LC_ALL="zh_CN.GBK" export LANG="zh_CN.GBK" 到profile文件中，变量的可以修改...

qimh
9分钟前
0
0
Kafka相关使用

10分钟前
0
0
CentOS7 解决无法使用tab自动补全 tab代码提示

ziluopao
16分钟前
0
0
redis安装

https://www.cnblogs.com/feijl/p/6879929.html

ghou-靠墙哭
16分钟前
0
0
Spring核心——注解自动装载

19分钟前
1
0
ElasticSearch学习（8）—— SearchType

Elasticsearch有四种类型的SearchType 1、query and fetch 向索引的所有分片（shard）都发出查询请求，各分片返回的时候把元素文档（document）和计算后的排名信息一起返回。这种搜索方式是最...

21分钟前
0
0
MYSQL备份工具-mysqldump

23分钟前
0
0

24分钟前
0
0

26分钟前
1
0