avl树的实现与测试总结（数据结构AVL树了解一下）

avl树的实现与测试总结（数据结构AVL树了解一下）下面我们通过java代码来实现AVL树，供大家参考。根据上述我们也看到了，AVL树是根据一次或者多次树旋转，得以实现平衡，那么我们来了解一下它是怎么做到的。二叉树2根据二叉树1与二叉树2比较可以看到，当在构建树的时为有序时，二叉查找树就及可能蜕变为单支树（或者说是一个链表），这样也就失去二叉树的意义，所以我们介绍新的数据结构AVL树。在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O (log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization

写在前面

在讲AVL树之前，我们首先需要有二叉搜索树的基础，那么我们先来了解一下二叉搜索树。

二叉查找树：（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

简单用几个图来表示如下：

二叉树1

二叉树2

根据二叉树1与二叉树2比较可以看到，当在构建树的时为有序时，二叉查找树就及可能蜕变为单支树（或者说是一个链表），这样也就失去二叉树的意义，所以我们介绍新的数据结构AVL树。

AVL树（平衡二叉查找树）

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O (log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

根据上述我们也看到了，AVL树是根据一次或者多次树旋转，得以实现平衡，那么我们来了解一下它是怎么做到的。

• 右旋转

• 左旋转

下面我们通过java代码来实现AVL树，供大家参考。

import java.util.ArrayList; public class AVLTree<K extends Comparable<K> V> { private Node root; private int size; public AVLTree() { root = null; size = 0; } // 向二分搜索树中添加新的元素(key value) public void add(K key V value) { root = add(root key value); } public boolean contains(K key) { return getNode(root key) != null; } public V get(K key) { Node node = getNode(root key); return node == null ? null : node.value; } public int getSize() { return size; } // 判断该二叉树是否是一棵二分搜索树 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; } // 判断该二叉树是否是一棵平衡二叉树 public boolean isBalanced() { return isBalanced(root); } public boolean isEmpty() { return size == 0; } // 从二分搜索树中删除键为key的节点 public V remove(K key) { Node node = getNode(root key); if (node != null) { root = remove(root key); return node.value; } return null; } 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; } // 向以node为根的二分搜索树中插入元素(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 // key.compareTo(node.key) == 0 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; } // 获得节点node的平衡因子 private int getBalanceFactor(Node node) { if (node == null) { return 0; } return getHeight(node.left) - getHeight(node.right); } // 获得节点node的高度 private int getHeight(Node node) { if (node == null) { return 0; } return node.height; } // 返回以node为根节点的二分搜索树中，key所在的节点 private Node getNode(Node node K key) { if (node == null) return null; if (key.equals(node.key)) return node; else if (key.compareTo(node.key) < 0) return getNode(node.left key); else // if(key.compareTo(node.key) > 0) return getNode(node.right key); } private void inOrder(Node node ArrayList<K> keys) { if (node == null) { return; } inOrder(node.left keys); keys.add(node.key); inOrder(node.right keys); } // 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法 private boolean isBalanced(Node node) { if (node == null) { return true; } int balanceFactor = getBalanceFactor(node); if (Math.abs(balanceFactor) > 1) { return false; } return isBalanced(node.left) && isBalanced(node.right); } // 对节点y进行向左旋转操作，返回旋转后新的根节点x // y x // / \ / \ // T1 x 向左旋转 (y) y z // / \ - - - - - - - -> / \ / \ // T2 z T1 T2 T3 T4 // / \ // T3 T4 private Node leftRotate(Node y) { Node x = y.right; Node T2 = x.left; // 向左旋转过程 x.left = y; y.right = T2; // 更新height y.height = Math.max(getHeight(y.left) getHeight(y.right)) 1; x.height = Math.max(getHeight(x.left) getHeight(x.right)) 1; return x; } // 返回以node为根的二分搜索树的最小值所在的节点 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); // return node; retNode = node; } else if (key.compareTo(node.key) > 0) { node.right = remove(node.right key); // return node; retNode = node; } else { // key.compareTo(node.key) == 0 // 待删除节点左子树为空的情况 if (node.left == null) { Node rightNode = node.right; node.right = null; size--; // return rightNode; retNode = rightNode; } // 待删除节点右子树为空的情况 else if (node.right == null) { Node leftNode = node.left; node.left = null; size--; // return leftNode; retNode = leftNode; } // 待删除节点左右子树均不为空的情况 else { // 找到比待删除节点大的最小节点 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right); //successor.right = removeMin(node.right); successor.right = remove(node.right successor.key); successor.left = node.left; node.left = node.right = null; // return successor; 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; } // 对节点y进行向右旋转操作，返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Node rightRotate(Node y) { Node x = y.left; Node T3 = x.right; // 向右旋转过程 x.right = y; y.left = T3; // 更新height y.height = Math.max(getHeight(y.left) getHeight(y.right)) 1; x.height = Math.max(getHeight(x.left) getHeight(x.right)) 1; return x; } private class Node { public int height; public K key; public Node left right; public V value; public Node(K key V value) { this.key = key; this.value = value; left = null; right = null; height = 1; } } }

https://github.com/gzdzss/tree/blob/master/src/AVLTree.java