算法:树和图-理论

引入树

在说树之前,我们先回想一下链表,在当前节点保存下一节点的引用,类时的如下:

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

我们用过链表会发现,我们要想在链表中搜索或者访问一个元素时特别麻烦的,时间时间复杂度是O(N)的,为什么搜索和访问那么慢呢?? 我们仔细一想

  • 1.链表一个线性结构,只能从头到尾的遍历元素得到需要的值,并不像数组可以通过下标取得。
  • 2.我们存入数据的时候,这个是一个无序的过程,我们只知道有数据进来就马上存进去。

假如从这两点入手的话,那么我们应该可以加快链表的搜索和访问的速度。某些研究人员发现,可以在这个链表的基础上,增加多一个节点的引用,即现在一个节点中有多个不一样的节点引用。

  • 1.当前节点存入上一节点和下一节点的引用(双向链表)
  • 2.当前节点存入多个下一节点的引用(树)

我们把一个节点中存入多个下一节点的数据结构称为树,首节点称为根节点,如图:

树:每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外,每个子结点可以分为多个不相交的子树。

二叉树

上图是树这种数据结构的定义,我们比较长用到的二叉树有是怎么样的呢?如图:

二叉树:是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

上面这图也称完全二叉树

假设这个树有K层,此树前提是二叉树,K-1层必须是满的,K层左边(左子树)必须先满右边才能为空。

那么这样的数据结构是否可以增加访问速度呢?相比链表,在以知元素是在哪个子树,或许可以加快访问速度。在不知元素位置的时候,也是不能加快访问速度的,这还是一种无序的状态,需要访问元素还是需要遍历一次才可以找到。

⼆叉搜索树

某研究人员又发现,假如固定左边子树小于根节点,右边子树大于根节点,让元素存入的时候就排序好,那么访问速度就加快了,我们称这样的树为二叉搜索树。

它或者是一棵空树,或者是具有下列性质的二叉树:

⼆叉搜索树(英语: Binary Search Tree),也称⼆叉搜索树、有序⼆叉树(英语: ordered binary tree),排序⼆叉树(英语:sorted binary tree),是指⼀棵空树或者具有下列性质的⼆叉树: 
 1. 若任意节点的左⼦树不空,则左⼦树上所有结点的值均⼩于它的根结点的值; 
 2. 若任意节点的右⼦树不空,则右⼦树上所有结点的值均⼤于它的根结点的值; 
 3. 任意节点的左、右⼦树也分别为⼆叉查找树。

红黑树

假如有这样一个业务场景,一批已经排序好的数据,要找一个数据结构加快访问和搜索数据,那么二叉搜索树合适吗??仔细想象。

因为数据是排序好的,假如我们使用这种由序的二叉搜索树之类数据结构,那么最后存完数据后,这颗树就只有左节点或者右节点,实际变成一个链表了。

为了改变二叉搜索树存在的不足,对二叉搜索树进行改进,使整颗树可以自平衡,他将这种排序二叉树称为“对称二叉B树”、“红黑树”。

  • 性质1:每个节点要么是红色,要么是黑色。
  • 性质2:根节点永远是黑色的。
  • 除质3:所有的叶子节点都是空节点(即nil),并且是黑色的。
  • 性质4:每个红色节点的两个子节点都是黑色的。(从每个叶子到根的路径上不会有两个连续的红色节点。)
  • 性质5:从任一节点到其子树中每个叶子节点(nil节点)的路径都包含相同数量的黑色节点。

利用颜色规则,通过旋转达到树的平衡。我是看这篇文章大致了解的:教你透彻了解红黑树

下面通过JDK中的TreeMap详细讲解了解一下。

java的树(TreeMap)是怎么实现的?

翻了一下JDK,发现Java并没有自己实现常见的树,二叉树、二叉搜索树等结构,而是在其他已实现的数据结构中,再次利用树这种类型,加快访问搜索速度。查找发现,TreeMap是基于红黑树实现的。所以,我们从此入手。关于Map数据类型可以访问,算法:列表List、映射Map、集合Set-理论

public class TreeMap<K,V> extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable{                     
    private final Comparator<? super K> comparator;                //比较器
    public TreeMap() {   comparator = null;  }                     //构造函数之一

