Skip to content

Commit 8901ce7

Browse files
byhiegbyhieg
committed
添加红黑树的插入，旋转
1 parent 2a1900f commit 8901ce7

3 files changed

Lines changed: 244 additions & 1 deletion

File tree

‎src/main/java/cn/byhieg/algorithmtutorial/RedBlackTree.java‎

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,211 @@
1+
package cn.byhieg.algorithmtutorial;
2+
3+
/**
4+
* Created by byhieg on 2017/6/24.
5+
* Mail to byhieg@gmail.com
6+
*/
7+
8+
9+
/**
10+
* 红黑树，一种通过红黑两种节点来维持二叉搜索树的一种树
11+
* 这样树比原先的BST而言，不会出现最坏的查找情况是o(N)的情况
12+
* 但是对于插入和删除的节点而言，就需要调整树的平衡，也就是维持红黑树的定义
13+
*
14+
* 红黑树的定义如下：
15+
* 1. 任何节点要不是黑色要不是红色
16+
* 2. 根节点是黑色节点
17+
* 3. 红节点的两个子节点都是黑色节点
18+
* 4. 空节点是黑色节点
19+
* 5. 任何一个节点下面遍历其子孙的叶子节点，经过的黑色节点的个数必须相等。
20+
*
21+
* 红黑树也是通过第5点进行维持平衡的，而为了维持平衡，需要对树进行调整，即进行左旋，右旋。
22+
*
23+
* 左旋是指 A
24+
* B C
25+
* 对C左旋 变成
26+
*
27+
* C
28+
* A
29+
* B
30+
*
31+
* 节点从左节点变成根节点就是左旋
32+
*
33+
* 右旋是指 A
34+
* B C
35+
*
36+
* 对B右旋 变成
37+
* B
38+
* A
39+
* C
40+
*
41+
* 节点从右节点变成根节点就是右旋
42+
*
43+
*/
44+
public class RedBlackTree {
45+
46+
Node root;
47+
48+
public RedBlackTree(){
49+
}
50+
51+
public RedBlackTree(int value) {
52+
root = new Node(value);
53+
}
54+
55+
public Node find(int value) {
56+
if (root == null) {
57+
throw new RuntimeException("树是空的");
58+
}
59+
60+
Node currentNode = root;
61+
while (currentNode != null && currentNode.getValue() != value) {
62+
if (currentNode.getValue() < value) {
63+
currentNode = currentNode.getLeft();
64+
}else{
65+
currentNode = currentNode.getRight();
66+
}
67+
}
68+
69+
return currentNode;
70+
}
71+
72+
73+
public void insertNode(int value) {
74+
Node node = new Node(value);
75+
insertNode(node);
76+
77+
}
78+
79+
/**
80+
* 插入节点
81+
* 该方法首先找到要插入的位置，然后设置插入的节点为红色节点
82+
* 然后因为可能会破坏平衡，因此需要进行平衡调整
83+
* @param node
84+
*/
85+
public void insertNode(Node node) {
86+
int cmp;
87+
Node y = null;
88+
Node x = this.root;
89+
90+
while (x != null) {
91+
y = x;
92+
cmp = node.getValue() - x.getValue();
93+
if (cmp < 0) {
94+
x = x.left;
95+
}else{
96+
x = x.right;
97+
}
98+
}
99+
100+
node.parent = y;
101+
if (y != null) {
102+
cmp = node.getValue() - y.getValue();
103+
if (cmp < 0) {
104+
y.left = node;
105+
}else{
106+
y.right = node;
107+
}
108+
}else{
109+
this.root = node;
110+
}
111+
112+
node.isRed = true;
113+
insertFixUp(node);
114+
115+
}
116+
117+
/**
118+
* 插入修复： 新插入的节点是红色节点，插入修复操作如果遇到父节点的颜色为黑色则修复结束
119+
* 也就是说只有在父节点为红色节点的时候才需要插入修复操作
120+
* 插入修复操作分为3种情况，
121+
* 1. 叔叔节点也为红色节点
122+
* 2. 叔叔节点为空，且祖父节点，父节点与新节点在一个斜线上
123+
* 3. 叔叔节点为空，且祖父节点，父节点与新节点不在一个斜线上
124+
*
125+
*
126+
* 解决办法：对于第一种，只需要将祖父节点与父节点以及叔叔节点的颜色对调即可。
127+
* 即原祖父节点是黑色，现在变成红色，父节点与叔叔节点都变成黑色。
128+
* 对于第二种，我们将新插入的节点为C,父节点为B,祖父节点为A.
129+
* 如果BC都是左节点，要现将B右旋，然后调整B与C的颜色，即B变成黑色，A变成红色
130+
* 如果BC都是右节点，要现将B左旋，然后调整B与C的颜色，即B变成黑色，A变成红色
131+
* 对于第三种，我们将新插入的节点为C,父节点为B,祖父节点为A.
132+
* 如果C为右节点，B为左节点，要先将C左旋，然后就变成第二种的情况
133+
* 如果C为左节点，B为右节点，要先将C右旋，然后就变成第二种的情况
134+
*
135+
* @param node
136+
*/
137+
private void insertFixUp(Node node) {
138+
139+
140+
}
141+
142+
143+
static class Node {
144+
private int value;
145+
private Node parent;
146+
private boolean isRed;
147+
private Node left;
148+
private Node right;
149+
150+
public Node(){
151+
152+
}
153+
154+
public Node(int value) {
155+
this.value = value;
156+
157+
}
158+
159+
public Node(int value, boolean isRed) {
160+
this.value = value;
161+
this.isRed = isRed;
162+
}
163+
public int getValue() {
164+
return value;
165+
}
166+
167+
public void setValue(int value) {
168+
this.value = value;
169+
}
170+
171+
public Node getParent() {
172+
return parent;
173+
}
174+
175+
public void setParent(Node parent) {
176+
this.parent = parent;
177+
}
178+
179+
public boolean isRed() {
180+
return isRed;
181+
}
182+
183+
public boolean isBlack(){
184+
return !isRed();
185+
}
186+
187+
public Node getLeft() {
188+
return left;
189+
}
190+
191+
public void setLeft(Node left) {
192+
this.left = left;
193+
}
194+
195+
public Node getRight() {
196+
return right;
197+
}
198+
199+
public void setRight(Node right) {
200+
this.right = right;
201+
}
202+
203+
public void makeRed(){
204+
isRed = true;
205+
}
206+
207+
public void makeBlack(){
208+
isRed = false;
209+
}
210+
}
211+
}

