【数据结构与算法】十四二叉树 BST / 平衡二叉树AVL

╰半橙微兮° 2022-07-28 10:58 217阅读 0赞

# 【数据结构与算法】十四 二叉树 BST / 平衡二叉树AVL #

# **特点** #

每个节点有两个子节点,左小右大.

# 二叉树 BST #

package com.cn.mark.algorithm.binarytree;
    
    
    public class BST <T extends Comparable<? super T>>{
    
    
        private static class Node<T> {
    
            private T value ; 
            private Integer position ; 
            private Integer height ;
            private Node<T> left;
            private Node<T> right;
    
    
            public Node(T value , Integer position, Node<T> left, Node<T> right) {
                this.value =  value;
                this.position = position ; 
                this.height = 0;
                this.left = left;
                this.right = right;
            }
        }
    
        private int height(Node<T> t) {
            return t == null ? -1 : t.height;
        }
    
        private Node<T> root ; 
    
        public void add(T value , Integer position){
            root = add( value , position, root );
        }
    
        private Node<T> add(T value , Integer position, Node<T> node){
            if(node == null){
                return new Node<T>(value,position , null ,null);
            }
    
            int comparaResult = value.compareTo(node.value);
    
            if(comparaResult > 0)
                node.right = add(value , position , node.right);
            else if (comparaResult < 0)
                node.left = add(value , position , node.left);
            else 
                System.out.println("as same a value");
    
            node.height = Math.max(height(node.left), height(node.right)) + 1;
            return node;
    
        }
    
        public Integer search(Node<T> node , T value){
            if(node == null)
                return -1 ; 
            int comparaResult = value.compareTo(node.value);
            if(comparaResult == 0)
                return node.position;
            else if(comparaResult > 0)
                return search(node.right, value);
            else if(comparaResult < 0)
                return search(node.left, value);
            else
                return -1;
        }
    
        public static void main(String[] args){
            BST<Integer> bst = new BST<Integer>();
            //  int[] array = {0,1,2,3,4,5,6,7,8,9};
            for(int i=0;i<10;i++)
                bst.add(i,i);// 
            System.out.println(bst.height(bst.root));
            System.out.println(bst.search(bst.root, 8));
            System.out.println(bst.search(bst.root, 0));
            System.out.println(bst.search(bst.root, 22));
        }
    }

普通二叉树会纯在节点深度差距大的情况(具体请 baidu google ).  
接下接介绍平衡二叉树AVL

--------------------

# 平衡二叉树AVL #

最关键就是平衡,先看看四种不平衡类型.  
1、LL型（右旋操作）：插入一个新的结点到根结点的左子树的左子树，导致根结点的平衡.  
2、RR型（左旋操作）：插入一个新的结点到根结点的右子树的右子树，导致根结点的平衡  
3、LR型（左旋+右旋）：在根结点的左孩子的右子树上插入结点，插入情况笔者就  
4、RL型（右旋+左旋）在根结点的右子树的左子树上插入结点。同样以一个实例图  
![这里写图片描述][20160501130855806]

通过旋转节点关系.

package com.cn.mark.algorithm.binarytree;
    
    
    public class AVLBST<T extends Comparable<? super T>> {
    
        private static class Node<T> {
    
            private T value;
            private Integer position;
            private Integer height ;
            private Node<T> left;
            private Node<T> right;
    
            public Node(T value, Integer position, Node<T> left, Node<T> right) {
                this.value = value;
                this.position = position;
                this.height = 0;
                this.left = left;
                this.right = right;
            }
        }
    
    
        private int height(Node<T> t) {
            return t == null ? -1 : t.height;
        }
    
        private Node<T> root;
    
        public void add(T value, Integer position) {
            root = add(value, position, root);
        }
    
        private Node<T> add(T value, Integer position, Node<T> node) {
            if (node == null) {
                return new Node<T>(value, position, null, null);
            }
    
            int comparaResult = value.compareTo(node.value);
    
            if (comparaResult < 0) {
                node.left = add(value, position , node.left);// 将x插入左子树中
                if (height(node.left) - height(node.right) == 2)// 打破平衡
                    if (value.compareTo(node.left.value) < 0)// LL型（左左型）
                        node = rotateWithLeftChild(node);
                    else // LR型（左右型）
                        node = doubleWithLeftChild(node);
            } else if (comparaResult > 0) {
                node.right = add(value,  position , node.right);// 将x插入右子树中
                if (height(node.right) - height(node.left) == 2)// 打破平衡
                    if (value.compareTo(node.right.value) > 0)// RR型（右右型）
                        node = rotateWithRightChild(node);
                    else // RL型
                        node = doubleWithRightChild(node);
            } else
                System.out.println("as same a value");
    
    
            node.height = Math.max(height(node.left), height(node.right)) + 1;
    
            return node;
    
        }
    
    
        // 带左子树旋转,适用于LL型
        private Node<T> rotateWithLeftChild(Node<T> k2) {
            Node<T> k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
            k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
            k1.height = Math.max(height(k1.left), k2.height) + 1;
            return k1;
        }
    
        // 带右子树旋转，适用于RR型
        private Node<T> rotateWithRightChild(Node<T> k1) {
            Node<T> k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
            k2.height = Math.max(height(k2.right), k1.height) + 1;
            return k2;
        }
    
        // 双旋转，适用于LR型
        private Node<T> doubleWithLeftChild(Node<T> k3) {
            k3.left = rotateWithRightChild(k3.left);
            return rotateWithLeftChild(k3);
        }
    
        // 双旋转,适用于RL型
        private Node<T> doubleWithRightChild(Node<T> k1) {
            k1.right = rotateWithLeftChild(k1.right);
            return rotateWithRightChild(k1);
        }
    
    
    
        public Integer search(Node<T> node, T value) {
            if (node == null)
                return -1;
            int comparaResult = value.compareTo(node.value);
            if (comparaResult == 0)
                return node.position;
            else if (comparaResult > 0)
                return search(node.right, value);
            else if (comparaResult < 0)
                return search(node.left, value);
            else
                return -1;
        }
    
        public static void main(String[] args) {
            AVLBST<Integer> avlbst = new AVLBST<Integer>();
            // int[] array = {0,1,2,3,4,5,6,7,8,9};
            for (int i = 0; i < 10; i++)
                avlbst.add(i, i);//
            System.out.println(avlbst.height(avlbst.root));
            System.out.println(avlbst.search(avlbst.root, 8));
            System.out.println(avlbst.search(avlbst.root, 0));
            System.out.println(avlbst.search(avlbst.root, 22));
        }
    }

[20160501130855806]: /images/20220724/fd005ee8347f440e8029ebd5a1be184d.png