1010 * 红黑树，一种通过红黑两种节点来维持二叉搜索树的一种树
1111 * 这样树比原先的BST而言，不会出现最坏的查找情况是o(N)的情况
1212 * 但是对于插入和删除的节点而言，就需要调整树的平衡，也就是维持红黑树的定义
13- *
13+ * <p>
1414 * 红黑树的定义如下：
1515 * 1. 任何节点要不是黑色要不是红色
1616 * 2. 根节点是黑色节点
1717 * 3. 红节点的两个子节点都是黑色节点
1818 * 4. 空节点是黑色节点
1919 * 5. 任何一个节点下面遍历其子孙的叶子节点，经过的黑色节点的个数必须相等。
20- *
20+ * <p>
2121 * 红黑树也是通过第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- *
22+
4323 */
4424public class RedBlackTree {
4525
4626 Node root ;
4727
48- public RedBlackTree (){
28+ public RedBlackTree () {
4929 }
5030
5131 public RedBlackTree (int value ) {
@@ -61,7 +41,7 @@ public Node find(int value) {
6141 while (currentNode != null && currentNode .getValue () != value ) {
6242 if (currentNode .getValue () < value ) {
6343 currentNode = currentNode .getLeft ();
64- }else {
44+ } else {
6545 currentNode = currentNode .getRight ();
6646 }
6747 }
@@ -80,6 +60,7 @@ public void insertNode(int value) {
8060 * 插入节点
8161 * 该方法首先找到要插入的位置，然后设置插入的节点为红色节点
8262 * 然后因为可能会破坏平衡，因此需要进行平衡调整
63+ *
8364 * @param node
8465 */
8566 public void insertNode (Node node ) {
@@ -92,7 +73,7 @@ public void insertNode(Node node) {
9273 cmp = node .getValue () - x .getValue ();
9374 if (cmp < 0 ) {
9475 x = x .left ;
95- }else {
76+ } else {
9677 x = x .right ;
9778 }
9879 }
@@ -102,10 +83,10 @@ public void insertNode(Node node) {
10283 cmp = node .getValue () - y .getValue ();
10384 if (cmp < 0 ) {
10485 y .left = node ;
105- }else {
86+ } else {
10687 y .right = node ;
10788 }
108- }else {
89+ } else {
10990 this .root = node ;
11091 }
11192
@@ -121,22 +102,155 @@ public void insertNode(Node node) {
121102 * 1. 叔叔节点也为红色节点
122103 * 2. 叔叔节点为空，且祖父节点，父节点与新节点在一个斜线上
123104 * 3. 叔叔节点为空，且祖父节点，父节点与新节点不在一个斜线上
124- *
125- *
105+ * <p>
106+ * <p>
126107 * 解决办法：对于第一种，只需要将祖父节点与父节点以及叔叔节点的颜色对调即可。
127108 * 即原祖父节点是黑色，现在变成红色，父节点与叔叔节点都变成黑色。
128109 * 对于第二种，我们将新插入的节点为C,父节点为B,祖父节点为A.
129- * 如果BC都是左节点，要现将B右旋，然后调整B与C的颜色 ，即B变成黑色，A变成红色
130- * 如果BC都是右节点，要现将B左旋，然后调整B与C的颜色 ，即B变成黑色，A变成红色
110+ * 如果BC都是左节点，要现将A右旋，然后调整B与A的颜色 ，即B变成黑色，A变成红色
111+ * 如果BC都是右节点，要现将A左旋，然后调整B与A的颜色 ，即B变成黑色，A变成红色
131112 * 对于第三种，我们将新插入的节点为C,父节点为B,祖父节点为A.
132- * 如果C为右节点，B为左节点，要先将C左旋 ，然后就变成第二种的情况
133- * 如果C为左节点，B为右节点，要先将C右旋 ，然后就变成第二种的情况
113+ * 如果C为右节点，B为左节点，要先将B左旋 ，然后就变成第二种的情况
114+ * 如果C为左节点，B为右节点，要先B右旋 ，然后就变成第二种的情况
134115 *
135116 * @param node
136117 */
137118 private void insertFixUp (Node node ) {
119+ Node parent , grandParent , uncle ;
120+ while ((parent = parentOf (node )) != null && parent .isRed ()) {
121+ grandParent = parentOf (node );
122+ //如果父节点是祖父节点的左孩子
123+ if (parent == grandParent .left ) {
124+ uncle = grandParent .right ;
125+ //第一种情况
126+ if ((uncle != null ) && uncle .isRed ()) {
127+ uncle .makeBlack ();
128+ parent .makeBlack ();
129+ grandParent .makeRed ();
130+ node = grandParent ;
131+ continue ;
132+ }
133+ //将第三种情况变成第二种情况
134+ if (parent .right == node ) {
135+ Node tmp ;
136+ rotateLeft (parent );
137+ tmp = parent ;
138+ parent = node ;
139+ node = tmp ;
140+ }
141+ parent .makeBlack ();
142+ grandParent .makeRed ();
143+ rotateRight (grandParent );
144+ } else {
145+ uncle = grandParent .left ;
146+ if ((uncle != null ) && uncle .isRed ()) {
147+ uncle .makeBlack ();
148+ parent .makeBlack ();
149+ grandParent .makeRed ();
150+ node = grandParent ;
151+ continue ;
152+ }
153+
154+ if (parent .left == node ) {
155+ Node tmp ;
156+ rotateRight (parent );
157+ tmp = parent ;
158+ parent = node ;
159+ node = tmp ;
160+ }
161+
162+ parent .makeBlack ();
163+ grandParent .makeRed ();
164+ rotateLeft (grandParent );
165+
166+ }
167+
168+ }
169+
170+ root .makeBlack ();
171+ }
172+
173+
174+ /**
175+ * 对红黑树的节点(y)进行右旋转
176+ *
177+ * 右旋示意图(对节点y进行左旋)：
178+ * py py
179+ * / /
180+ * y x
181+ * / \ --(右旋)-. / \ #
182+ * x ry lx y
183+ * / \ / \ #
184+ * lx rx rx ry
185+ *
186+ * @param y 待旋转的节点
187+ */
188+ private void rotateRight (Node y ) {
189+
190+ Node x = y .left ;
191+
192+ // 将 “x的右孩子” 设为 “y的左孩子”；
193+ // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”
194+ y .left = x .right ;
195+ if (x .right != null )
196+ x .right .parent = y ;
197+
198+ // 将 “y的父亲” 设为 “x的父亲”
199+ x .parent = y .parent ;
200+
201+ if (y .parent == null ) {
202+ this .root = x ; // 如果 “y的父亲” 是空节点，则将x设为根节点
203+ } else {
204+ if (y == y .parent .right )
205+ y .parent .right = x ; // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”
206+ else
207+ y .parent .left = x ; // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
208+ }
138209
210+ // 将 “y” 设为 “x的右孩子”
211+ x .right = y ;
212+
213+ // 将 “y的父节点” 设为 “x”
214+ y .parent = x ;
215+ }
216+
217+ /**
218+ *
219+ * 对红黑树的节点(x)进行左旋转
220+ *
221+ * 左旋示意图(对节点x进行左旋)：
222+ * px px
223+ * / /
224+ * x y
225+ * / \ --(左旋)-. / \ #
226+ * lx y x ry
227+ * / \ / \
228+ * ly ry lx ly
229+ *
230+ * @param x 待旋转的节点
231+ */
232+ private void rotateLeft (Node x ) {
233+ Node y = x .getRight ();
234+ x .right = y .left ;
235+ if (y .left != null ) {
236+ y .left .parent = x ;
237+ }
238+ y .parent = x .parent ;
239+ if (x .parent == null ) {
240+ root = y ;
241+ }else {
242+ if (x .parent .left == x ) {
243+ x .parent .left = y ;
244+ }else {
245+ x .parent .right = y ;
246+ }
247+ }
248+ y .left = x ;
249+ x .parent = y ;
250+ }
139251
252+ private Node parentOf (Node node ) {
253+ return node != null ? node .parent : null ;
140254 }
141255
142256
@@ -147,7 +261,7 @@ static class Node {
147261 private Node left ;
148262 private Node right ;
149263
150- public Node (){
264+ public Node () {
151265
152266 }
153267
@@ -160,6 +274,7 @@ public Node(int value, boolean isRed) {
160274 this .value = value ;
161275 this .isRed = isRed ;
162276 }
277+
163278 public int getValue () {
164279 return value ;
165280 }
@@ -180,7 +295,7 @@ public boolean isRed() {
180295 return isRed ;
181296 }
182297
183- public boolean isBlack (){
298+ public boolean isBlack () {
184299 return !isRed ();
185300 }
186301
@@ -200,11 +315,11 @@ public void setRight(Node right) {
200315 this .right = right ;
201316 }
202317
203- public void makeRed (){
318+ public void makeRed () {
204319 isRed = true ;
205320 }
206321
207- public void makeBlack (){
322+ public void makeBlack () {
208323 isRed = false ;
209324 }
210325 }
0 commit comments