‎src/main/java/cn/byhieg/algorithmtutorial/SingleLinkList.java‎

Lines changed: 21 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,10 @@ public Node insertFromHead(int data) {
4343
return head;
4444
}
4545

46-
46+
/**
47+
* 反转链表的非递归实现
48+
* @return
49+
*/
4750
public Node reverseLinkList() {
4851
if (head == null) {
4952
return head;
@@ -63,6 +66,23 @@ public Node reverseLinkList() {
6366
return reverseHead;
6467
}
6568

69+
70+
/**
71+
* 反转链表的递归实现
72+
* @return
73+
*/
74+
public Node reverseLinkList(Node head){
75+
if (head == null || head.next == null) {
76+
return head;
77+
}
78+
Node newNode = reverseLinkList(head.next);
79+
head.next.next = head;
80+
head.next = null;
81+
return newNode;
82+
}
83+
84+
85+
6686
/**
6787
* 打印链表
6888
*/

‎src/test/java/cn/byhieg/algorithmtutorialtest/SingleLinkListTest.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ public void testInsertFromHead() throws Exception {
4343
// System.out.println("头插入");
4444
}
4545
public void testReverseLinkList() throws Exception {
46+
System.out.println();
4647
linkList.insertFromHead(1);
4748
linkList.insertFromHead(2);
4849
linkList.insertFromHead(3);
@@ -51,6 +52,17 @@ public void testReverseLinkList() throws Exception {
5152
linkList.insertFromHead(6);
5253
linkList.printLinkList(linkList.reverseLinkList());
5354
}
55+
56+
public void testReverseLinkList2() throws Exception{
57+
System.out.println("递归反转链表");
58+
linkList.insertFromHead(1);
59+
linkList.insertFromHead(2);
60+
linkList.insertFromHead(3);
61+
linkList.insertFromHead(4);
62+
linkList.insertFromHead(5);
63+
linkList.insertFromHead(6);
64+
linkList.printLinkList(linkList.reverseLinkList(linkList.getHead()));
65+
}
5466
public void testGetHead() throws Exception {
5567
}
5668

0 commit comments

Comments
 (0)