2023新版数据结构与算法Java视频教程（上篇），java高级程序员必学的数据

所有的旋转关键是知道要转成啥样，画个图，标注中序遍历，代码就信手拈来了。

右旋

/**
 * <ol>
 *     <li> 旋转挂载 </li>
 *     <li> 处理 parent </li>
 *     <li> 旋转后直接建立 层级关系 </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、旋转挂载

    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、旋转后直接建立 层级关系
    //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;
    }

}

大学用C++做项目和练习，工作一直java，所以C++手生，一直想用java写数据结构，这样就可以顺利用java刷leetcode，但是自己搞弯路特别多。感谢满老师