平衡二叉树概述以及左旋转实现思路

/*平衡二叉树(AVL树)概述解决了二叉排序树的一些问题举一个栗子给你1个数列{1,2,3,4,5,6}让你构造1棵二叉排序树根据左小右大原则你就会构造出来只有1直向右子树延申的所有节点最多只有1棵节点的二叉树也就是左子树全部为空此时你会发现你所构造的二叉排序树更像是1棵单链表这样的话，插入和删除速度不会受影响但查询速度会很慢甚至比单链表还要慢因为在查询的时候还需要判断左子树是否有节点解决方案平衡二叉树特点前提是二叉排序树是1棵空树或2棵子树的高度差绝对值不超过1并且左右2子树都是1棵平衡二叉树常见的实现方法有红黑树，替罪羊树，AVL算法，伸展树等；需求给你1个数列，要求创建1棵平衡二叉树{4,3,6,5,7,8}左旋转思路分析一旦右子树的高度 - 左子树的高度 > 1就采用左旋转降低右子树的高度如何进行左旋转1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r6. 当前节点的左子树指向新节点((NODE)value = 4)左旋转过后明显地发现原先根节点指向的右子树这条线已经断掉了实际上原来的右子树已经被销毁了新出现相同的节点只是副本而已想想有一种悲伤的感觉代码实现的话我会复用之前的Node1节点类*/

树的高度求解

// 将以下方法写进Node类，创建AVLT平衡二叉树类，将原先的二叉排序树类复制进class AVLT，这里就不展示源码了/*** 返回左子树的高度* 递归出口** @return 左子树的高度*/public int leftTreeHeight() {if (leftNode == null) {return 0;}return leftNode.maximumHeightOfTree();}/*** 返回右子树的高度* 递归出口** @return 右子树的高度*/public int rightTreeHeight() {if (rightNode == null) {return 0;}return rightNode.maximumHeightOfTree();}/*** 树的最大高度** @return 当前二叉树的最大高度*/public int maximumHeightOfTree() {/*程序进入方法体递归左子树和右子树再取最大值还要+1的原因是当前自己也要加上*/return Math.max(leftNode == null ? 0 : leftNode.maximumHeightOfTree(),rightNode == null ? 0 : rightNode.maximumHeightOfTree()) + 1;}

左右旋转的方法

/*** 左旋转方法*/public void rotateLeft() {/*程序开始进行左旋转操作1. 创建1个新节点，value等于当前根节点的值，创建1个当前指针，指向根节点2. 把新节点((NODE)value = 4)的左子树设置为当前节点((ROOT)value = 4)的左子树3. 把新节点的右子树设置为当前节点的右子树的左子树，如果没有指向null就行了4. 把当前节点的值换成右子节点的值((ROOT)value = 6)，注意只是换，还没开始移动呢5. 把当前节点的右子树设置为当前节点右子树的右子树((ROOT)value = 6).rightNode = ROOT.r.r6. 当前节点的左子树指向新节点((NODE)value = 4)此时默认value是根节点leftNode是根节点的左子树*/Node1 newNode = new Node1(value);newNode.leftNode = leftNode;newNode.rightNode = rightNode.leftNode;value = rightNode.value;rightNode = rightNode.rightNode;leftNode = newNode;}/*** 右旋转方法*/public void rotateRight() {/*右旋转实现思路1. 创建1个新节点，为当前根节点的值((NEW_NODE)value = 10)2. 新节点的右子树((NEW_NODE).r)设置为当前节点的右子树((ROOT).r)3. 新节点的左子树((NEW_NODE).l)设置为当前节点左子树的右子树((ROOT).l.r)4. 把当前根节点的值((ROOT).value)换成左子树节点的值((ROOT).l.value)5. 当前节点的左子树设置为当前节点左子树的左子树6. 把当前节点的右子树设置为新节点此时根节点的左子树节点已经被销毁了因为没有任何引用指向该节点*/Node1 newNode = new Node1(value);newNode.rightNode = rightNode;newNode.leftNode = leftNode.rightNode;value = leftNode.value;leftNode = leftNode.leftNode;rightNode = newNode;}/*** 插入节点的方法** @param node 需要插入的节点*/public void insertNode(Node1 node) {if (node == null) {return;}/*程序运行到此处此时可以判断插入的节点和根节点的关系this.value表示根节点的值*/if (node.value < this.value) {if (this.leftNode == null) {/*程序运行到此处说明当前插入的节点比根节点的值小并且根节点的左子树位空直接插入即可*/this.leftNode = node;} else {this.leftNode.insertNode(node);}} else {/*程序运行到此处说明当前节点比根节点大需要插入到右子树*/if (this.rightNode == null) {this.rightNode = node;} else {this.rightNode.insertNode(node);}}/*程序运行到此处应该判断左子树和右子树的高度如果右子树的高度 - 左子树的高度 > 1应该左旋转如果左子树的高度 - 右子树的高度 > 1应该右旋转*/if (rightTreeHeight() - leftTreeHeight() > 1) {/*程序运行到此处先不考虑那么多直接左旋转*/rotateLeft();}if (leftTreeHeight() - rightTreeHeight() > 1) {rotateRight();}}

实现双旋转

/*这里分析几个特殊的情况比如给你1个数组{10,11,7,6,8,9}构造完二叉排序树此时满足右旋转的条件但进行右旋转过后仍然不是1棵平衡二叉树双旋转思路分析和条件1. 满足右旋转的条件2. 左子树的右子树高度 > 右子树高度3. 先对当前这个节点的左节点进行左旋转4. 再对当前根节点进行右旋转即可*//*** 插入节点的方法** @param node 需要插入的节点*/public void insertNode(Node1 node) {if (node == null) {return;}/*程序运行到此处此时可以判断插入的节点和根节点的关系this.value表示根节点的值*/if (node.value < this.value) {if (this.leftNode == null) {/*程序运行到此处说明当前插入的节点比根节点的值小并且根节点的左子树位空直接插入即可*/this.leftNode = node;} else {this.leftNode.insertNode(node);}} else {/*程序运行到此处说明当前节点比根节点大需要插入到右子树*/if (this.rightNode == null) {this.rightNode = node;} else {this.rightNode.insertNode(node);}}/*程序运行到此处应该判断左子树和右子树的高度如果右子树的高度 - 左子树的高度 > 1应该左旋转如果左子树的高度 - 右子树的高度 > 1应该右旋转注意这里需要判断是否满足双旋转的条件*/if (rightTreeHeight() - leftTreeHeight() > 1) {if (rightNode != null && rightNode.leftTreeHeight() > rightNode.rightTreeHeight()) {rightNode.rotateRight();rotateLeft();}else {rotateLeft();}return;}if (leftTreeHeight() - rightTreeHeight() > 1) {if (leftNode != null && leftNode.rightTreeHeight() > leftNode.leftTreeHeight()) {leftNode.rotateLeft();rotateRight();}else {rotateRight();}}}

总目录