二叉平衡树
定义
- 是一个特殊的 二叉查找树
- 任何结点的两个子树的高度差小于等于1
- 前5个函数为后面的功能做铺垫，一般的树都有这些函数
1. 结点
public class Node{
int height; //树高
int value; //存值
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
this.height = 0; //默认树高为0
}
}2. 树高
//树高
public int height(){
return height(root);
}
private int height(Node node){
if(node != null){
return node.height;
}
return 0; //默认为0
}3. 比大小
//比大小
private int max(int a,int b){
return a>b ? a : b;
}4. 找最值及其结点
//最值
public int min(){
Node node = minTree(root);
if(node != null){
return node.value;
}
return 0;
}
//最值的结点
private Node minTree(Node node){
if(node == null) return null;
while(node.left != null){
node = node.left;
}
return node;
}
public int max(){
Node node = maxTree(root);
if(node != null){
return node.value;
}
return 0;
}
private Node maxTree(Node node){
if(node == null) return null;
while(node.right != null){
node = node.right;
}
return node;
}5. 查找
public Node search(int value){
return search(root,value);
}
private Node search(Node node,int value){
if(node == null){
return node;
}
if(value < node.value){
return search(node.left,value);
}else if(value > node.value){
return search(node.right,value);
}else{
return node;
}
}6. 旋转
为了实现任何结点的左右子树高度差小于等于1，就要用旋转使树达到平衡，而旋转分为，左左旋转，右右旋转，左右旋转和右左旋转
- 左左旋转
private Node leftLeftRotation(Node node){
Node temp;
temp = node.left;
node.left = temp.right;
temp.right = node;
node.height = max( height(node.left), height(node.right)) + 1;
temp.height = max( height(temp.right), node.height) + 1;
return temp;
}- 右右旋转
public Node rightRightRotation(Node node){
Node temp;
temp = node.right;
node.right = temp.left;
temp.left = node;
node.height = max( height(node.left), height(node.right)) + 1;
temp.height = max( height(temp.left), node.height) + 1;
return temp;
}- 左右旋转
//左右旋转
private Node leftRightRotation(Node node){
node.left = rightRightRotation(node.left);
return leftLeftRotation(node);
}- 右左旋转
//右左旋转
private Node rightLeftRotation(Node node){
node.right = leftLeftRotation(node.right);
return rightRightRotation(node);
}7. 插入
//插入
public void add(int value){
root = add(root,value);
}
private Node add(Node node,int value){
if(node == null){
node = new Node(value,null,null);
}else{
//左移
if(value < node.value){
node.left = add(node.left,value);
//插入平衡调整
if((height(node.left) - height(node.right)) == 2){
if (value < node.left.value){
node = leftLeftRotation(node);
}else{
node = leftRightRotation(node);
}
}
//右移
}else if(value > node.value){
node.right = add(node.right,value);
if ((height(node.right) - height(node.left)) == 2){
if(value > node.right.value){
node = rightRightRotation(node);
}else{
node = rightLeftRotation(node);
}
}
//相等
}else{
System.out.println("不能插入相同的值");
}
}
node.height = max(height(node.left),height(node.right)) + 1;
return node;
}8. 删除
public void remove(int value){
Node node;
Node tree = root;
if( (node = search(root,value)) != null ){
root = remove(tree,node);
}
}
private Node remove(Node tree, Node node){
if( tree == null || node == null){
return null;
}
//在左树
if(node.value < tree.value){
tree.left = remove(tree.left,node);
//删除后不平衡
if(height(tree.right ) - height(tree.left) == 2){
Node temp = tree.right;
if(height(temp.left) > height(temp.right)){
tree = rightLeftRotation(tree);
}else{
tree = rightRightRotation(tree);
}
}
}else if(node.value > tree.value){
tree.right = remove(tree, node);
if(height(tree.left) - height(tree.right) == 2){
Node temp = tree.left;
if(height(temp.right) > height(temp.left)){
tree = leftRightRotation(tree);
}else{
tree = leftLeftRotation(tree);
}
}
//是该结点了
}else{
if(tree.left != null && tree.right != null){
if(height(tree.left) > height(tree.right)){
Node max = maxTree(tree.left);
tree.value = max.value;
tree.left = remove(tree.left, max);
}else{
Node min = minTree(tree.right);
tree.value = min.value;
tree.right = remove(tree.right, min);
}
}else{
Node temp = tree;
tree = (tree.left != null) ? tree.left : tree.right;
temp = null;
}
}
return tree;
}9. 测试
public static void main(String[] args) {
AVLTree tree = new AVLTree();
int[] arrs = {10,20,5,30,1,100,50};
for (int arr : arrs){
tree.add(arr);
}
tree.preOrder();
tree.add(1000);
tree.remove(1);
tree.preOrder();
}20
10
30
分开上下输出-----------------
30
20
4010. 整体代码
public class AVLTree {
private Node root;
public class Node{
int height;
int value;
Node left;
Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
this.height = 0;
}
}
//树高
public int height(){
return height(root);
}
private int height(Node node){
if(node != null){
return node.height;
}
return 0;
}
//比大小
private int max(int a,int b){
return a>b ? a : b;
}
//左左旋转
private Node leftLeftRotation(Node node){
Node temp;
temp = node.left;
node.left = temp.right;
temp.right = node;
node.height = max( height(node.left), height(node.right)) + 1;
temp.height = max( height(temp.right), node.height) + 1;
return temp;
}
//右右旋转
public Node rightRightRotation(Node node){
Node temp;
temp = node.right;
node.right = temp.left;
temp.left = node;
node.height = max( height(node.left), height(node.right)) + 1;
temp.height = max( height(temp.left), node.height) + 1;
return temp;
}
//左右旋转
private Node leftRightRotation(Node node){
node.left = rightRightRotation(node.left);
return leftLeftRotation(node);
}
//右左旋转
private Node rightLeftRotation(Node node){
node.right = leftLeftRotation(node.right);
return rightRightRotation(node);
}
//插入
public void add(int value){
root = add(root,value);
}
private Node add(Node node,int value){
if(node == null){
node = new Node(value,null,null);
}else{
//左移
if(value < node.value){
node.left = add(node.left,value);
//插入平衡调整
if((height(node.left) - height(node.right)) == 2){
if (value < node.left.value){
node = leftLeftRotation(node);
}else{
node = leftRightRotation(node);
}
}
//右移
}else if(value > node.value){
node.right = add(node.right,value);
if ((height(node.right) - height(node.left)) == 2){
if(value > node.right.value){
node = rightRightRotation(node);
}else{
node = rightLeftRotation(node);
}
}
//相等
}else{
System.out.println("不能插入相同的值");
}
}
node.height = max(height(node.left),height(node.right)) + 1;
return node;
}
public void preOrder(){
preOrder(root);
}
public void preOrder(Node node){
if(node != null){
System.out.println(node.value);
preOrder(node.left);
preOrder(node.right);
}
}
public Node search(int value){
return search(root,value);
}
private Node search(Node node,int value){
if(node == null){
return node;
}
if(value < node.value){
return search(node.left,value);
}else if(value > node.value){
return search(node.right,value);
}else{
return node;
}
}
public void remove(int value){
Node node;
Node tree = root;
if( (node = search(root,value)) != null ){
root = remove(tree,node);
}
}
private Node remove(Node tree, Node node){
if( tree == null || node == null){
return null;
}
//在左树
if(node.value < tree.value){
tree.left = remove(tree.left,node);
//删除后不平衡
if(height(tree.right ) - height(tree.left) == 2){
Node temp = tree.right;
if(height(temp.left) > height(temp.right)){
tree = rightLeftRotation(tree);
}else{
tree = rightRightRotation(tree);
}
}
}else if(node.value > tree.value){
tree.right = remove(tree, node);
if(height(tree.left) - height(tree.right) == 2){
Node temp = tree.left;
if(height(temp.right) > height(temp.left)){
tree = leftRightRotation(tree);
}else{
tree = leftLeftRotation(tree);
}
}
//是该结点了
}else{
if(tree.left != null && tree.right != null){
if(height(tree.left) > height(tree.right)){
Node max = maxTree(tree.left);
tree.value = max.value;
tree.left = remove(tree.left, max);
}else{
Node min = minTree(tree.right);
tree.value = min.value;
tree.right = remove(tree.right, min);
}
}else{
Node temp = tree;
tree = (tree.left != null) ? tree.left : tree.right;
temp = null;
}
}
return tree;
}
//最值
public int min(){
Node node = minTree(root);
if(node != null){
return node.value;
}
return 0;
}
private Node minTree(Node node){
if(node == null) return null;
while(node.left != null){
node = node.left;
}
return node;
}
public int max(){
Node node = maxTree(root);
if(node != null){
return node.value;
}
return 0;
}
private Node maxTree(Node node){
if(node == null) return null;
while(node.right != null){
node = node.right;
}
return node;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录