平衡二叉树
一，概述
平衡二叉树，也称为AVL树，是一种特殊的二叉排序树，它的每个节点的左子树和右子树的高度差不超过1。平衡二叉树的定义可以概括为以下两点：
- 左子树和右子树的高度差绝对值不超过1。
- 左子树和右子树都是平衡二叉树。
平衡因子是平衡二叉树中的一个重要概念，它表示一个节点的左子树高度减去右子树的高度。根据平衡二叉树的定义，每个节点的平衡因子只能是-1、0或1。
当在一个平衡二叉排序树上插入一个新节点时，有可能导致失衡，即出现平衡因子绝对值大于1的节点。为了恢复平衡，可能需要对树进行调整。常见的调整方法包括旋转和重新平衡。
旋转分为四种类型：左旋、右旋、左右旋和右左旋。旋转操作是平衡二叉树调整中常用的方法，它的目的是通过改变节点的位置来满足平衡二叉树的定义。
总体来说，平衡二叉树是一种重要的数据结构，具有很好的查找和插入性能。它通过保持树的平衡，提高了操作的效率。
简介：
- 平衡二叉树是一种自我平衡的二叉搜索树，它的左子树和右子树的高度差不超过1。
- 平衡二叉树的基本操作包括插入、删除和查找，这些操作的时间复杂度均为O(log n)，其中n为树中节点的数量。
- 平衡二叉树的主要应用场景包括计算机科学、数据结构和算法等领域。
图示：
以下是一个简单的平衡二叉树图示：
50
/ \
30 70
/ \ / \
10 40 60 80
在这个平衡二叉树中，每个节点的左子树和右子树的高度差都不超过1。
示例：
以下是一个在Java中实现平衡二叉树的简单示例：
public class AVLTree {
class Node {
int key;
Node left, right;
int height;
public Node(int item) {
key = item;
left = right = null;
height = 1;
}
}
Node root;
AVLTree(int key) {
root = new Node(key);
}
AVLTree() {
root = null;
}
int height(Node node) {
if (node == null) return 0;
return node.height;
}
Node insert(Node node, int key) {
if (node == null) return new Node(key);
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else { // Duplicate keys not allowed
return node;
}
node.height = 1 + Math.max(height(node.left), height(node.right));
return node;
}
}
在这个示例中，定义了一个内部类Node来表示平衡二叉树的节点。每个节点都有一个键key和两个子节点left和right，以及一个表示节点高度的属性height。还定义了两个方法height和insert。height方法用于计算节点的高度，而insert方法则用于向平衡二叉树中插入一个新的节点。
二，添加数据
在Java中，平衡二叉树是一种常见的数据结构，它可以有效地组织和搜索数据。平衡二叉树是一种自我平衡的二叉搜索树，它的任何一个节点的左子树和右子树的高度差的绝对值不超过1。AVL树和红黑树是平衡二叉树的两种常见类型。
下面是一个示例，展示如何在平衡二叉树中添加数据：
首先，需要创建一个表示平衡二叉树节点的类：
// 定义平衡二叉树的节点类
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
// 构造方法
public TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
然后，可以创建一个表示平衡二叉树的类，并添加一个方法来添加数据：
// 定义平衡二叉树类
public class AVLTree {
TreeNode root;
// 构造方法
public AVLTree() {
root = null;
}
// 添加数据的方法
public void add(int value) {
root = addRecursive(root, value);
}
// 递归添加数据的方法
private TreeNode addRecursive(TreeNode current, int value) {
if (current == null) {
// 如果当前节点为空，则创建一个新节点作为根节点
return new TreeNode(value);
}
// 根据值的大小决定添加到左子树还是右子树
if (value < current.value) {
current.left = addRecursive(current.left, value);
} else if (value > current.value) {
current.right = addRecursive(current.right, value);
} else {
// 如果值已经存在于树中，则不做任何操作
return current;
}
// 更新当前节点的高度为左子树和右子树的最大高度+1
current.height = 1 + Math.max(getHeight(current.left), getHeight(current.right));
// 获取当前节点的平衡因子，检查是否失衡
int balance = getBalance(current);
// 如果当前节点失衡，则根据情况进行旋转操作
if (balance > 1) {
// 如果左子树的平衡因子大于1，则进行右旋操作
return rightRotate(current);
} else if (balance < -1) {
// 如果右子树的平衡因子小于-1，则进行左旋操作
return leftRotate(current);
} else {
// 如果平衡因子为0，则不做任何操作，返回当前节点指针
return current;
}
}
// 计算节点的高度的方法
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
} else {
return node.height;
}
}
// 计算节点的平衡因子的方法（左子树高度-右子树高度）
private int getBalance(TreeNode node) {
if (node == null) {
return 0;
} else {
return getHeight(node.left) - getHeight(node.right);
}
}
}
三，删除数据
在Java中，平衡二叉树是一种常见的数据结构，它可以有效地组织和搜索数据。平衡二叉树是一种自我平衡的二叉搜索树，它的任何一个节点的左子树和右子树的高度差的绝对值不超过1。AVL树和红黑树是平衡二叉树的两种常见类型。
下面是一个示例，展示如何在平衡二叉树中删除数据：
首先，需要创建一个表示平衡二叉树节点的类：
// 定义平衡二叉树的节点类
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
// 构造方法
public TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
然后，可以创建一个表示平衡二叉树的类，并添加一个方法来删除数据：
// 定义平衡二叉树类
public class AVLTree {
TreeNode root;
// 构造方法
public AVLTree() {
root = null;
}
// 删除数据的方法
public void remove(int value) {
root = removeRecursive(root, value);
}
// 递归删除数据的方法
private TreeNode removeRecursive(TreeNode current, int value) {
if (current == null) {
// 如果当前节点为空，则不做任何操作，返回null
return null;
}
// 根据值的大小决定从左子树还是右子树中删除数据
if (value < current.value) {
current.left = removeRecursive(current.left, value);
} else if (value > current.value) {
current.right = removeRecursive(current.right, value);
} else {
// 如果值等于当前节点的值，则根据子节点的情况进行处理
if (current.left == null && current.right == null) {
// 如果当前节点没有子节点，则直接删除当前节点，返回null
return null;
} else if (current.left == null) {
// 如果当前节点只有右子节点，则直接删除当前节点，并返回右子节点作为新的节点
return current.right;
} else if (current.right == null) {
// 如果当前节点只有左子节点，则直接删除当前节点，并返回左子节点作为新的节点
return current.left;
} else {
// 如果当前节点有两个子节点，则找到右子树中的最小节点作为新的节点，并删除该最小节点
TreeNode minNode = findMinNode(current.right);
current.value = minNode.value;
current.right = removeRecursive(current.right, minNode.value);
}
}
// 更新当前节点的高度为左子树和右子树的最大高度+1
current.height = 1 + Math.max(getHeight(current.left), getHeight(current.right));
// 获取当前节点的平衡因子，检查是否失衡
int balance = getBalance(current);
// 如果当前节点失衡，则根据情况进行旋转操作
if (balance > 1) {
// 如果左子树的平衡因子大于1，则进行右旋操作
return rightRotate(current);
} else if (balance < -1) {
// 如果右子树的平衡因子小于-1，则进行左旋操作
return leftRotate(current);
} else {
// 如果平衡因子为0，则不做任何操作，返回当前节点指针
return current;
}
}
// 计算节点的高度的方法
private int getHeight(TreeNode node) {
if (node == null) {
return 0;
} else {
return node.height;
}
}
// 计算节点的平衡因子的方法（左子树高度-右子树高度）
private int getBalance(TreeNode node) {
if (node == null) {
return 0;
} else {
return getHeight(node.left) - getHeight(node.right);
}
}
// 找到右子树中的最小节点的方法（递归）
private TreeNode findMinNode(TreeNode node) {
if (node == null) {
return null;
} else if (node.left == null) {
return node;
} else {
return findMinNode(node.left);
}
}
}
