引言
二叉排序树存在的问题：
当遇到下面这种情况的时候，二叉排序树就会出现下面的一些问题：
- 形式类似与链表，与链表区别不大
- 插入数据的效率不会改变
- 但是查询的效率甚至还比不少链表，因为每一次都要比较左子树
为解决这个问题，引述平衡二叉树的概念
特殊情况的二叉排序树
平衡二叉树的定义：平衡二叉树也叫平衡 二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树， 可以保证查询效率较高。
特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且 左右两个子树都是一棵平衡二叉树。
平衡二叉树的常用实现方法：红黑树、AVL、替罪羊树、Treap、伸展树等。
举例：
平衡二叉树实列
构造：
测试类：测试二叉平衡树
二叉平衡树类：
- 属性：Node root——表示根节点，用一个根节点来表示一颗二叉树
- 方法:
节点类：
- 属性：int value表示节点的值 // 左子节点： left // 右子节点： right
- 方法：
实现细节：
传送门——数据结构——平衡二叉搜索树(AvlTree)的实现
代码实现：
package com.aiguigu.avl;
// 创建一个平衡二叉树的实列
public class AVLTreeDemo {
public static void main(String[] args) {
int[] arr = { 10, 11, 7, 6, 8, 9 };
AVLTree avlTree = new AVLTree();
//创建一个二叉平衡树
for(int i=0; i < arr.length; i++) {
avlTree.add(new Node(arr[i]));
}
//遍历测试一下
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在平衡处理~~");
System.out.println("树的高度=" + avlTree.getRoot().height()); //3
System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
System.out.println("根节点为：" + avlTree.getRoot());
}
}
//创建一个二叉平衡树的类
class AVLTree{
private Node root;
public Node getRoot() {
return root;
}
//查找要删除的节点
public Node search(int value){
if(root == null){
return null;
}else{
return root.search(value);
}
}
//查找要删除节点的父节点
public Node searchParent(int value){
if(root == null){
return null;
}else{
return root.searchParent(value);
}
}
//删除以当前节点为根节点的树中最小的节点，并且返回节点的值
public int delRightTreeMin(Node node){
Node target = node;
while(target != null){
target = target.left;
}
delNode(target.value);
return target.value;
}
//删除节点的方法
public void delNode(int value){
if(root == null){ //如果根节点为空，直接返回
return;
}else{
Node targetNode = search(value);
if(targetNode == null){ //如果没有找到要删除的节点
return;
}
//如果当前的树中只有一个根节点
if(root.left == null && root.right == null){
root = null;
return;
}
//找到targetNode的父节点
Node parent = searchParent(value);
if(targetNode.left == null && targetNode.right == null){
//如果当前查找的节点为叶子节点
if(parent.left != null && parent.left.value == value){
parent.left = null;
}else if(parent.right != null && parent.right.value == value){
parent.right = null;
}
}else if(targetNode.left != null && targetNode.right != null){
//如果当前的节点左右子节点都不为空
int minValue = delRightTreeMin(targetNode.right);
targetNode.value = minValue;
}else {
//如果当前节点只有一个子节点的情况下
if(targetNode.left != null){ //拥有左子节点的情况下
if(parent != null){
if(parent.left.value == value){
parent.left = targetNode.left;
}else{
parent.right = targetNode.left;
}
}else{ //parent为空，肯定为根节点
root = targetNode.left;
}
}else{ //拥有右子节点的情况下
if(parent != null){
if(parent.left.value == value){
parent.left = targetNode.right;
}else{
parent.right = targetNode.right;
}
}else{
root = targetNode.right;
}
}
}
}
}
//添加节点的方法
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("二叉排序树为空，不能遍历");
}
}
}
//创建节点类
class Node{
int value; //存放数值
Node left; //指向左子节点
Node right; //指向右子节点
//创建构造器
public Node(int value) {
this.value = value;
}
//重写toString()方法
@Override
public String toString() {
return "Node{" +
"value=" + value +
'}';
}
//返回以该节点为根节点的树的高度
public int height(){
return Math.max(left == null ? 0 : left.height(),right == null ? 0: right.height()) + 1;
//找一轮，就会在后面加上1，
}
//返回左子树的高度
public int leftHeight(){
if(left == null){
return 0;
}
return left.height();
}
//返回右子树的高度
public int rightHeight(){
if(right == null){
return 0;
}
return right.height();
}
//查找当前节点位置的方法
public Node search(int value){
if(this.value == value){
return this;
}else if(value < this.value){
if(this.left == null){
return null;
}
return this.left.search(value);
}else{
if(this.right == null){
return null;
}
return this.right.search(value);
}
}
//左旋转的方法(以当前节点为根节点的旋转方法)
private void leftRotate(){
Node newNode = new Node(value); //1.以根节点的值创建一个新的节点
newNode.left = left; //2.将新的左节点指向
newNode.right = right.left;
value = right.value;
right = right.right;
left = newNode;
}
//右旋转的方法（以当前节点为根节点的旋转方法）
private void rightRotate(){
Node newNode = new Node(value);
newNode.right = right;
newNode.left = left.right;
value = left.value;
left = left.left;
right = newNode;
}
//查找当前节点父节点的方法
public Node searchParent(int value){
if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)){
return this;
}else{
if(value < this.value && this.left != null){
return this.left.searchParent(value);
}else if(value >= this.value && this.right != null){
return this.right.searchParent(value);
}else{
return null; //没有找到父节点
}
}
}
//创建在此节点上添加节点的方法(节点对象自己的方法)
public void add(Node node){
if(node == null){
return; //如果要添加的节点为空，直接跳出
}
if(this.value < node.value){ //如果当前节点值小于添加的节点的node值
if(this.right == null){
this.right = node;
}else{
this.right.add(node);
}
}else{
if(this.left == null){
this.left = node;
}else{
this.left.add(node);
}
}
//添加结束之后，判断是不是平衡二叉树，如果不是则需要进行旋转（/左右旋转/）
if((leftHeight() - rightHeight())> 1){ //如果左子树比右子树高二级或以上，则应该右旋转
if(left != null && (left.rightHeight() > left.leftHeight())){
//在右旋转开始之前，先检测左子树的右子树高度是否比其左子树大，如果是，现队左子树进行左旋转
left.leftRotate();
rightRotate();
}else {
rightRotate();
}
}
//如果右子树比左子树高1层以上，左旋转
if((rightHeight() - leftHeight()) > 1){
if(right != null && right.leftHeight() > right.rightHeight()){
right.rightRotate();
leftRotate();
}else{
leftRotate();
}
}
}
//写一个中序遍历的方法
public void infixOrder(){
if(this.left != null){
this.left.infixOrder();
}
System.out.println(this);
if(this.right != null){
this.right.infixOrder();
}
}
}
网友评论