Haffman树

1.概念和构造：

我们来看一个案例：

image.png image.png

重点理解一下路径长度和带权的路径长度的概念：（权重就是结点到结点之间的数字，代表重复了多少次）

image.png

下面我们来看一下Haffman树的构造：

image.png image.png image.png

Haffman树编码：

image.png image.png

2.附上Haffman树的代码实现：

package com.xx.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;

public class HaffmanTree {

    public static void main(String[] arg0) {
        HaffmanTree haffmanTree = new HaffmanTree();
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        list.add(new TreeNode("good", 50));
        TreeNode node = new TreeNode("nice", 10);
        list.add(node);
        list.add(new TreeNode("greate", 20));
        list.add(new TreeNode("hello", 110));
        list.add(new TreeNode("hi", 200));
        haffmanTree.showHaffman(haffmanTree.createHaffmanTree(list));
        haffmanTree.getCode(node);
    }

    TreeNode root;

    // 创建哈夫曼树
    public TreeNode createHaffmanTree(ArrayList<TreeNode> list) {
        // 排序
        while (list.size() > 1) {
            // 可以根据输入的数组不同用不同的方法进行排序
            Collections.sort(list);
            TreeNode left = list.get(list.size() - 1);
            TreeNode right = list.get(list.size() - 2);
            TreeNode parent = new TreeNode("tree", left.weight + right.weight);

            parent.leftChild = left;
            parent.rightChild = right;

            left.parent = parent;
            right.parent = parent;

            list.remove(right);
            list.remove(left);

            list.add(parent);
        }
        root = list.get(0);
        return root;
    }

    // 从上到小 从左往右依次显示
    public void showHaffman(TreeNode root) {
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.offer(root);
        while (!list.isEmpty()) {
            // 先进先出
            TreeNode node = list.pop();
            System.out.println(node.data);
            if (node.leftChild != null) {
                list.offer(node.leftChild);
            }
            if (node.rightChild != null) {
                list.offer(node.rightChild);
            }
        }
    }
    // 获取编码
    public void getCode(TreeNode node) {
        TreeNode tNode = node;
        Stack<String> stack = new Stack<String>();
        while (tNode != null && tNode.parent != null) {
            if (tNode.parent.leftChild == tNode) {
                // node是左节点
                stack.push("0");
            } else if (tNode.parent.rightChild == tNode) {
                // node是右节点
                stack.push("1");
            }
            tNode = tNode.parent;
        }
        System.out.println();
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }

    public static class TreeNode<T> implements Comparable<TreeNode<T>> {

        T data;
        int weight;// 权重
        TreeNode leftChild;
        TreeNode rightChild;
        TreeNode parent;

        public TreeNode(T data, int weight) {
            this.data = data;
            this.weight = weight;
            leftChild = null;
            rightChild = null;
            parent = null;
        }

        // 倒序 从大到小
        public int compareTo(TreeNode<T> o) {
            // TODO Auto-generated method stub
            if (this.weight > o.weight) {
                return -1;
            } else if (this.weight < o.weight) {
                return 1;
            }
            return 0;
        }

    }
}

AVL树（平衡二叉树）

概念：

1.平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差最多等于1.
2.平衡因子:二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）,上面的概念又可以说成是 每个节点的平衡因子<=1的二叉排序树。
3.最小不平衡子树：距离插入结点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们成为最小不平衡子树。

构建平衡二叉树：

image.png
image.png
image.png image.png image.png 左旋： image.png
右旋： image.png

插入规则：

1.左平衡操作：结点t的不平衡是因为左子树过深

image.png

2.右平衡操作：结点t的不平衡是因为右子树过深

image.png

实现代码：

package com.xx.tree;

import java.util.LinkedList;

/**
 * AVL树(二叉平衡树)
 * 
 */
