数据结构与算法(十一)

树的应用

二叉排序树

给你一个数列 7, 3, 10, 12, 5, 1, 9，要求能够高效的完成对数据的查询和添加。

在 为什么需要该数据结构 中讲解了数组、链表数据结构的优缺点，简单说：

• 数组访问快，增删慢

  新增或移除时，需要整体移动数据

• 链表增删快，访问慢

  只能从头开始遍历查找

那么利用 二叉排序树（Binary Sort/Search Tree），既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改 的速度

二叉排序树介绍

二叉排序树（Binary Sort/Search Tree），简称 BST。

对于二叉排序树的任何一个 非叶子节点，要求如下：

• 左节点，比父节点小
• 右节点，比父节点大

特殊说明：如果有有相同的值，可以将该节点放在左节点或右节点。当然，最理想的是没有重复的值，比如 Mysql 中的 B 树索引，就是以主键 ID 来排序的。

比如对下面这个二叉树增加一个节点：

1. 从根节点开始，发现比 7 小，直接往左子树查找，相当于直接折半了
2. 比 3 小，再次折半
3. 比 1 大：直接挂在 1 的右节点

创建、遍历、删除、查找

复制代码

	//定义节点
	class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
	this.value = value;
	}
	//添加节点
	public void add(Node node){
	if(node == null){
	return;
	}
	if(node.value < this.value){
	if(this.left == null){
	this.left = node;
	}else{
	this.left.add(node);//递归查找添加
	}
	}else{
	if(this.right == null){
	this.right = node;
	}else{
	this.right.add(node);
	}
	}
	}
	//查找要删除的父节点
	public Node searchParent(int value){
	if(this.left != null && this.left.value == value || this.right != null && this.right.value == value){
	return this;
	}else if(this.left != null && this.value > value){//左递归查找
	return this.left.searchParent(value);
	}else if(this.right != null && this.value < value){//右递归查找
	return this.right.searchParent(value);
	}else{
	return null;
	}
	}
	//查找要删除的节点
	public Node search(int value){
	if(this.value == value){
	return this;
	}else if(value < this.value){
	if(this.left != null){
	return this.left.search(value);//向左递归查找
	}else{
	return null;
	}
	}else {
	if(this.right != null){
	return this.right.search(value);
	}else{
	return null;
	}
	}
	}
	//中序遍历
	public void infixOrder(){
	if(this.left != null){
	this.left.infixOrder();
	}
	System.out.println(this);
	if(this.right != null){
	this.right.infixOrder();
	}
	}
	@Override
	public String toString() {
	return "Node{" +
	"value=" + value +
	'}';
	}
	}
	class BinarySortTree{
	private Node root;
	public Node getRoot() {
	return root;
	}
	public void add(Node node){
	if(root == null){
	root = node;
	}else{
	root.add(node);
	}
	}
	public void infixOrder(){
	if(root != null){
	root.infixOrder();
	}else{
	System.out.println("二叉排序树为空");
	}
	}
	//查找要删除的节点
	public Node search(int value){
	if(root != null){
	return root.search(value);
	}else{
	return null;
	}
	}
	//查找要删除的父节点
	public Node searchParent(int value){
	if(root != null){
	return root.searchParent(value);
	}{
	return null;
	}
	}
	//找到目标节点为根节点最小的那个节点，并删除其节点，然后返回其值
	public int delRightMin(Node root){
	Node target = root;
	while(target.left != null){
	target = target.left;
	}
	delNode(target.value);
	return target.value;
	}
	//删除节点
	public void delNode(int value){
	Node targetNode = search(value);
	//要删除的节点是根节点
	if(targetNode == root){
	root = null;
	return;
	}
	Node parentNode = searchParent(value);
	if(targetNode.left == null && targetNode.right == null){//删除的叶子节点
	if(parentNode.left == targetNode){//当目标节点为父节点的左子节点
	parentNode.left = null;
	}else{
	parentNode.right = null;
	}
	}else if(targetNode.left != null && targetNode.right != null){//删除的节点为有两个子节点的非叶子节点
	targetNode.value = delRightMin(targetNode.right);
	}else{//删除的节点为只有一个节点的非叶子节点
	if(targetNode.left != null){
	if(parentNode != null){
	if(parentNode.left == targetNode){
	parentNode.left = targetNode.left;
	}else{
	parentNode.right = targetNode.left;
	}
	}else{
	root = targetNode.left;
	}
	}else {
	if(parentNode != null){
	if(parentNode.left == targetNode){
	parentNode.left = targetNode.right;
	}else{
	parentNode.right = targetNode.right;
	}
	}else{
	root = targetNode.right;
	}
	}
	}
	}
	}

