java实现平衡二叉树

java实现平衡二叉树(AVL树)

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在问题。

左边 BST存在的问题分析:

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

• 2)插入速度没有 影响

• 3)查询速度明显降低(因为需要依次比较),不能发挥BST树的优势，因为每次还需要比较左子树，其查询速度比单链表还慢

• 4)解决方案 - 平衡二 叉树(AVL)

基本介绍

平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树，可以保证查询效率较高。

具有以下特点: 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、 伸展树等。

举例说明, 看看下面哪些AVL树,为什么?

平衡二叉搜索树的左右子树，高度差不能大于1，所以前两个满足。

获取数的高度方法

//创建Node节点
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 == 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37