    private transient Entry<K,V> root;                             //数据实际保存类
    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;
    //还有很多常见的方法getKey、getValue、setValue、equals
    }
    public V put(K key, V value) {                                 //添加元素方法
        Entry<K,V> t = root;                                       //获取根节点
        if (t == null) {
            compare(key, key); // type (and possibly null) check

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        Comparator<? super K> cpr = comparator;                    //未指定比较器则为空
        if (cpr != null) {                                          
            do {
                parent = t;
                cmp = cpr.compare(key, t.key);
                if (cmp < 0)
                    t = t.left;
                else if (cmp > 0)
                    t = t.right;
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;//为当前元素类型的比较器
            do {                                                    //正常二叉树查找父节点,从根节点开始遍历
                parent = t;
                cmp = k.compareTo(t.key);
                if (cmp < 0)                                       //通过比较器后,当前值小于0              
                    t = t.left;                                    //和父节点的左节点进行比较
                else if (cmp > 0)
                    t = t.right;
                else                                               // 0 即 key相等
                    return t.setValue(value);                      //修改值
            } while (t != null);
        }
        Entry<K,V> e = new Entry<>(key, value, parent);            //保存数据到节点中
        if (cmp < 0)                                               //根据刚刚获取父节点时,比较的大小
            parent.left = e;                                       //,选择存入左右节点
        else
            parent.right = e;
        fixAfterInsertion(e);                     //上面是正常二叉树插入操作,后面是红黑树操作
        size++;
        modCount++;
        return null;
    }
}

上面是正常二叉树插入操作,下面是整理二叉树形成红黑树操作。

这个算法直接看容易懵,需要按图服用。下面给出每种情况调用的图例。

情况1,父亲节点在祖父节点左边,且叔叔节点为红色。

情况2,父亲节点在祖父节点左边,叔叔节点不是红色,且当前节点位于父节点的右边

情况3,当前父亲节点在祖父节点右边,且叔叔节点是红色

情况4,当前父亲节点在祖父节点右边,叔叔节点不是红色,且当前节点位于父节点的左边

/** From CLR */
    private void fixAfterInsertion(Entry<K,V> x) {                        //传入刚刚储存的节点
        x.color = RED;                                                    //设节点为红色,这样只可能违背 红黑树的性质4

        while (x != null && x != root && x.parent.color == RED) {        //当X的父节点为黑时,满足红黑树性质
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {     //当前节点的父亲节点在左边,才可能调用
//parentOf()返回 (p == null) ? null: p.parent
//leftOf()返回   (p == null) ? null: p.left;
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));    //获取当前节点祖父节点的右节点,也可以称为叔叔节点
                if (colorOf(y) == RED) {                          //情况1. y为红色时
                    setColor(parentOf(x), BLACK);                 //设父节点和叔叔节点为黑色,祖父节点红色
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED); 
                    x = parentOf(parentOf(x));                    //改当前节点为 祖父节点 并再次循环    
                } else {                                          //情况2,叔叔节点为黑或者为空
                    if (x == rightOf(parentOf(x))) {                    
                        x = parentOf(x);
                        rotateLeft(x);                            //左旋,为满足下面右旋后顺序正确
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateRight(parentOf(parentOf(x)));           //右旋
                }
            } else {        
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));        //获取叔叔节点
                if (colorOf(y) == RED) {                             //情况3,叔叔节点红色
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {                                        
                    if (x == leftOf(parentOf(x))) {                //情况4 ,叔叔节点不是红色
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }

    private void rotateLeft(Entry<K,V> p) {                        //左旋  ,情况2 左旋图解
        if (p != null) {
            Entry<K,V> r = p.right;
            p.right = r.left;
            if (r.left != null)
                r.left.parent = p;
            r.parent = p.parent;
            if (p.parent == null)
                root = r;
            else if (p.parent.left == p)
                p.parent.left = r;
            else
                p.parent.right = r;
            r.left = p;
            p.parent = r;
        }
    }
    
    private void rotateRight(Entry<K,V> p) {                   //右旋  ,情况2  右旋图解
        if (p != null) {
            Entry<K,V> l = p.left;
            p.left = l.right;
            if (l.right != null) l.right.parent = p;
            l.parent = p.parent;
            if (p.parent == null)
                root = l;
            else if (p.parent.right == p)
                p.parent.right = l;
            else p.parent.left = l;
            l.right = p;
            p.parent = l;
        }
    }

这个二叉树进行红黑处理,从开始的设置当前节点为红,判断父节点是否红、根节点,根据“性质4:每个红色节点的两个子节点都是黑色的”判断是否需要调整,通过调整节点颜色和旋转,保证二叉树符合所有红黑树的性质,达到一个自动平衡树的状态。

fixAfterInsertion方法逻辑顺序图

引入图

在树的基础上,我们知道当前节点中有多个指向下一节点的引用,假如还存在零个及以上指向上一节点(或者根节点)的引用,我们称之为图。

在链表的基础上,当前节点中有多个指向任意节点的引用。 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

JDK源码中好像并没有图这种数据结构。

下面给出几个Java实现图的博文。

Java数据结构和算法-图

数据结构(Java随笔)—图

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券