数据结构重读 – 平衡二叉树(AVL树)

大二那会根本没蹋下心来看,觉得天书一般,连旋转都没搞明白。

今天仔细看了书,发现真的一点不难啊,鄙视自己……

首先是概念:

平衡二叉树是为了解决前面二叉排序树不均衡的问题,而加入了一种平衡机制。所以,平衡二叉树是一种特殊的二叉排序树(BST)

AVL树查找的平均和最差复杂度都是O(logn) !!!(BST的最坏是O(n))

AVL树的插入复杂度是O(logn)。

平衡二叉树(简称AVL树):对任意一个结点,它的左子树和又子树都是平衡二叉树(左子树都小于结点,右子树都大于结点),且左子树深度和右子树深度不超过1。

书上那个平衡因子的概念只是为了辅助书上的实现方法,没有太大意义。

一般是在AVL树的构造(插入)阶段,做树的平衡处理(左、右旋),使得它称为一个平衡二叉树。

可以证明,AVL树的深度是logN

中序遍历AVL树(其实这是二叉排序树),可以从小到大还原出一个序列

下面的图摘自董师兄的博客《数据结构之AVL树》

一般,我们在插入时会遇到4种不平衡情况:

(1)Insert在左子树的左子树,此时需要根右旋转。

(2)Insert在左子树的右子树,此时先要对左子树左旋转,然后对根右旋转。

(3)Insert在右子树的右子树,此时需要根左旋转。

(4)Insert在右子树的左子树,此时先要对右子树右旋转,然后对根左旋转。

我们的实现中,没有用平衡因子,而是直接记录每个结点子树的深度,如下:

public class AVLNode {
	public AVLNode(int data) {
		this.data = data;
	}

	public int data;
	public AVLNode left = null;
	public AVLNode right = null;
	public int depth = 0;
}

为了方便处理null结点的深度,我们定义如下深度函数:

当空结点为-1时,它的父亲结点+1正好是0。

	public static int Depth(AVLNode node) {
		if (node == null) {
			return -1;
		} else {
			return node.depth;
		}
	}

然后是左旋操作:

特别注意:更新结点时要先更新下面的(原tree结点),再更新新的mid

返回要返回mid。

	public static AVLNode RotateLeft(AVLNode tree) {
		// Rotate right
		AVLNode mid = tree.right;
		tree.right = mid.left;
		mid.left = tree;

		// Update depth (Notify the sequence)
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		mid.depth = Math.max(Depth(mid.left), Depth(mid.right)) + 1;
		return mid;
	}

同理,右旋操作:

	public static AVLNode RotateRight(AVLNode tree) {
		// Rotate left
		AVLNode mid = tree.left;
		tree.left = mid.right;
		mid.right = tree;

		// Update depth (Notify the sequence)
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		mid.depth = Math.max(Depth(mid.left), Depth(mid.right)) + 1;
		return mid;
	}

好了,下面是插入的代码:

特别注意,Java中的引用实际是C++中的指针,即对函数传入的“临时变量”修改,将不会影响外围原变量

因此,我们每次需要返回这个树引用。调用时也应该是

tree = Insert(tree, data);
public static AVLNode Insert(AVLNode tree, int data) {
		if (tree == null) {
			tree = new AVLNode(data);
		} else {
			if (data < tree.data) {
				// Insert at left child
				tree.left = Insert(tree.left, data);
				if (Depth(tree.left) - Depth(tree.right) == 2) {
					// Need balance
					if (data < tree.left.data) {
						// Insert at left child's left child
						// Left-Rotate
						tree = RotateRight(tree);
					} else if (data > tree.left.data) {
						// Insert at left child's right child
						// First Left-rotate tree's left child
						// Then Right-rotate tree
						tree.left = RotateLeft(tree.left);
						tree = RotateRight(tree);
					}
				}
			} else if (data > tree.data) {
				// Insert at right child
				tree.right = Insert(tree.right, data);
				if (Depth(tree.left) - Depth(tree.right) == -2) {
					if (data > tree.right.data) {
						// Insert at right child's right
						// Left-Rotate
						tree = RotateLeft(tree);
					} else if (data < tree.right.data) {
						// Insert at right child's left

						// First Right-rotate on tree's right child
						tree.right = RotateRight(tree.right);
						// Then Left-rotate tree
						tree = RotateLeft(tree);
					}
				}
			}
		}
		// Update depth
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		return tree;
	}

