平衡二叉树

排序二叉树中存在一个问题就是可能会退化成一个链表，当只有左子树或者右子树有节点的时候，此时排序二叉树就像链表一样，但因为排序二叉树在插入查询的时候还要判断左右子树的问题，这样查询的效率反而变低，从而引出了平衡二叉树

平衡二叉树又称平衡搜索树(Self-balance Binary Search Tree)又称AVL树，同时保证了查询和添加的效率。首先平衡二叉树是一颗排序二叉树，且它是空树或者他的每一个节点分支的左右两颗子树的高度差值的绝对值小于等于1。平衡二叉树的实现方法主要有红黑树，AVL，替罪羊树，Treap，伸展树等

• 平均查找长度 找到每一个因子的路径(或者每层因子的个数*当前层K) / 所有因子个数

• 平衡因子( Balancer Factor BF) 记为BF(T) = hl -hr hl 和hr分别为T的左右子树的高度

• 如果一个K层的平衡二叉树 最小节点数为 Nk = K-1层节点数 + K-2层节点数 +1 类似斐波那契数列 +1 (K > 0) 如果一个节点数为n的AVL树的最大高度为O(log2n)

• **最小不平衡子树：**指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

二叉树的旋转

因为顺序插入二叉树的关系，在插入节点时可能会引起整个树的不平衡，此时需要通过旋转节点的方式重新让树回到平衡的状态

左旋转步骤

1. 创建一个临时节点用于保存当前失衡节点的值 temp = new Node
2. 将临时节点的left指向 失衡节点的left temp.left = this.left
3. 将临时节点的right指向 失衡节点的右节点的左子树 temp.right = this.right.left
4. 将失衡节点的值修改为right的值 this.data = right.data
5. 将失衡节点的right指向 右节点的right this.right= left.right
6. 将失衡节点的left指向temp临时节点 this.left = temp

右旋转步骤

1. 创建一个临时节点保存当前失衡节点的值 temp = new Node
2. 临时节点的right指向失衡节点的right temp.right = this.right
3. 临时节点的left指向失衡节点的左节点的右子树 temp.left = this.left.right
4. 将失衡节点的值改为 失衡节点的left的值 this.data = left.data
5. 将失衡节点的left指向 失衡节点左节点的left this.left = left.left
6. 将失衡节点的right指向 temp this.right = temp

双旋转

1. 当整体需要右旋转 left.height - right.height >1 且 失衡节点的左节点的右子树高度大于其左子树高度的时即 left.rightHeight > left.leftHeight 需要进行双旋转 先将失衡节点的left进行左旋转left.leftRotate 再对失衡节点进行右旋转
2. 当整体需要左旋转 right.height - left.height >1 且 失衡节点的右子树的左子树高度大于其右子树 即 right.leftHeight > right.rightHeight 时需要将失衡节点的right节点先进行右旋转即right.rightRotate 再对失衡节点进行左旋转