完整平衡二叉树（AVL树）

二叉排序树可能的问题

一个数列 {1,2,3,4,5,6}，创建一颗二叉排序树（BST）

创建完成的树如上图所示，那么它存在的问题有以下几点：

1. 左子树全部为空，从形式上看，更像一个单链表

2. 插入速度没有影响

3. 查询速度明显降低

   因为需要依次比较，不能利用二叉排序树的折半优势。而且每次都还要比较左子树，可能比单链表查询速度还慢。

那么解决这个劣势的方案就是：平衡二叉树（AVL）。

基本介绍

平衡二叉树也叫 平衡二叉搜索树（Self-balancing binary search tree），又被称为 AVL 树，可以保证 查询效率较高。它是解决 二叉排序 可能出现的查询问题。

它的特点：是一颗空树或它的 左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一颗平衡二叉树。

平衡二叉树的常用实现方法有：

• 红黑树
• AVL（算法）
• 替罪羊树
• Treap
• 伸展树

如下所述，哪些是平衡二叉树？

1. 是平衡二叉树：

   • 左子树高度为 2
   • 右子树高度为 1

   他们差值为 1

2. 也是平衡二叉树

3. 不是平衡二叉树

   1. 左子树高度为 3
   2. 右子树高度为 1

   他们差值为 2，所以不是

单旋转（左旋转）

一个数列 4,3,6,5,7,8 ，创建出它对应的平衡二叉树。

思路分析：下图红线部分是调整流程。

按照规则调整完成之后，形成了下面这样一棵树

完整流程如下图所示：

插入 8 时，发现左右子树高度相差大于 1，则进行左旋转：

1. 创建一个新的节点 newNode，值等于当前 根节点 的值（以 4 创建）
2. 把新节点的 左子树 设置为当前节点的 左子树
3. 把新节点的 右子树 设置为当前节点的 右子树的左子树
4. 把 当前节点 的值换为 右子节点 的值
5. 把 当前节点 的右子树设置为 右子树的右子树
6. 把 当前节点 的左子树设置为新节点

注：左图是调整期，右图是调整后。注意调整期的 6 那个节点，调整之后，没有节点指向他了。也就是说，遍历的时候它是不可达的。那么将会自动的被垃圾回收掉。

树高度计算

前面说过，平衡二叉树是为了解决二叉排序树中可能出现的查找效率问题，那么基本上的代码都可以在之前的二叉排序树上进行优化。那么下面只给出与当前主题相关的代码，最后放出一份完整的代码。

树的高度计算，我们需要得到 3 个高度：

1. 这颗树的整体高度
2. 左子树的高度
3. 右子树的高度

复制代码

	//Node
	//获得左子树的高度
	public int leftHeight(){
	if(left == null){
	return 0;
	}
	return left.height();
	}
	//获得右子树的高度
	public int rightHeight(){
	if(right == null){
	return 0;
	}
	return right.height();
	}
	//获得当前节点高度
	public int height(){
	return Math.max(left == null ? 0 : left.height(),right == null ? 0 : right.height())+1;
	}

旋转

说下旋转的时机：也就是什么时机采取做旋转的操作？

当然是：当 右子树高度 - 左子树高度 > 1 时，才执行左旋转。

这里就得到一些信息:

1. 每次添加完一个节点后，就需要检查树的高度