查找和排序二叉树一样的,如下:

public static boolean Find(AVLNode tree, int key) {
		AVLNode ptr = tree;
		while (true) {
			if (ptr == null) {
				break;
			}
			if (key == ptr.data) {
				return true;
			} else if (key < ptr.data) {
				ptr = ptr.left;
			} else {
				ptr = ptr.right;
			}
		}
		return false;
	}

好了,上面的版本有点土,用了Java还用static,下面这个版本是将AVLNode封装在了类内。调用时候不用在保存更新的AVLNode了,内部处理了,如下:

import java.util.Random;

public class AVLTree {

	private int Depth(AVLNode node) {
		if (node == null) {
			return -1;
		} else {
			return node.depth;
		}
	}

	private AVLNode RotateRight(AVLNode tree) {
		// Rotate left
		AVLNode mid = tree.left;
		tree.left = mid.right;
		mid.right = tree;

		// Update depth (Notify the sequence)
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		mid.depth = Math.max(Depth(mid.left), Depth(mid.right)) + 1;
		return mid;
	}

	private AVLNode RotateLeft(AVLNode tree) {
		// Rotate right
		AVLNode mid = tree.right;
		tree.right = mid.left;
		mid.left = tree;

		// Update depth (Notify the sequence)
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		mid.depth = Math.max(Depth(mid.left), Depth(mid.right)) + 1;
		return mid;
	}

	private AVLNode Insert(AVLNode tree, int data) {
		if (tree == null) {
			tree = new AVLNode(data);
		} else {
			if (data < tree.data) {
				// Insert at left child
				tree.left = Insert(tree.left, data);
				if (Depth(tree.left) - Depth(tree.right) == 2) {
					// Need balance
					if (data < tree.left.data) {
						// Insert at left child's left child
						// Left-Rotate
						tree = RotateRight(tree);
					} else if (data > tree.left.data) {
						// Insert at left child's right child
						// First Left-rotate tree's left child
						// Then Right-rotate tree
						tree.left = RotateLeft(tree.left);
						tree = RotateRight(tree);
					}
				}
			} else if (data > tree.data) {
				// Insert at right child
				tree.right = Insert(tree.right, data);
				if (Depth(tree.left) - Depth(tree.right) == -2) {
					if (data > tree.right.data) {
						// Insert at right child's right
						// Left-Rotate
						tree = RotateLeft(tree);
					} else if (data < tree.right.data) {
						// Insert at right child's left

						// First Right-rotate on tree's right child
						tree.right = RotateRight(tree.right);
						// Then Left-rotate tree
						tree = RotateLeft(tree);
					}
				}
			}
		}
		// Update depth
		tree.depth = Math.max(Depth(tree.left), Depth(tree.right)) + 1;
		return tree;
	}

	public void Insert(int data) {
		root = Insert(root, data);
	}

	private void Print(AVLNode tree) {
		if (tree != null) {
			Print(tree.left);
			System.out.println(tree.data);
			Print(tree.right);
		}
	}

	public void Print() {
		Print(root);
	}

	public boolean Find(int key) {
		AVLNode ptr = root;
		while (true) {
			if (ptr == null) {
				break;
			}
			if (key == ptr.data) {
				return true;
			} else if (key < ptr.data) {
				ptr = ptr.left;
			} else {
				ptr = ptr.right;
			}
		}
		return false;
	}

	private AVLNode root = null;

	public static void main(String[] args) {
		// AVLTree tree = new AVLTree();
		// for (int i = 0; i < 1000; i++) {
		// tree.Insert(i);
		// }
		// tree.Print();
		// int key = 1000;
		// System.out.println("Find: " + key + "? " + tree.Find(key));

		// AVLTree tree = new AVLTree();
		// int arr[] = { 13, 24, 37, 90, 53 };
		// for (int data : arr) {
		// tree.Insert(data);
		// }
		// tree.Print();

		AVLTree tree = new AVLTree();
		Random rand = new Random();
		for (int i = 0; i < 10000; i++) {
			tree.Insert(rand.nextInt(100000));
		}
		tree.Print();

	}
}

 

 

Leave a Reply

Your email address will not be published.