前言
二叉搜索树在一般情况下它的查找时间复杂度是 O(log n). 但在一些特殊的情况下, 它会退化为斜树变成线性结构, 导致查询效率大大降低, 根本发挥不出折半查找的优势. 因此, 就需要一种平衡的二叉搜索树来达到我们期望查询时间复杂度为 O(log n) 的数据结构, 那就是平衡二叉搜索树.
平衡二叉搜索树
平衡二叉搜索树又叫 AVL 树, 它具有以下性质:
1. 任一节点对应的两棵子树的最大高度差为 1.
2. 两棵子树都是平衡二叉树.
通过保证上面 2 条规则, 因此它也被称为高度平衡树. 查找, 插入和删除在平均和最坏情况下的时间复杂度都是 O(log n). 因此, 它是一颗相对稳定的树.
为了保证左右 2 棵子树的最大高度差为 1, 我们需要在插入和删除时, 对树进行旋转操作, 以保证树的平衡性. 有 2 种基本的操作, 那就是左旋和右旋.
树的左旋和右旋
在进行左右旋转时, 会出现四种可能性:
1. 左左形态
当 x 是 y 的左节点, y 又是 z 的左节点时, 这个时候只需要把 y 节点向右旋转即可. 如下图:
左左
2. 左右形态
当 x 是 y 的右节点, 而 y 又是 z 的左节点时, 需要先把 y 左旋, 变成 左左形态, 然后再把 z 右旋. 如下图:
左右
3. 右右形态
当 x 是 y 的右节点, y 又是 z 的右节点时, 这时候只需要把 y 节点向左旋转即可. 如下图:
右右
4. 右左形态
当 x 是 y 的左节点, 而 y 又是 z 的右节点时, 需要先把 y 右旋, 变成 右右形态, 然后再把 z 左旋. 如下图:
右左
平衡二叉树的实现
- public class AVLTree {
- // 获取左右节点的高度差
- public int getBalance(Node n) {
- if (n != null) {
- return (getHeight(n.left) - getHeight(n.right));
- }
- return 0;
- }
- // 获取节点的高度
- public int getHeight(Node n) {
- if (n != null) {
- return n.height;
- }
- return 0;
- }
- // 右旋
- public Node rightRotate(Node y) {
- Node x = y.left;
- Node T2 = x.right;
- // 旋转
- x.right = y;
- y.left = T2;
- // 更新节点的高度
- x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
- y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
- return x;
- }
- // 左旋
- public Node leftRotate(Node x) {
- Node y = x.right;
- Node T2 = y.left;
- // 旋转
- y.left = x;
- x.right = T2;
- // 更新节点的高度
- x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
- y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
- return y;
- }
- public Node insert(Node node, int data) {
- if (node == null) {
- return (new Node(data));
- }
- if (node.data> data) {
- node.left = insert(node.left, data);
- } else {
- node.right = insert(node.right, data);
- }
- // 更新节点的高度
- node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
- int balDiff = getBalance(node);
- // 右旋
- if (balDiff> 1 && data <node.left.data) {
- return rightRotate(node);
- }
- // 左旋
- if (balDiff < -1 && data> node.right.data) {
- return leftRotate(node);
- }
- // 先左旋在右旋
- if (balDiff> 1 && data> node.left.data) {
- node.left = leftRotate(node.left);
- return rightRotate(node);
- }
- // 先右旋在左旋
- if (balDiff < -1 && data < node.right.data) {
- node.right = rightRotate(node.right);
- return leftRotate(node);
- }
- return node;
- }
- }
- class Node {
- int data;
- Node left;
- Node right;
- int height;
- public Node(int data) {
- this.data = data;
- height = 1;
- }
- }
总结
二叉搜索树的不稳定性, 就有可能退化为近似链或链, 查询时间复杂度就退化为 O(n). 当 n 很大的时候, 性能就大大降低, 达不到折半的效果. 因此, 我们需要一个平衡的二叉搜索树.
平衡二叉树是通过对树节点的左旋和右旋来保证树的平衡性, 也就是保证左右子树的高度差不超过 1.
在对树进行左旋和右旋时, 有四种形态分别是: 左左, 左右, 右右, 右左.
因此, 平衡二叉树的查找, 插入和删除在平均和最坏情况下的时间复杂度都是 O(log n).
PS:
清山绿水始于尘, 博学多识贵于勤.
我有酒, 你有故事吗?
公众号:「清尘闲聊」.
欢迎一起谈天说地, 聊代码.
来源: http://www.jianshu.com/p/dcd2a1f03983