2. 满足 右子树高度 - 左子树高度 > 1，那么一定满足下面的条件：

   1. 左子树高度为 1
   2. 右子树高度为 3

   也就是符合这张图

复制代码

	//左旋转
	public void leftRotate(){
	//使用当前跟节点创建一个新节点
	Node newNode = new Node(value);
	//当前根节点的左子树设置为新节点的左子树
	newNode.left = left;
	//当前根节点的右子树的左子树设置为当前新节点的右子树
	newNode.right = right.left;
	//将右子树的值拷贝到当前根节点
	value = right.value;
	//将跟节点的右子树设置为右子树的右子树
	right = right.right;
	//将根节点左子树设置为新节点
	left = newNode;
	}

右旋转

其实这个就很好理解了：

• 左旋转：右 - 左 > 1，把右边的往左边旋转一层
• 右旋转：左 - 右 > 1，把左边的往右边旋转一层

他们其实是反着来的，那么右旋转的思路如下：

1. 创建一个新的节点 newNode，值等于当前 根节点 的值（以 4 创建）
2. 把新节点的 右子树 设置为当前节点的 右子树
3. 把新节点的 左子树 设置为当前节点的 左子树的右子树
4. 把 当前节点 的值换为 左子节点 的值
5. 把 当前节点 的左子树设置为 左子树的左子树
6. 把 当前节点 的右子树设置为新节点

复制代码

	//右旋转
	public void rightRotate(){
	Node newNode = new Node(value);
	newNode.right = right;
	newNode.left = left.right;
	value = left.value;
	left = left.left;
	right = newNode;
	}

双旋转

在前面的例子中，使用单旋转（即一次旋转）就可以将非平衡二叉树转换为平衡二叉树。

但是在某些情况下，就无法做到。比如下面这两组数列

左侧这个树满足 leftHeight - rightHeight > 1 ，也就是满足右旋转，旋转之后，树结构变化了。但是还是一个非平衡二叉树。

它的主要原因是：root 左子树的 左子树高度 小于 右子树的高度。即：节点 7 的左子树高度小于右子树的高度。

解决办法：

1. 先将 7 这个节点为 root 节点，进行左旋转
2. 再将原始的 root 节点进行右旋转

过程示意图如下：

其实可以参考下前面两个单旋转的图例，它有这样一个特点：

1. 右旋转：
   • root 的 left 左子树高度 大于 右子树高度
   • 右旋转的时候，会将 left.right 旋转到 right.left 节点上
2. 左旋转：
   • root 的 right 右子树高度 大于 左子树高度
   • 左旋转的时候，会将 right.left 旋转到 left.right 上。

如果不满足这个要求，在第二个操作的时候，就会导致 2 层的高度被旋转到 1 层的节点下面，导致不平衡了。

复制代码

	//左旋转
	if(rightHeight() - leftHeight() > 1){
	//如果右子树的左子树高度大于右子树的右子树，先进行右旋转，再进行左旋转
	if(right != null && right.leftHeight() > right.rightHeight()){
	right.rightRotate();
	leftRotate();//左旋转
	}else{
	leftRotate();
	}
	return;//进行了旋转之后就不用进行下面的再次旋转
	}
	//右旋转
	if(leftHeight() - rightHeight() > 1){
	//如果左子树的右子树高度，大于左子树的左子树先进行左旋转，再进行右旋转
	if(left != null && left.rightHeight() > left.leftHeight()){
	left.leftRotate();//左子树左旋转
	rightRotate();//右旋转
	}else{
	rightRotate();
	}
	}

完整代码