public class AVLTree<E extends Comparable<E>> {
    Node<E> root;
    int size = 0;
    private static final int LH = 1;
    private static final int RH = -1;
    private static final int EH = 0;
    /**
     * 左旋转
     * @param x
     */
    public void left_rotate(Node<E> x) {
        if (x != null) {
            Node<E> y = x.right;// 先取到Y结点
            // 1。把贝塔作为X的右孩子
            x.right = y.left;
            if (y.left != null) {
                y.left.parent = x;
            }
            // 2。把Y移到原来X的位置
            y.parent = x.parent;
            if (x.parent == null) {
                root = y;
            } else {
                if (x.parent.left == x) {
                    x.parent.left = y;

                } else if (x.parent.right == x) {
                    x.parent.right = y;
                }
            }
            // 3。X作为Y的左孩子
            y.left = x;
            x.parent = y;
        }
    }
    /**
     * 右旋转
     * @param y
     */
    public void right_rotate(Node<E> y) {
        if (y != null) {
            Node<E> yl = y.left;

            // step1
            y.left = yl.right;
            if (yl.right != null) {
                yl.right.parent = y;
            }

            // step2
            yl.parent = y.parent;
            if (y.parent == null) {
                root = yl;
            } else {
                if (y.parent.left == y) {
                    y.parent.left = yl;
                } else if (y.parent.right == y) {
                    y.parent.right = yl;
                }
            }
            // step3
            yl.right = y;
            y.parent = yl;
        }
    }
    /**
     * 右平衡操作，即结点t的不平衡是因为右子树过深
    */
    public void rightBalance(Node<E> t) {
        Node<E> tr = t.right;
        switch (tr.balance) {
        case RH:// 新的结点插入到t的右孩子的右子树中
            left_rotate(t);
            t.balance = EH;
            tr.balance = EH;
            break;
        case LH:// 新的结点插入到t的右孩子的左子树中
            Node<E> trl = tr.left;
            switch (trl.balance) {
            case RH:
                t.balance = LH;
                tr.balance = EH;
                trl.balance = EH;
                break;
            case LH:
                t.balance = EH;
                tr.balance = RH;
                trl.balance = EH;
                break;
            case EH:
                tr.balance = EH;
                trl.balance = EH;
                t.balance = EH;
                break;

            }
            right_rotate(t.right);
            left_rotate(t);
            break;

        }
    }
    /**
     * 左平衡操作，即结点t的不平衡是因为左子树过深
    */
    public void leftBalance(Node<E> t) {
        Node<E> tl = t.left;
        switch (tl.balance) {
        case LH:
            right_rotate(t);
            tl.balance = EH;
            t.balance = EH;
            break;
        case RH:
            Node<E> tlr = tl.right;
            switch (tlr.balance) {
            case LH:
                t.balance = RH;
                tl.balance = EH;
                tlr.balance = EH;
                break;
            case RH:
                t.balance = EH;
                tl.balance = LH;
                tlr.balance = EH;
                break;
            case EH:
                t.balance = EH;
                tl.balance = EH;
                tlr.balance = EH;
                break;

            default:
                break;
            }
            left_rotate(t.left);
            right_rotate(t);
            break;

        }
    }
    //插入
    public boolean insertElement(E element) {
        Node<E> t = root;
        if (t == null) {
            root = new Node<E>(element, null);
            size = 1;
            root.balance = 0;
            return true;
        } else {
            // 开始找到要插入的位置
            int cmp = 0;
            Node<E> parent;
            Comparable<? super E> e = (Comparable<? super E>) element;
            do {
                parent = t;
                cmp = e.compareTo(t.elemet);
                if (cmp < 0) {
                    t = t.left;
                } else if (cmp > 0) {
                    t = t.right;
                } else {
                    return false;
                }
            } while (t != null);
            // 开始插入数据
            Node<E> child = new Node<E>(element, parent);
            if (cmp < 0) {
                parent.left = child;
            } else {
                parent.right = child;
            }
            // 节点已经放到了树上
            // 检查平衡，回溯查找
            while (parent != null) {
                cmp = e.compareTo(parent.elemet);
                if (cmp < 0) {
                    parent.balance++;
                } else {
                    parent.balance--;
                }
                if (parent.balance == 0) {// 如果插入后还是平衡树，不用调整
                    break;
                }
                if (Math.abs(parent.balance) == 2) {
                    // 出现了平衡的问题，需要修正
                    fixAfterInsertion(parent);
                    break;
                } else {
                    parent = parent.parent;
                }
            }
        }
        size++;
        return true;
    }

    public void showAVL(Node root) {
        LinkedList<Node> list = new LinkedList<Node>();
        list.offer(root);// 队列放入
        while (!list.isEmpty()) {
            Node node = list.pop();// 队列的取出
            System.out.println(node.elemet);
            if (node.left != null) {
                list.offer(node.left);
            }
            if (node.right != null) {
                list.offer(node.right);
            }
        }
    }

