Tree Algorithm


Tree

  • 根节点 , root
  • 子节点
  • 叶子节点,没有子节点的节点,即度为零的节点
  • 兄弟节点:有相同父节点的子节点,即为兄弟节点,siblings
  • 祖先节点,该节点到根节点路径上的所有节点,都是该节点的祖先节点
  • 度, 节点的子节点个数
  • 层 , 根节点为第一层,其余节点为其父节点的层次 + 1
  • 深度, 根的深度为零, 其余节点深度为该节点到根节点的唯一路径长
  • 高度, 叶子节点高度为零,其余节点,为该节点到叶子节点的最长路径
  • 树的深度 = 树的高度

ps: 关于深度, 这里按照 WIKI EN 的定义说明

BT

binary tree , 二叉树

  • 第 n 层节点最大为 2n-1 ,root 为第一层,最大为 21-1 = 1
  • 深度为 k 的二叉树,最多有 2k+1 - 1 个节点 [注1]

示例图

Node 节点基本结构:

public BTreeNode {
    private BTreeNode left; // 左节点
    private BTreeNode right; // 右节点
    private Object value; // 值

    private boolean hasLeft() {
        return null != this.left;
    }

    private boolean hasRight() {
        return null != this.right;
    }
}

深度优先

DFS , Deep First Search

从根节点开始,优先搜索子节点,然后搜索同一层节点

前序遍历

preOrder traversal , 又称为先序遍历。处理方式是,从左到右,先处理自己,再处理左子节点,最后处理右子节点

则对照上图,我们得出的遍历顺序为: 1 -> 2 -> 3 -> 4 -> 5 -> 6

代码实现思路:

打印当前值(先处理自己) -> 打印左节点(递归) -> 打印右节点(递归)

// 递归
public static void preOrder(final BTreeNode root) {
    if(Objects.isNull(root)) return;
    System.out.println(root.value.toString());
    if(root.hasLeft()) preOrder(root.left);
    if(root.hasRight()) preOrder(root.right);
}

// 非递归 利用 stack
public void preOrder() {
    var ret = new ArrayList<T>();
    var cur = root;
    var stack = new Stack<BTreeNode>();
    stack.push(cur);
    while (!stack.isEmpty() && (cur = stack.pop()) != null) {
        ret.add(cur.value);
        if (Objects.nonNull(cur.right)) {
            stack.push(cur.right);
        }
        if (Objects.nonNull(cur.left)) {
            stack.push(cur.left);
        }
    }
}

中序遍历

inOrder traversal , 处理方式是,从左往右,先处理左子节点,自己在中间处理 , 最后处理右子节点

对照上图, 得出的遍历顺序 : 3 -> 2 -> 4 -> 1 -> 5 -> 6

代码实现思路:

打印左节点(递归) -> 打印自己 -> 打印右节点(递归)

// 递归
public static void inOrder(final BTreeNode root) {
    if(Objects.isNull(root)) return;
    if(root.hasLeft()) inOrder(root.left);
    System.out.println(root.value.toString());
    if(root.hasRight()) inOrder(root.right);
}

// 非递归, 利用 stack
public void inPrint() {
    var cur = root;
    var stack = new Stack<BTreeNode>();
    do {
        // 压入左节点
        if (Objects.nonNull(cur)) {
            stack.push(cur);
            cur = cur.left;
        } else {
            var tmp = stack.pop();
            System.out.println(tmp.value.toString)
            cur = tmp.right;
        }
    } while (!stack.isEmpty() || Objects.nonNull(cur));
}

发现没有, 和前序遍历的实现相比,只是改了下代码的位置


后序遍历

prostOrder traversal,处理方式是,从左往右, 先处理左子节点,再处理右子节点,最后处理自己

遍历顺序 : 3 -> 4 -> 2 -> 6 -> 5 -> 1

代码实现思路:

打印左节点(递归) -> 打印右节点(递归) -> 打印自己

public static void postOrder(final BTreeNode root) {
    if(Objects.isNull(root)) return;
    if(root.hasLeft()) postOrder(root.left);
    if(root.hasRight()) postOrder(root.right);
    System.out.println(root.value.toString());
}

public void postOrder() {
    var cur = root;
    // 记录处理的子节点 , 用来验证节点的右子节点是否被处理过
    BTreeNode pre = null;

    var stack = new Stack<BSTreeNode>();
    stack.push(cur);
    while (!stack.isEmpty()) {
        while (cur.hasLeft()) {
            cur = cur.left;
            stack.push(cur);
        }

        // 这里先不拿出来, 如果该节点有右子节点,则优先处理右子节点
        var tmp = stack.peek();
        if (tmp.hasRight() && tmp.right != pre) {
            cur = tmp.right;
            stack.push(cur);
        } else {
            pre = stack.pop();
            ret.add(pre.value);
        }
    }
}