复制代码

	//AVL树
	class AVLTree{
	private Node root;
	public Node getRoot() {
	return root;
	}
	public void add(Node node){
	if(root == null){
	root = node;
	}else{
	root.add(node);
	}
	}
	public void infixOrder(){
	if(root != null){
	root.infixOrder();
	}else{
	System.out.println("二叉排序树为空");
	}
	}
	//查找要删除的节点
	public Node search(int value){
	if(root != null){
	return root.search(value);
	}else{
	return null;
	}
	}
	//查找要删除的父节点
	public Node searchParent(int value){
	if(root != null){
	return root.searchParent(value);
	}{
	return null;
	}
	}
	//找到目标节点为根节点最小的那个节点，并删除其节点，然后返回其值
	public int delRightMin(Node root){
	Node target = root;
	while(target.left != null){
	target = target.left;
	}
	delNode(target.value);
	return target.value;
	}
	//删除节点
	public void delNode(int value){
	Node targetNode = search(value);
	//要删除的节点是根节点
	if(targetNode == root){
	root = null;
	return;
	}
	Node parentNode = searchParent(value);
	if(targetNode.left == null && targetNode.right == null){//删除的叶子节点
	if(parentNode.left == targetNode){//当目标节点为父节点的左子节点
	parentNode.left = null;
	}else{
	parentNode.right = null;
	}
	}else if(targetNode.left != null && targetNode.right != null){//删除的节点为有两个子节点的非叶子节点
	targetNode.value = delRightMin(targetNode.right);
	}else{//删除的节点为只有一个节点的非叶子节点
	if(targetNode.left != null){
	if(parentNode != null){
	if(parentNode.left == targetNode){
	parentNode.left = targetNode.left;
	}else{
	parentNode.right = targetNode.left;
	}
	}else{
	root = targetNode.left;
	}
	}else {
	if(parentNode != null){
	if(parentNode.left == targetNode){
	parentNode.left = targetNode.right;
	}else{
	parentNode.right = targetNode.right;
	}
	}else{
	root = targetNode.right;
	}
	}
	}
	}
	}
	//节点
	class Node{
	int value;
	Node left;
	Node right;
	public Node(int value) {
	this.value = value;
	}
	//获得左子树的高度
	public int leftHeight(){
	if(left == null){
	return 0;
	}
	return left.height();
	}
	//获得右子树的高度
	public int rightHeight(){
	if(right == null){
	return 0;
	}
	return right.height();
	}
	//获得当前节点高度
	public int height(){
	return Math.max(left == null ? 0 : left.height(),right == null ? 0 : right.height())+1;
	}
	//左旋转
	public void leftRotate(){
	//使用当前跟节点创建一个新节点
	Node newNode = new Node(value);
	//当前根节点的左子树设置为新节点的左子树
	newNode.left = left;
	//当前根节点的右子树的左子树设置为当前新节点的右子树
	newNode.right = right.left;
	//将右子树的值拷贝到当前根节点
	value = right.value;
	//将跟节点的右子树设置为右子树的右子树
	right = right.right;
	//将根节点左子树设置为新节点
	left = newNode;
	}
	//右旋转
	public void rightRotate(){
	Node newNode = new Node(value);
	newNode.right = right;
	newNode.left = left.right;
	value = left.value;
	left = left.left;
	right = newNode;
	}
	public void add(Node node){
	if(node == null){
	return;
	}
	if(node.value < this.value){
	if(this.left == null){
	this.left = node;
	}else{
	this.left.add(node);//递归查找添加
	}
	}else{
	if(this.right == null){
	this.right = node;
	}else{
	this.right.add(node);
	}
	}
	//左旋转
	if(rightHeight() - leftHeight() > 1){
	//如果右子树的左子树高度大于右子树的右子树，先进行右旋转，再进行左旋转
	if(right != null && right.leftHeight() > right.rightHeight()){
	right.rightRotate();
	leftRotate();//左旋转
	}else{
	leftRotate();
	}
	return;//进行了旋转之后就不用进行下面的再次旋转
	}
	//右旋转
	if(leftHeight() - rightHeight() > 1){
	//如果左子树的右子树高度，大于左子树的左子树先进行左旋转，再进行右旋转
	if(left != null && left.rightHeight() > left.leftHeight()){
	left.leftRotate();//左子树左旋转
	rightRotate();//右旋转
	}else{
	rightRotate();
	}
	}
	}
	}