旋转代码示例

 /*** 左旋转*/public void leftRotate() {// 1. 创新一个新的节点 暂存失衡节点AvlNode tempNode = new AvlNode(this.data);// 2. 新节点的左节点为失衡节点的左节点tempNode.left = this.left;// 3. 新节点的右节点为失衡节点的右节点的左节点tempNode.right = this.right.left;// 4. 当前失衡节点的值改为 失衡节点的右节点的值this.data = this.right.data;// 5. 当前失衡节点的右节点指向 右右节点  下移一位this.right = this.right.right;// 6. 当前节点的左节点指向临时节点即可this.left = tempNode;}/*** 将节点右旋转*/public void rightRotate() {// 1. 创建一个临时节点保存该节点的值AvlNode tempNode = new AvlNode(this.data);// 2. 新节点的右节点连接失衡节点的右节点 新节点的左节点连接失衡节点的左节点的右子树tempNode.right = this.right;tempNode.left = this.left.right;// 3. 当前节点的值改为 当前节点左节点的值this.data = this.left.data;// 4. 当前节点的左节点 指向 左左节点this.left = this.left.left;// 5. 当前节点右节点 指向新的temp节点this.right = tempNode;}/*** 获取给节点的高度** @return*/public int height() {return Math.max(this.left == null ? 0 : left.height(), this.right == null ? 0 : right.height()) + 1;}/*** 左子树高度** @return*/public int leftHeight() {if (left == null) {return 0;}return left.height();}/*** 右子树高度** @return*/public int rightHeight() {if (right == null) {return 0;}return right.height();}

添加平衡调整代码

   /*** 与BST树添加方法一样** @param node*/public void add(AvlNode node) {if (this.data > node.data) {if (this.left == null) {this.left = node;} else {this.left.add(node);}}if (this.data <= node.data) {if (this.right == null) {this.right = node;} else {this.right.add(node);}}// 添加完整之后需要将树重新调整平衡if (leftHeight() - rightHeight() > 1) {// 左子树比右子树高度大于1 进行右旋转if (left != null && left.leftHeight() < left.rightHeight()) {// 如果失衡节点的左节点的 的左子树高度小于右子树高度 需要先让左子节点进行左旋转left.leftRotate();}rightRotate();}if (rightHeight() - leftHeight() > 1) {// 右子树的高度比左子树高度差大于1 需要左旋转if (right != null && right.leftHeight() > right.rightHeight()) {// 如果失衡节点的右节点 的右子树高度小于左子树高度 需要先将失衡节点的右子树进行右旋转right.rightRotate();}leftRotate();}}

完整代码演示

public class AvlTreeDemo {public static void main(String[] args) {
//        int[] arr = {4, 3, 6, 5, 7, 8}; // 右旋转int[] arr = {10, 12, 8, 9, 7, 6}; // 左旋转
//        int[] arr = {10, 11, 7, 6, 8, 9}; ////创建一个 AVLTree对象AvlTree avlTree = new AvlTree();//添加结点for (int i = 0; i < arr.length; i++) {avlTree.add(new AvlNode(arr[i]));}System.out.println("在平衡处理~~");System.out.println("树的高度=" + avlTree.root.height());System.out.println("树的根节点=" + avlTree.root);System.out.println("在平衡之后中序遍历~~");avlTree.inOrderTraversal();//        System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());
//        System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());
//        System.out.println("当前的根结点=" + avlTree.getRoot());//8}
}/*** AVL 平衡二叉树*/
class AvlTree {AvlNode root;/*** 左子树高度** @return*/public int leftTreeHeight() {if (root.left != null) {return root.left.height();}return 0;}/*** 右子树高度** @return*/public int rightTreeHeight() {if (root.right != null) {return root.right.height();}return 0;}/*** 获取树的高度*/public int height() {if (root == null) {return 0;}return root.height();}/*** 添加方法** @param node*/public void add(AvlNode node) {if (root == null) {root = node;} else {root.add(node);}}public void inOrderTraversal() {if (root == null) {throw new RuntimeException("root is null!");} else {root.inOrderTraversal();}}}/*** 平衡树节点*/
class AvlNode {AvlNode left;AvlNode right;int data;public AvlNode(int data) {this.data = data;}@Overridepublic String toString() {return "Node{" +"data=" + data +'}';}/*** 左旋转*/public void leftRotate() {// 1. 创新一个新的节点 暂存失衡节点AvlNode tempNode = new AvlNode(this.data);// 2. 新节点的左节点为失衡节点的左节点tempNode.left = this.left;// 3. 新节点的右节点为失衡节点的右节点的左节点tempNode.right = this.right.left;// 4. 当前失衡节点的值改为 失衡节点的右节点的值this.data = this.right.data;// 5. 当前失衡节点的右节点指向 右右节点  下移一位this.right = this.right.right;// 6. 当前节点的左节点指向临时节点即可this.left = tempNode;}/*** 将节点右旋转*/public void rightRotate() {// 1. 创建一个临时节点保存该节点的值AvlNode tempNode = new AvlNode(this.data);// 2. 新节点的右节点连接失衡节点的右节点 新节点的左节点连接失衡节点的左节点的右子树tempNode.right = this.right;tempNode.left = this.left.right;// 3. 当前节点的值改为 当前节点左节点的值this.data = this.left.data;// 4. 当前节点的左节点 指向 左左节点this.left = this.left.left;// 5. 当前节点右节点 指向新的temp节点this.right = tempNode;}/*** 获取给节点的高度** @return*/public int height() {return Math.max(this.left == null ? 0 : left.height(), this.right == null ? 0 : right.height()) + 1;}/*** 左子树高度** @return*/public int leftHeight() {if (left == null) {return 0;}return left.height();}/*** 右子树高度** @return*/public int rightHeight() {if (right == null) {return 0;}return right.height();}/*** 是否是叶子节点** @return*/public boolean isLeaf() {return left == null && right == null;}/*** 与BST树添加方法一样** @param node*/public void add(AvlNode node) {if (this.data > node.data) {if (this.left == null) {this.left = node;} else {this.left.add(node);}}if (this.data <= node.data) {if (this.right == null) {this.right = node;} else {this.right.add(node);}}// 添加完整之后需要将树重新调整平衡if (leftHeight() - rightHeight() > 1) {// 左子树比右子树高度大于1 进行右旋转if (left != null && left.leftHeight() < left.rightHeight()) {// 如果失衡节点的左节点的 的左子树高度小于右子树高度 需要先让左子节点进行左旋转left.leftRotate();}rightRotate();}if (rightHeight() - leftHeight() > 1) {// 右子树的高度比左子树高度差大于1 需要左旋转if (right != null && right.leftHeight() > right.rightHeight()) {// 如果失衡节点的右节点 的右子树高度小于左子树高度 需要先将失衡节点的右子树进行右旋转right.rightRotate();}leftRotate();}}/*** 中序遍历  先左 再中 后右*/public void inOrderTraversal() {if (this.left != null) {this.left.inOrderTraversal();}System.out.print(this + "\t");if (this.right != null) {this.right.inOrderTraversal();}}}