    private void fixAfterInsertion(Node<E> parent) {
        if (parent.balance == 2) {
            leftBalance(parent);
        }
        if (parent.balance == -2) {
            rightBalance(parent);
        }
    }

    public static class Node<E extends Comparable<E>> {
        E elemet;
        int balance = 0;// 平衡因子
        Node<E> left;
        Node<E> right;
        Node<E> parent;

        public Node(E elem, Node<E> pare) {
            this.elemet = elem;
            this.parent = pare;
        }

        public E getElemet() {
            return elemet;
        }

        public void setElemet(E elemet) {
            this.elemet = elemet;
        }

        public int getBalance() {
            return balance;
        }

        public void setBalance(int balance) {
            this.balance = balance;
        }

        public Node<E> getLeft() {
            return left;
        }

        public void setLeft(Node<E> left) {
            this.left = left;
        }

        public Node<E> getRight() {
            return right;
        }

        public void setRight(Node<E> right) {
            this.right = right;
        }

        public Node<E> getParent() {
            return parent;
        }

        public void setParent(Node<E> parent) {
            this.parent = parent;
        }

    }

    public static void main(String[] arg0){
        Integer[] nums={5,8,2,0,1,-2};
            AVLTree<Integer> tree=new AVLTree<Integer>();
            for(int i=0;i<nums.length;i++){
                tree.insertElement(nums[i]);
            }
            tree.showAVL((Node) tree.root);
    }
}

红黑树

上次我们讲到AVL树。AVL树的性能（添加，删除）还是比较大的，为了解决这些操作上的性能的问题，我们会用到红黑树。（查询的效率和AVL是差不多的）
红黑树是对平衡树的改进,任意一个节点，他的左右子树的层次最多不超过一倍。

红黑树定义

image.png

插入节点

插入节点：先按照二叉排序树的方式插入一个节点，再查找最小不平衡子树，以最小不平衡子树进行下面的操作

1. 插入的是根节点
    直接将节点涂黑
2. 插入的节点的父节点是黑色
    不违背任何性质，不用调整
3. 插入节点的父节点是红色
    3.1 父节点是祖父节点的左孩子
        3.1.1 情况1：祖父节点的另一个子节点（叔叔节点）是红色
        将当前节点的父节点和叔叔节点涂黑，祖父节点涂红，把当前节点指向祖父节点，从新的当前节点开始算法
        3.1.2 情况2：叔叔节点是黑色
            3.1.2.1 当前节点是其父节点的右孩子
            当前节点的父节点做为新的当前节点，以新当前节点为支点左旋。
            3.1.2.2 当前节点是其父节点的左孩子
            父节点变为黑色，祖父节点变红色，再祖父节点为支点进行右旋
    3.2 父节点是祖父节点的右孩子
          参考3.1 将左全部变成右即可

删除节点

删除节点：先进行二叉排序树的删除操作，然后已替换节点作为当前节点进行后面的平衡操作

1.当前节点是红色
    直接把当前节点染成黑色，结束。
2.当前节点是黑色
    2.1  被删除节点是父节点的左孩子
         2.1.1 当前节点是根节点
               什么都不做
         2.1.2 当前节点x的兄弟节点是红色(此时父节点和兄弟节点的子节点分为黑)
               把父节点染成红色，兄弟节点染成黑色，对父节点进行左旋，重新设置x的兄弟节点
         2.1.3 当前节点x 的兄弟节点是黑色
               2.1.3.1 兄弟节点的两个孩子都是黑色
               将x的兄弟节点设为红色，设置x的父节点为新的x节点
               2.1.3.2 兄弟的右孩子是黑色，左孩子是红色
               将x兄弟节点的左孩子设为黑色，将x兄弟节点设置红色，将x的兄弟节点右旋，右旋后，重新设置x的兄弟节点。
               2.1.3.3 兄弟节点的右孩子是红色
               把兄弟节点染成当前节点父节点颜色，把当前节点父节点染成黑色，兄弟节点右孩子染成黑色，再以当前节点的父节点为支点进行左旋，算法结算
    2.2  被删除节点是父节点的右孩子
          参照2.1 把左设置为右

红黑树的应用：

Hashtable
TreeSet
TreeMap

计算机科学中的树

image.png