同样,实现方式和上面的两种遍历方式相比,只是变更了顺序。

可以看到,所谓的前中后序遍历,就是看什么时候处理自己,先处理自己就是前序,中间处理就是中序,最后处理就是后序。

广度优先

BFS ,Breath First Search

从根节点开始,优先搜索同一层节点,然后搜索子节点

参照上图,我们得出的遍历顺序是: 1 -> 2 -> 5 -> 3 -> 4 -> 6

代码实现思路(借助队列):

将每层依次塞入队列的尾部,依次从队头取出数据读取

// 递归
public static void bfs(final BTreeNode root) {
    var q = new ArrayDeque<BTreeNode>();
    BTreeNode node = root;
    do {
        System.out.println(node.value.toString());
        if (node.hasLeft()) q.add(node.left); // 添加到队尾
        if (node.hasRight()) q.add(node.right);
    } while (null != (node = q.poll())); // 从队头取
}

// 非递归
public void bfs() {
    var ret = new ArrayList<T>();
    var queue = new ArrayDeque<BTreeNode>();
    queue.add(root);
    BTreeNode cur;
    while (!queue.isEmpty()) {
        cur = queue.remove();
        ret.add(cur.value);
        if (cur.hasLeft()) {
            queue.add(cur.left);
        }
        if (cur.hasRight()) {
            queue.add(cur.right);
        }
    }
}

BST

Binary Search Tree , 二叉查找树(二叉搜索树):任意节点的左子树(如果非空)值,小于当前节点, 任意节点的右子树(如果非空) 值, 大于或等于当前节点,任意节点的左、右子树也是二叉查找树。

总结一句话,就是左边最小,右边最大。

前驱节点 , 对于 BST 而言,一个节点的前驱节点,是一个节点值仅小于当前节点值的节点,如下图中, 8 的迁居节点是 3, 3 的前驱节点是 1

后继节点 , 对于 BST 而言,一个节点的后继节点,是一个节点值仅大于当前节点值的节点,如下图中, 8 的后继节点是 9, 9 的后继节点是 12

我们中序遍历该树,1 –> 3 –> 8 –> 9 –> 12 –> 13 , 此时再看前驱节点, 后继节点,就一目了然了。

时间复杂度,最坏 O(N) (变成一条链),平均 O(log N)。

BST

BSTreeNode 结构:

public class BSTree {
    private BSTreeNode root;
    private int size;

    static class BSTreeNode {
        private BSTree left;
        private BSTree right;
        private BSTreeNode<T> parent; // 父节点
        private Object value;
        public boolean hasLeft() {
            return null != this.left;
        }
        public boolean hasRight() {
            return null != this.right;
        }
    }
}

插入

分析:如果 root 节点为空,则直接作为 root 节点,否则,小于 root 则放到左侧,大于则放到右侧。

再次对 root 的左节点和右节点重复上述步骤,直到找到符合位置的地方停止。

代码实现:

private void insert(final BSTreeNode<T> r, final BSTreeNode<T> obj) {
    if (obj.compareTo(r) < 0) {
        if (null == r.left) {
            r.left = obj;
            return;
        }
        insert(r.left, obj);
    }
    if (obj.compareTo(r) >= 0) {
        if (null == r.right) {
            r.right = obj;
            return;
        }
        insert(r.right, obj);
    }
}

查找

根据给定值,查找 BST 中有无该节点

分析:同样从根节点开始搜索,小于则往左侧搜索,大于则往右侧搜索

代码实现:

private boolean contains(final BSTreeNode<T> r, final BSTreeNode<T> obj) {
    if (obj.compareTo(r) < 0 && null != r.left) return contains(r.left, obj);
    if (obj.compareTo(r) > 0 && null != r.right) return contains(r.right, obj);
    return obj.equals(r);
}

删除

删除给定值的节点(如果有此节点)

分析:

  1. 查找该节点,无则直接返回, 借助 contains 方法即可

  2. 若存在节点 P,则需要分开讨论:

    1. P 存在两个子节点(即节点度为二),我们可以用该节点的直接前驱节点(in-order predecessor),或者直接后继节点(in-order successor)替代 P , 然后删除后继节点,此时后继节点(此节点的左节点必然为空)的度变为 1, 我们可以进入到步骤二

    2. P 只有左子树或者右子树(即节点度为一) , 把该子节点挂到 P 的父节点即可

    3. P 没有子节点(即节点度为零), 则可以直接删除,不会影响树结构

BST Delete

代码实现 [2]

