数据结构和部分算法题解.zip

package data.avl; import data.linkliststruct.LinkedListQueue; import data.map.BinarySearchTreeMap; import data.map.Map; import java.util.ArrayList; import java.util.Stack; /** * @Author: liyuzhan * @classDesp： 平衡二叉树(加上自平衡机制) * @Date: 2020/3/10 10:08 * @Email: 1031759184@qq.com */ public class AVLTree<K extends Comparable<K>, V> implements Map<K, V> { /** * 树节点 */ private class Node { public K key; public V value; public Node left, right; public int height; public Node(K key, V value) { this.key = key; this.value = value; left = null; right = null; height = 1; } } private Node root; private int size; public AVLTree() { root = null; size = 0; } @Override public void add(K key, V value) { root = add(root, key, value); } private Node add(Node node, K key, V value) { if (node == null) { size++; return new Node(key, value); } if (key.compareTo(node.key) < 0) { node.left = add(node.left, key, value); } else if (key.compareTo(node.key) > 0) { node.right = add(node.right, key, value); } else { node.value = value; } //更新height node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); //计算平衡因子 int balanceFactor = getBalanceFactor(node); //平衡维护 //右旋转LL if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } //左旋转RR if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { return leftRotate(node); } //先左旋再右旋 LR if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } //先右旋再左旋 RL if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; } @Override public V remove(K key) { Node node = getNode(root, key); if (node != null) { root = remove(root, key); return node.value; } return null; } private Node minimum(Node node) { if (node.left == null) { return node; } return minimum(node.left); } private Node remove(Node node, K key) { if (node == null) { return null; } Node retNode; if (key.compareTo(node.key) < 0) { node.left = remove(node.left, key); retNode = node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right, key); retNode = node; } else { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; retNode = rightNode; } if (node.right == null) { Node leftNode = node.left; node.left = null; size--; retNode = leftNode; } //待删除节点左右子树均不为空 //找到比待删除节点大的最小节点（后继节点），即待删除节点右子树的最小节点 //用这个节点顶替待删除节点的位置 else { Node successor = minimum(node.right); successor.right = remove(node.right, successor.key); successor.left = node.left; node.left = node.right = null; retNode = successor; } } if (retNode == null) { return null; } //更新height retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); //计算平衡因子 int balanceFactor = getBalanceFactor(retNode); //平衡维护 //右旋转LL if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) { return rightRotate(retNode); } //左旋转RR if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) { return leftRotate(retNode); } //先左旋再右旋 LR if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { retNode.left = leftRotate(retNode.left); return rightRotate(retNode); } //先右旋再左旋 RL if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { retNode.right = rightRotate(retNode.right); return leftRotate(retNode); } return retNode; } private Node removeMin(Node node) { if (node.left == null) { Node rightNode = node.right; node.right = null; size--; return rightNode; } node.left = removeMin(node.left); return node; } @Override public boolean contain(K key) { return getNode(root, key) != null; } @Override public V get(K key) { Node node = getNode(root, key); return node == null ? null : node.value; } private Node getNode(Node node, K key) { if (node == null) { return null; } if (key.compareTo(node.key) == 0) { return node; } else if (key.compareTo(node.key) < 0) { return getNode(node.left, key); } else { return getNode(node.right, key); } } @Override public void set(K key, V newValue) { Node node = getNode(root, key); if (node == null) { throw new IllegalArgumentException(key + "doesn't exist!"); } node.value = newValue; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } /** * 返回节点所对应的高度值 * * @param node 传入的节点 * @return 高度值 */ private int getHeight(Node node) { if (node == null) { return 0; } return node.height; } /** * 计算节点的平衡因子 * * @param node 传入节点 * @return 平衡因子 */ private int getBalanceFactor(Node node) { if (node == null) { return 0; } return getHeight(node.left) - getHeight(node.right); } /** * 判断该二叉树是否是一颗二分搜索树 * * @return 是否是二分搜索树 */ public boolean isBst() { ArrayList<K> keys = new ArrayList<>(); inOrder(root, keys); for (int i = 1; i < keys.size(); i++) { if (keys.get(i - 1).compareTo(keys.get(i)) > 0) { return false; } } return true; } /** * 二叉树中序遍历 * * @param node 当前节点 * @param keys 获取中序遍历后的键的数组 */ private void inOrder(Node node, ArrayList<K> keys) { if (node == null) { return; } inOrder(node.left, keys); keys.add(node.key); inOrder(node.right, keys); } /** * 判断该二叉树是否是一颗AVL树 * * @return 是否是一颗AVL树 */ public boolean isBalanced() { return isBalanced(root); } /** * 判断该节点为根的二叉树是否是一颗AVL树，递归算法 * * @param node 当前节点 * @return 是否是一颗AVL树 */ private boolean isBalanced(Node node) { if (node == null) { return true; }