美文网首页
平衡二叉树AVLTree手写实现(Java)

平衡二叉树AVLTree手写实现(Java)

作者: aruba | 来源:发表于2021-07-31 19:42 被阅读0次

    定义节点:

            //平衡因子 左树深度多
            public static final int LH = 1;
            //平衡因子 右数深度多
            public static final int RH = -1;
            //平衡因子 左右树深度相同
            public static final int EH = 0;
    
            class AVLNode<T> {
                T value;
                AVLNode<T> leftChild;
                AVLNode<T> rightChild;
                AVLNode<T> parent;
                int balance = EH;
            }
    

    实现左旋方法:


    左旋.jpg
            /**
             * 节点左旋
             * //            转换前:
             * //                |
             * //                a   <-
             * //               / \
             * //              b   c
             * //                  / \
             * //                 z  h
             * //
             * //            转换后:
             * //
             * //                |
             * //                c
             * //               / \
             * //         ->   a   h
             * //             / \
             * //            b  z
             */
            private void leftRotate(AVLNode<T> a) {
                AVLNode<T> c = a.rightChild;
    
                //1.a的父节点的孩子指向c,c的父节点变为a的父节点
                if (a.parent == null) {//根节点,即a没有父节点
                    root = c;
                } else if (a.parent.leftChild == a) {//a是左孩子
                    a.parent.leftChild = c;
                } else {//a是右孩子
                    a.parent.rightChild = c;
                }
                //c的父节点变为a的父节点
                c.parent = a.parent;
    
                //2.a的右孩子变为z
                AVLNode<T> z = c.leftChild;
                a.rightChild = z;
                //z父节点指向a
                if (z != null)
                    z.parent = a;
    
                //3.c的左孩子变为a,a的父节点指向c
                c.leftChild = a;
                //a的父节点指向c
                a.parent = c;
            }
    

    实现右旋方法:


    右旋.jpg
            /**
             * 节点右旋
             * //            转换前:
             * //                |
             * //                a   <-
             * //               / \
             * //              b   c
             * //             / \
             * //            z  h
             * //
             * //            转换后:
             * //
             * //                |
             * //                b
             * //               / \
             * //              z   a  <-
             * //                 / \
             * //                h  c
             */
            private void rightRotate(AVLNode<T> a) {
                AVLNode<T> b = a.leftChild;
    
                //1.b的父节点变为a的父节点,a的父节点的孩子变为b
                b.parent = a.parent;
                //a的父节点的孩子变为b
                if (a.parent == null) {//根节点,即a没有父节点
                    root = b;
                } else if (a.parent.leftChild == a) {//a是左孩子
                    a.parent.leftChild = b;
                } else {
                    a.parent.rightChild = b;
                }
    
                //2.a的左孩子变为h,h父节点指向a
                AVLNode<T> h = b.rightChild;
                a.leftChild = b.leftChild;
                if (h != null) {
                    h.parent = a;
                }
    
                //3.b的右孩子指向a,a的父节点变为b
                b.rightChild = a;
                //a的父节点变为b
                a.parent = b;
            }
    

    实现左平衡和右平衡:

            /**
             * 右平衡
             */
            public void rightBalance(AVLNode<T> t) {
                AVLNode<T> tr = t.rightChild;
    
                switch (tr.balance) {
                    case RH:
    //            1、如果新的结点插入到t的右孩子的右子树中,则直接进行左旋操作即可
    //              t                                            tr
    //            /   \                                        /     \
    //           l     tr              左旋操作                   t       trr
    //                /   \         ----------->             / \     /    \
    //              trl    trr                             l   trl  rrl    rrr
    //                    /   \
    //                  rrl     rrr  <----插入rrl或rrr
                        leftRotate(t);
                        t.balance = EH;
                        tr.balance = EH;
                        //trr平衡因子不变
                        break;
                    case LH://2、如果新的结点插入到p的右孩子的左子树中,则需要进行分情况讨论
                        switch (tr.leftChild.balance) {
                            case LH:   //情况a:当p的右孩子的左子树根节点的balance = LEFT_HIGH
                                //          t                       t                           trl
                                //         /  \                    /  \                        /   \
                                //        2   tr        tr右旋      2  trl         t左旋          t     tr
                                //            /  \     ------->       /  \      ------->     /  \     \
                                //        trl     5                  6   tr                 2   6      5
                                //       /                             \
                                //      6   <----插入                  5
                                t.balance = EH;
                                tr.balance = RH;
                                tr.leftChild.balance = EH;
                                break;
                            case RH://情况b:当p的右孩子的左子树根节点的balance = RIGHT_HIGH
                                //          t                       t                           trl
                                //         /  \                    /  \                        /   \
                                //        2   tr        tr右旋      2  trl         t左旋          t    tr
                                //            /  \     ------->          \      ------->     /     /  \
                                //           trl  5                      tr                 2     6    5
                                //            \                          /  \
                                //             6    <----插入         6    5
                                t.balance = LH;
                                tr.balance = EH;
                                tr.leftChild.balance = EH;
                                break;
                            case EH://情况C:当p的右孩子的左子树根节点的balance = EQUAL_HIGH
                                //          t                       t                           trl
                                //            \                       \                        /   \
                                //            tr        tr右旋         trl        t左旋       t    tr
                                //           /         ------->         \       -------> 
                                //         trl  <----插入             tr                  
                                t.balance = EH;
                                tr.balance = EH;
                                tr.leftChild.balance = EH;
                                break;
                        }
    
                        rightRotate(t.rightChild);
                        leftRotate(t);
                        break;
                    case EH:
                        break;
                }
            }
    
            /**
             * 左平衡
             */
            public void leftBalance(AVLNode<T> t) {
                AVLNode<T> tl = t.leftChild;
    
                switch (tl.balance) {
                    case LH://1、如果新的结点插入到t的左孩子的左子树中,则直接进行右旋操作即可
    //                  t                                      tl
    //                 /  \         t右旋操作                  /         \
    //                tl   tr       ------------->        tll         t
    //               /  \                                /  \        /   \
    //              tll  tlr                           lcll  lclr    tlr   tr 
    //              /  \
    //            lcll   lclr <----插入lcll或lclr
                        rightRotate(t);
                        t.balance = EH;
                        tl.balance = EH;
                        //tll平衡因子不变
                        break;
                    case RH://2、如果新的结点插入到t的左孩子的右子树中,则需要进行分情况讨论
                        switch (tl.rightChild.balance) {
                            case RH://情况a:当t的左孩子的右子树根节点的balance = RIGHT_HIGH
                                //          t                       t                           tlr
                                //         /  \                    /  \                        /  \
                                //        tl   6      tl左旋     tlr    6       t右旋             tl    t
                                //       /  \       ------->     /  \        -------->       /    /  \
                                //      3  tlr                 tl    5                      3    5    6
                                //            \                /
                                //             5  <----插入     3
                                t.balance = EH;
                                tl.balance = LH;
                                tl.rightChild.balance = EH;
                                break;
                            case LH://情况b:当t的左孩子的右子树根节点的balance = LEFT_HIGH
                                //          t                       t                          tlr
                                //         /  \                    /  \                        /  \
                                //       tl    6      tl左旋      tlr    6          t右旋        tl    t
                                //      /  \        ------->     /              -------->    / \    \
                                //     3  tlr                   tl                          3   5    6
                                //        /                    / \
                                //       5   <----插入          3   5
                                t.balance = RH;
                                tl.balance = EH;
                                tl.rightChild.balance = EH;
                                break;
                            case EH://情况c:当t的左孩子的右子树根节点的balance = EQUAL_HIGH
                                //          t                       t                          tlr
                                //         /                       /                           /  \
                                //        tl            tl左旋    tlr            t右旋         tl   t
                                //          \          ------->   /            -------->              
                                //         tlr  <----插入        tl                                     
                                t.balance = EH;
                                tl.balance = EH;
                                tl.rightChild.balance = EH;
                                break;
                        }
    
                        leftRotate(t.leftChild);
                        rightRotate(t);
                        break;
                    case EH:
                        break;
                }
            }
    

    实现插入元素:

            /**
             * 插入元素
             * @param value
             */
            public void insertNode(T value) {
                if (root == null) {//没有元素
                    root = new AVLNode<>(value, null, null, null);
                } else {
                    Comparable e = value;
                    AVLNode<T> head = root;
                    AVLNode<T> parent = null;
                    int cmp = 0;
                    while (head != null) {
                        cmp = e.compareTo(head.value);
    
                        parent = head;
                        if (cmp == 0) {
                            return;
                        } else if (cmp > 0) {//往右子树偏移
                            head = head.rightChild;
                        } else {
                            head = head.leftChild;
                        }
                    }
    
                    if (cmp > 0) {//往右子树插入节点
                        parent.rightChild = new AVLNode<>(value, null, null, parent);
                    } else {
                        parent.leftChild = new AVLNode<>(value, null, null, parent);
                    }
                    
                    //平衡因子调整
                    while (parent != null) {
                        if (e.compareTo(parent.value) > 0) {//右子树多了深度
                            parent.balance--;
                        } else {
                            parent.balance++;
                        }
    
                        if(parent.balance == 0){//插入后正好平衡了,不用处理了
                            break;
                        }
                        
                        if (Math.abs(parent.balance) == 2) {//不平衡了
                            //根据平衡因子进行旋转操作
                            calcBalance(parent);
                            break;
                        } else {//继续往上找父亲,调整平衡因子
                            parent = parent.parent;
                        }
                    }
                }
    
                size++;
            }
    
            /**
             * 处理平衡问题
             * @param parent
             */
            private void calcBalance(AVLNode<T> parent) {
                if (parent.balance == -2) {//右子树多了
                    rightBalance(parent);
                } else {
                    leftBalance(parent);
                }
            }
    

    完整代码:

        /**
         * 平衡二叉树
         */
        public static class AVLTree<T extends Comparable<T>> {
            //平衡因子 左树深度多
            public static final int LH = 1;
            //平衡因子 右数深度多
            public static final int RH = -1;
            //平衡因子 左右树深度相同
            public static final int EH = 0;
    
            //根节点
            AVLNode<T> root;
            
            //元素个数
            private int size = 0;
    
            public AVLTree() {
            }
    
            public AVLTree(AVLNode<T> root) {
                this.root = root;
            }
    
            /**
             * 节点左旋
             * //            转换前:
             * //                |
             * //                a   <-
             * //               / \
             * //              b   c
             * //                  / \
             * //                 z  h
             * //
             * //            转换后:
             * //
             * //                |
             * //                c
             * //               / \
             * //         ->   a   h
             * //             / \
             * //            b  z
             */
            private void leftRotate(AVLNode<T> a) {
                AVLNode<T> c = a.rightChild;
    
                //1.a的父节点的孩子指向c,c的父节点变为a的父节点
                if (a.parent == null) {//根节点,即a没有父节点
                    root = c;
                } else if (a.parent.leftChild == a) {//a是左孩子
                    a.parent.leftChild = c;
                } else {//a是右孩子
                    a.parent.rightChild = c;
                }
                //c的父节点变为a的父节点
                c.parent = a.parent;
    
                //2.a的右孩子变为z
                AVLNode<T> z = c.leftChild;
                a.rightChild = z;
                //z父节点指向a
                if (z != null)
                    z.parent = a;
    
                //3.c的左孩子变为a,a的父节点指向c
                c.leftChild = a;
                //a的父节点指向c
                a.parent = c;
            }
    
            /**
             * 节点右旋
             * //            转换前:
             * //                |
             * //                a   <-
             * //               / \
             * //              b   c
             * //             / \
             * //            z  h
             * //
             * //            转换后:
             * //
             * //                |
             * //                b
             * //               / \
             * //              z   a  <-
             * //                 / \
             * //                h  c
             */
            private void rightRotate(AVLNode<T> a) {
                AVLNode<T> b = a.leftChild;
    
                //1.b的父节点变为a的父节点,a的父节点的孩子变为b
                b.parent = a.parent;
                //a的父节点的孩子变为b
                if (a.parent == null) {//根节点,即a没有父节点
                    root = b;
                } else if (a.parent.leftChild == a) {//a是左孩子
                    a.parent.leftChild = b;
                } else {
                    a.parent.rightChild = b;
                }
    
                //2.a的左孩子变为h,h父节点指向a
                AVLNode<T> h = b.rightChild;
                a.leftChild = b.leftChild;
                if (h != null) {
                    h.parent = a;
                }
    
                //3.b的右孩子指向a,a的父节点变为b
                b.rightChild = a;
                //a的父节点变为b
                a.parent = b;
            }
    
            /**
             * 右平衡
             */
            public void rightBalance(AVLNode<T> t) {
                AVLNode<T> tr = t.rightChild;
    
                switch (tr.balance) {
                    case RH:
    //            1、如果新的结点插入到t的右孩子的右子树中,则直接进行左旋操作即可
    //              t                                            tr
    //            /   \                                        /     \
    //           l     tr              左旋操作                   t       trr
    //                /   \         ----------->             / \     /    \
    //              trl    trr                             l   trl  rrl    rrr
    //                    /   \
    //                  rrl     rrr  <----插入rrl或rrr
                        leftRotate(t);
                        t.balance = EH;
                        tr.balance = EH;
                        //trr平衡因子不变
                        break;
                    case LH://2、如果新的结点插入到p的右孩子的左子树中,则需要进行分情况讨论
                        switch (tr.leftChild.balance) {
                            case LH:   //情况a:当p的右孩子的左子树根节点的balance = LEFT_HIGH
                                //          t                       t                           trl
                                //         /  \                    /  \                        /   \
                                //        2   tr        tr右旋      2  trl         t左旋          t     tr
                                //            /  \     ------->       /  \      ------->     /  \     \
                                //        trl     5                  6   tr                 2   6      5
                                //       /                             \
                                //      6   <----插入                  5
                                t.balance = EH;
                                tr.balance = RH;
                                tr.leftChild.balance = EH;
                                break;
                            case RH://情况b:当p的右孩子的左子树根节点的balance = RIGHT_HIGH
                                //          t                       t                           trl
                                //         /  \                    /  \                        /   \
                                //        2   tr        tr右旋      2  trl         t左旋          t    tr
                                //            /  \     ------->          \      ------->     /     /  \
                                //           trl  5                      tr                 2     6    5
                                //            \                          /  \
                                //             6    <----插入         6    5
                                t.balance = LH;
                                tr.balance = EH;
                                tr.leftChild.balance = EH;
                                break;
                            case EH://情况C:当p的右孩子的左子树根节点的balance = EQUAL_HIGH
                                //          t                       t                           trl
                                //            \                       \                        /   \
                                //            tr        tr右旋         trl        t左旋       t    tr
                                //           /         ------->         \       -------> 
                                //         trl  <----插入             tr                  
                                t.balance = EH;
                                tr.balance = EH;
                                tr.leftChild.balance = EH;
                                break;
                        }
    
                        rightRotate(t.rightChild);
                        leftRotate(t);
                        break;
                    case EH:
                        break;
                }
            }
    
            /**
             * 左平衡
             */
            public void leftBalance(AVLNode<T> t) {
                AVLNode<T> tl = t.leftChild;
    
                switch (tl.balance) {
                    case LH://1、如果新的结点插入到t的左孩子的左子树中,则直接进行右旋操作即可
    //                  t                                      tl
    //                 /  \         t右旋操作                  /         \
    //                tl   tr       ------------->        tll         t
    //               /  \                                /  \        /   \
    //              tll  tlr                           lcll  lclr    tlr   tr 
    //              /  \
    //            lcll   lclr <----插入lcll或lclr
                        rightRotate(t);
                        t.balance = EH;
                        tl.balance = EH;
                        //tll平衡因子不变
                        break;
                    case RH://2、如果新的结点插入到t的左孩子的右子树中,则需要进行分情况讨论
                        switch (tl.rightChild.balance) {
                            case RH://情况a:当t的左孩子的右子树根节点的balance = RIGHT_HIGH
                                //          t                       t                           tlr
                                //         /  \                    /  \                        /  \
                                //        tl   6      tl左旋     tlr    6       t右旋             tl    t
                                //       /  \       ------->     /  \        -------->       /    /  \
                                //      3  tlr                 tl    5                      3    5    6
                                //            \                /
                                //             5  <----插入     3
                                t.balance = EH;
                                tl.balance = LH;
                                tl.rightChild.balance = EH;
                                break;
                            case LH://情况b:当t的左孩子的右子树根节点的balance = LEFT_HIGH
                                //          t                       t                          tlr
                                //         /  \                    /  \                        /  \
                                //       tl    6      tl左旋      tlr    6          t右旋        tl    t
                                //      /  \        ------->     /              -------->    / \    \
                                //     3  tlr                   tl                          3   5    6
                                //        /                    / \
                                //       5   <----插入          3   5
                                t.balance = RH;
                                tl.balance = EH;
                                tl.rightChild.balance = EH;
                                break;
                            case EH://情况c:当t的左孩子的右子树根节点的balance = EQUAL_HIGH
                                //          t                       t                          tlr
                                //         /                       /                           /  \
                                //        tl            tl左旋    tlr            t右旋         tl   t
                                //          \          ------->   /            -------->              
                                //         tlr  <----插入        tl                                     
                                t.balance = EH;
                                tl.balance = EH;
                                tl.rightChild.balance = EH;
                                break;
                        }
    
                        leftRotate(t.leftChild);
                        rightRotate(t);
                        break;
                    case EH:
                        break;
                }
            }
    
            /**
             * 插入元素
             * @param value
             */
            public void insertNode(T value) {
                if (root == null) {//没有元素
                    root = new AVLNode<>(value, null, null, null);
                } else {
                    Comparable e = value;
                    AVLNode<T> head = root;
                    AVLNode<T> parent = null;
                    int cmp = 0;
                    while (head != null) {
                        cmp = e.compareTo(head.value);
    
                        parent = head;
                        if (cmp == 0) {
                            return;
                        } else if (cmp > 0) {//往右子树偏移
                            head = head.rightChild;
                        } else {
                            head = head.leftChild;
                        }
                    }
    
                    if (cmp > 0) {//往右子树插入节点
                        parent.rightChild = new AVLNode<>(value, null, null, parent);
                    } else {
                        parent.leftChild = new AVLNode<>(value, null, null, parent);
                    }
                    
                    //平衡因子调整
                    while (parent != null) {
                        if (e.compareTo(parent.value) > 0) {//右子树多了深度
                            parent.balance--;
                        } else {
                            parent.balance++;
                        }
    
                        if(parent.balance == 0){//插入后正好平衡了,不用处理了
                            break;
                        }
                        
                        if (Math.abs(parent.balance) == 2) {//不平衡了
                            //根据平衡因子进行旋转操作
                            calcBalance(parent);
                            break;
                        } else {//继续往上找父亲,调整平衡因子
                            parent = parent.parent;
                        }
                    }
                }
    
                size++;
            }
    
            /**
             * 处理平衡问题
             * @param parent
             */
            private void calcBalance(AVLNode<T> parent) {
                if (parent.balance == -2) {//右子树多了
                    rightBalance(parent);
                } else {
                    leftBalance(parent);
                }
            }
    
            class AVLNode<T> {
                T value;
                AVLNode<T> leftChild;
                AVLNode<T> rightChild;
                AVLNode<T> parent;
                //平衡因子
                int balance = EH;
    
                public AVLNode(T value, AVLNode<T> leftChild, AVLNode<T> rightChild, AVLNode<T> parent) {
                    this.value = value;
                    this.leftChild = leftChild;
                    this.rightChild = rightChild;
                    this.parent = parent;
                }
            }
        }
    

    测试输出:

        public static void main(String args[]) {
            AVLTree<Integer> avlTree = new AVLTree();
            avlTree.insertNode(5);
            avlTree.insertNode(-1);
            avlTree.insertNode(6);
            avlTree.insertNode(4);
            avlTree.insertNode(2);
            avlTree.insertNode(7);
            avlTree.insertNode(0);
    
            dfs(avlTree);
        }
    
        private static void dfs(AVLTree<Integer> avlTree) {
            Deque<AVLTree.AVLNode> deque = new LinkedList<>();
    
            if (avlTree.root != null) {
                deque.offer(avlTree.root);
            }
            while (!deque.isEmpty()) {
                int size = deque.size();
                while (size > 0) {
                    AVLTree.AVLNode node = deque.poll();
    
                    System.out.print(node.value + " ");
                    if (node.leftChild != null) {
                        deque.offer(node.leftChild);
                    }
                    if (node.rightChild != null) {
                        deque.offer(node.rightChild);
                    }
    
                    size--;
                }
    
                System.out.println();
            }
        }
    

    结果:
    5
    2 6
    -1 4 7
    0

    相关文章

      网友评论

          本文标题:平衡二叉树AVLTree手写实现(Java)

          本文链接:https://www.haomeiwen.com/subject/qvmxvltx.html