private void remove(BSTreeNode<T> toDelete) {
    // degree = 2
    if (toDelete.hasRight() && toDelete.hasLeft()) {
        // 寻找直接后继节点
        var successor = min(toDelete.right);
        toDelete.value = successor.value;
        // 此时 toDelete 变成了 degree = 1 的节点
        toDelete = successor;
    }

    // 处理 degree = 1 的情况
    var replacement = toDelete.hasLeft() ? toDelete.left : toDelete.right;
    // 表明有一个子节点
    if (replacement != null) {
        // 1. 设置子节点的父节点
        replacement.parent = toDelete.parent;
        // 2. 如果 toDelete 为 root
        if (toDelete.parent == null) {
            root = replacement;
        } else if (toDelete == toDelete.parent.left) {
            toDelete.parent.left = replacement;
        } else {
            toDelete.parent.right = replacement;
        }
    }
    // 只有一个 root 节点
    else if (toDelete.parent == null) {
        root = null;
    }
    // degree = 0
    else {
        if (toDelete == toDelete.parent.left) {
            toDelete.parent.left = null;
        } else {
            toDelete.parent.right = null;
        }
        toDelete.parent = null;
    }
}

RBT

Red Black Tree, 红黑树

正常的 BST,没有什么问题,但在某些情况下,BST 可能会退化成链表。比如依次插入 5,4,3,2,1 。这个时候, RBT 就出现了,它会对 BST 做再平衡操作(不要问我为什么,我也不知道计算机科学家们是怎么想出来的…)。

RBT 中:

  1. 根节点必须是 black ,所有新插入的节点,默认为 red 。

  2. 兄弟节点的颜色必须一致。

  3. 父子节点不能是全 red ,可以是全黑。

  4. 所有叶子节点为黑色。(对于这一条,代码实现时,基本可以忽略。因为所有叶子节点,默认会有一个 nil 的空姐点,而该空姐点是黑色)

Red Black Tree

旋转:

  1. 变颜色: 当前节点的父节点是红色,且父节点的兄弟节点也是红色,则

    1. 把父节点和叔叔节点变为黑色
    2. 把祖父节点变为红色
    3. 将祖父节点,设为工作节点,用来进行第二步
  2. 当前节点的父节点是红色,叔叔节点是黑色,且当前节点为父节点的右子树时,以父节点为轴进行左旋(左右左)

    image-20200425004625167

  3. 当前节点的父节点是红色,叔叔节点是黑色,且当前节点为父节点的左子树时,右旋(左左右 ):

    1. 把父节点变为黑色
    2. 把祖父节点变为红色
    3. 以祖父节点为轴右旋

    image-20200425004903494

Trie

字典树。常用于统计和排序大量字符串

// 后续待补充

Leetcode

B+

MySQL 的索引数据结构用的就是 B+ Tree

// 后续待补充

[1]

这里的定义参考 WIKI_EN

[2]

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}

// java.util.TreeMap#deleteEntry
private void deleteEntry(Entry<K,V> p) {
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key;
        p.value = s.value;
        p = s;
    } 
    // ...
}

这是 TreeMap 类里删除元素的一段代码。刚开始看的时候,我有点没搞懂,直接 p = s; 不就好了吗? 为什么要先赋值, 最后执行 p = s; 呢?

带着这个问题,我去问了问周公,豁然开朗,周公果真大神。

我们知道,java 中,我们执行 A a = new A(); 时, a 只是持有对象 A 的引用,说白了就是对象 A 的指针。

java 中对象的传递,也是引用传递,也就是说,我给你这个对象的地址,你改了这个对象,那其他持有这个对象地址的对象,同样也会跟着变化,因为操作的都是同一个对象嘛。

回到这里,deleteEntry 拿到一个 Entry 的引用 p, 我们设这个对象为 Entry-A , 通过 p.keyp.value 的操作,Entry-A 里的两个属性发生了变化,但是其他的属性没有变。其他持有 Entry-A 对象的引用,可以继续操作 Entry-A 。

而后把另一个对象,设为 Entry-B,的引用 s 赋值给 p ,则此时 p 不再是 Entry-A 的引用,而是化身成 Entry-B 的对象引用了。

Referenct

USFCA 算法动画展示


文章作者: peifeng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC-ND 4.0 许可协议。转载请注明来源 peifeng !
 上一篇
Sorts Sorts
Sorts本文主要介绍几种常见的排序算法,以及 Bloom 过滤器。 排序在正式介绍排序之前,先说下排序中的几个名词: 稳定 : 我们常说,这个排序算法是稳定的,那个是不稳定的,这里的稳定,是指,两个相同大小的元素 a,b ,在排序前后,
2020-04-26
下一篇 
Java 系列<二> -- 基础数据结构 Java 系列<二>-- 基础数据结构
本文着眼于 java 基础数据结构,以 Array , ArrayList , LinkedList , HashMap ,为主要分析点,介绍其底层存储结构及其特性。Queue, Stack 会略作分析。对于 HashMap, 其红黑树特性将会在另一篇文章介绍。
2020-04-22
  目录