2023新版數(shù)據(jù)結(jié)構(gòu)與算法Java視頻教程（上篇），java高級程序員必學(xué)的數(shù)據(jù)
所有的旋轉(zhuǎn)關(guān)鍵是知道要轉(zhuǎn)成啥樣，畫個圖，標(biāo)注中序遍歷，代碼就信手拈來了。
右旋
/**
* <ol>
* <li> 旋轉(zhuǎn)掛載 </li>
* <li> 處理 parent </li>
* <li> 旋轉(zhuǎn)后直接建立 層級關(guān)系 </li>
* </ol>
* <br>
* ---------- ---------- ---------- ---------- ---------- ---------- ----------
* | lastLevelNode | |
* | | | |
* | 8R. | lastLevelNode |
* | / \ | | |
* | 5B. 10B | 5B. |
* | / \ / \ | / \ |
* | 3R 6B. 9R 11R | 3R 8R. |
* | / \ \ | / \ / \ |
* | 2B 4B 7R | 2B 4B 6B. 10B |
* | / | / \ / \ |
* | 1R | 1R 7B 9R 11R |
* | 1 2 3 4 5 6 7 8 9 10 11 | 1 2 3 4 5 6 7 8 9 10 11 |
* | | |
* ---------- ---------- ---------- ---------- ---------- ---------- ----------
*/
public void rightRotate(Node n8) {
Node lastLevelNode = n8.parent;
//boolean isLastLeft = n8.isLeft();
// 1、旋轉(zhuǎn)掛載
Node n5 = n8.left;
Node n6 = n5.right;
n5.right = n8;
n8.left = n6;
// 2、處理 parent
//n5.parent = null;// 錯誤
n5.parent = lastLevelNode;
n8.parent = n5;
if (n6 != null) {
n6.parent = n8;
}
// 6、旋轉(zhuǎn)后直接建立 層級關(guān)系
//Node lastLevelNode = n5.parent;
if (lastLevelNode != null) {
//if (isLastLeft) {
// lastLevelNode.left = n5;
//}else {
// lastLevelNode.right = n5;
//}
if (lastLevelNode.left == n8) {
lastLevelNode.left = n5;
} else {
lastLevelNode.right = n5;
}
} else {
root = n5;
}
}
左旋
/**
* <p>
* 左旋
* <p>
* 大道至簡圖 <br>
* ---------- ---------- ---------- ---------- ---------- ----------
* | | |
* | ntParent | ntParent |
* | | | | |
* | nT | nR |
* | \ | / |
* | nR | nT |
* | / | \ |
* | nRL | nRL |
* | T RL R | T RL R |
* ---------- ---------- ---------- ---------- ---------- ----------
*/
private void leftRotate(Node nT) {
Node ntParent = nT.parent;
Node nR = nT.right;
Node nRL = nR.left;
nT.right = nRL;
nR.left = nT;
nR.parent = ntParent;
nT.parent = nR;
if (nRL != null) {
nRL.parent = nT;
}
if (ntParent == null) {
root = nR;
} else if (ntParent.left == nT) {
ntParent.left = nR;
} else {
ntParent.right = nR;
}
}
大學(xué)用C++做項目和練習(xí)，工作一直java，所以C++手生，一直想用java寫數(shù)據(jù)結(jié)構(gòu)，這樣就可以順利用java刷leetcode，但是自己搞彎路特別多。感謝滿老師
標(biāo)簽：
