二叉排序树 左旋转 右旋转
单旋转：1左旋转2右旋转 双向旋转： 调整排序树，使其最优。（左子树和右子树的高度差的绝对值不大于1）
平衡二叉树
Node类
package com.bjsxt.BinarySortTree;
//二叉排序树
public class Node {
int value;
Node left;
Node right;
public Node(int value){
this.value=value;
}
/**
* 获取左子树的高度
* @return
*/
public int leftHeight(){
if(left==null){
return 0;
}
return left.height();
}
/**
* 获取右子树的高度
* @return
*/
public int rightHeight(){
if(right==null){
return 0;
}
return right.height();
}
/**
* 返回当前节点的高度
* @return
*/
public int height(){
return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;
}
/**
* 向子树中添加节点
* @param node
*/
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(leftHeight()-rightHeight()>=2){
//双旋转
if(left!=null&&left.leftHeight()<left.rightHeight()){
//先左旋转
left.leftRotate();
//再右旋转
rightRotatr();
//单旋转
}else{
rightRotatr();
}
//左旋转
if(leftHeight()-rightHeight()<=-2){
//双旋转
if(right!=null&&right.rightHeight()<right.leftHeight()){
right.rightRotatr();
leftRotate();
//单旋转
}else{
leftRotate();
}
}
}
}
/**
* 左旋转
*/
private void leftRotate() {
Node newLeft = new Node(value);
newLeft.left=left;
newLeft.right=right.left;
value=right.value;
right=right.right;
left=newLeft;
}
/**
* 右旋转
*/
private void rightRotatr(){
//创建一个新的节点，值等于当前节点的值
Node newRight = new Node(value);
//把新节点的右子树设置为当前节点的右子树
newRight.right=right;
//把新节点的左子树设置为当前节点左子树的右子树
newRight.left=left.right;
//把当前节点的值换为左子节点的值
value=left.value;
//把当前节点的左子树设置为左子树的左子树
left=left.left;
//把当前节点的右子树设置为新节点
right=newRight;
}
/**
*中序遍历二叉排序树，从小到大排序
* @param node
*/
public void midShow(Node node) {
if (node==null){
return;
}
midShow(node.left);
System.out.println(node.value);
midShow(node.right);
}
/**
* 查找节点
* @param value
*/
public Node search(int value) {
if(this.value==value){
return this;
}else if(value<this.value){
if(left==null){
return null;
}
return left.search(value);
}else {
if(right==null){
return null;
}
return right.search(value);
}
}
/**
* 搜索父节点
* @param value
* @return
*/
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.value>value&&this.left!=null){
return this.left.searchParent(value);
}else if(this.value<value&&this.right!=null){
return this.right.searchParent(value);
}
return null;
}
}
}
创建一颗二叉排序树
package com.bjsxt.BinarySortTree;
public class BinarySortTree {
Node root;
public void add(Node node){
//如果是一颗空树
if(root==null){
root=node;
}else{
root.add(node);
}
}
/**
* 中序遍历二叉排序树，从小到大排序
*/
public void midShow(){
if(root!=null){
root.midShow(root);
}
}
/**
* 节点的查找
* @param value
* @return
*/
public Node search(int value){
if(root==null){
return null;
}else{
return root.search(value);
}
}
/**
* 删除节点
* @param value
*/
public void delete(int value){
if(root==null){
return;
}else {
//找到这个节点
Node target = search(value);
if(target==null){
return;
}
//找到他的父节点
Node parent = seaechParent(value);
//要删除的节点是叶子节点
if(target.left==null&&target.right==null){
//要删除的节点是父节点的左子节点
if(parent.left.value==value){
parent.left=null;
//要删除的节点是父节点的右子节点
}else {
parent.right=null;
}
//要删除的节点有两个子节点的情况
}else if(target.left!=null&&target.right!=null){
//删除右子树中最小的节点，并获取到该节点的值
int min = deleteMin(target.right);
//替换目标节点中的值
target.value=min;
//要删除的节点有一个左子节点或右子节点
}else {
//有左子节点
if(target.left!=null){
//要删除的节点是父节点的左子节点
if(parent.left.value==value){
parent.left=target.left;
//要删除的节点是父节点的右子节点
}else {
parent.right=target.left;
}
//有右子节点
}else {
//要删除的节点是父节点的左子节点
if(parent.left.value==value){
parent.left=null;
//要删除的节点是父节点的右子节点
}else {
parent.right=null;
}
}
}
}
}
/**
* 删除一棵树中最小的节点
* @param node
* @return
*/
private int deleteMin(Node node) {
Node target = node;
//递归向左找
while(target.left!=null){
target=target.left;
}
//删除最小的这个节点
delete(target.value);
return target.value;
}
/**
* 搜索父节点
* @param value
* @return
*/
public Node seaechParent(int value){
if(root==null){
return null;
}else {
return root.searchParent(value);
}
}
}
测试类（单旋转，双旋转）
package com.bjsxt.BinarySortTree;
public class TestBibarySortTree {
public static void main(String[] args){
// int[] arr=new int[]{8,9,6,7,5,4};
// int[] arr=new int[]{2,1,4,3,5,6};
int[] arr=new int[]{8,9,5,4,6,7};
//创建一颗二叉排序树
BinarySortTree bst = new BinarySortTree();
//循环结构
for(int i:arr){
bst.add(new Node(i));
}
//查看高度
System.out.println(bst.root.height());
System.out.println(bst.root.value);
// System.out.println(bst.root.leftHeight());
// System.out.println(bst.root.rightHeight());
}
}
该代码测试结果
3
6
