数据结构之2叉查找树,二叉查找数

二叉树

二叉查找数

前言

在前头讲过了对数码的排序,
可是相当的慢大家就会意识数目标排序消除了壹部分标题,
但在有个别景况下仍旧不可知满意我们的供给, 三个是, 对数组的扩大容积, 更新
都以一件不太简单的政工, 须求重新复制数组, 甚至是简简单单的删减, 插入操作,
都供给对数组举行更新.

小编们清楚, 对于链表的去除和插入无疑是1件非常粗大略的业务,
可是要保管更新数据之后的有序性, 大家就必须找准 插入数据的地点,
在一如既往数组中, 大家得以由此二分查找在对数时间内达成它, 而对于链表
必须从头到尾挨个开始展览访问 ,才能获得咱们想要的结果.

二叉树就是那二种优点的汇聚.

定义

2个贰叉查找数(BST)是壹颗2叉树,当中每一种结点都含有一个Comparable的键以及相关联的值,且每一种结点的键都大于其左子树的任性结点的键,小于其右子树的自由结点的键

构建

从上边简单知道, 2叉树是以链表方式结合的不变集合.

链表保障增加和删除简洁, 有序性和其数据结构相结合有限援救了查找也变得万分急速.

在那里不得不提到另2个眼光, 索引, 数据大约以键值对的花样展大理存,
而键的集合 正是此处涉及的索引. 在那节之后, 也就简单驾驭,
为何数据库中给列加上索引之后能够对寻找速度有高大的升高.

实际二叉树 并不不熟悉, 在堆排序中的 二叉堆, 甚至于
快速排序的怀想都以2叉树的源泉.

忆起一下飞快排序, 在每二次迭代中, 将大家取出来的 ‘哨兵成分’ 放在中间,
将数组 或 子数组中的数据分为两半, 二分一低于, 八分之四大于.

而相应的, 二叉树则是在历次插入数据的时候, 从根节点不断向下寻找, 直到命中
或 未命中 举行 更新 或许 插入操作.

中央落实

  1. 数据表示
    键+ 值+ 左链接+右链接+结点计数器
  2. 查找
    即便树是空的,则查找未命中;假使搜索的键小于当前结点的键,则继续搜寻其左子树;如若搜索的键大于当前结点的键,则继续寻找其右子树;借使搜索的键等于当前结点的键,则查找命中。
  3. 插入
    即使树是空的,则赶回2个暗含该键值对的新结点。就算被寻找的键小于根节点的键,则持续在左子树中插入该键,不然在右子树中插入该键。(记得更新节点计数器)
  4. 性情分析
    二叉查找数的算法的运营时刻凭借于树的形状,而树的形状则取决于键的插入顺序。要是插入七个上行下效的键值对,则会冒出最坏景况。
    由N个随机键构造的二叉查找数,查找命二月插入命中的平均所需相比次数为~2lnN(1.39lgN)。
    二叉查找和插入的财力都以对数级别的(相比较于二分查找的优势)

基准

2叉树的根节点, 它的每2个节点都不得不有2个父节点指向自个儿(根节点除却,
没有父节点); 同时每一个节点都有左右两个链接, 左链接(左子树) 的全数键小于
当前节点, 右链接(右子树) 的全体键大于当前节点. 如下图所示:

不设有卓殊 或 空值, 这里就无法不提到另2个设定, 键值 非空且唯一.
在Java中的 HashTable 就存在那几个设定, 而在 HashMap 中也有 唯1键这几个设定.

当大家想要查找贰个键值, 顺着树一路向下搜寻, 当查找到空节点时,
称为未命中, 查找到 等于 被寻找的键值时, 称为命中.

对此一颗完全平衡树而言, 也便是从根节点到持有空节点的冲天都十分的树,
当树的万丈为 3贰 层时, 仅叶节点就存在四亿多节点,
也便是说要从上亿数量中查找到须要的键, 最多也不超越三10七遍.

在算法那本书中往过去的事情关过 log二 N 这些量级, 并没有太多关切,
近日才意识那是叁个多么恐怖的数目, 对于函数曲线, 随着N的叠加,
曲线特别平整, 上百亿, 上千亿的数据量拉长 也可是是在全面平衡树中 查找次数
增大2, 3, 随着N的络绎不绝增大, 那样的数据量对寻找质量的震慑微乎其微.

当然, 完美平衡二叉树, 当前的树自然是不周全的.
但也不影响那种数据结构的英豪影响力.

在此地自身也就不再图像和文字并茂的表达二叉树, 网上的材质早已很全,
已经能够让你生出贰个主干的2叉树的认识.

有序性相关的点子达成

  1. 最大键和最小键
    最小键:若是左链接为空,最小键就是根节点;假使左链接非空,最小键便是左子树的最小键
    最大键:借使右链接为空,最大键便是根节点;假使右链接非空,最大键便是右子树的最大键
  2. 开拓进取取整和向下取整
    floor(key) : key等于贰叉树的根节点,重回根节点的值
    二.一 key小于2叉树的根节点,floor(key)一定在根节点的左子树中
    二.二 key大于2叉树的根节点
    2.二.一 右子树中设有小于等于key的结点时,floor(key)在右子树中
    2.二.2 不然赶回根节点
  3. 分选操作
    搜索排行为k的键(树中有k个小于它的节点),假如左子树的结点数为t
    三.一 借使t > k 在左子树中找找排名为k的键
    3.二 假诺t < k 在右子树中找寻排行为k-t-1的键
    三.3 要是t=k 再次回到根节点
  4. 排名
    再次来到给定键在树中的排行
    四.1 假使给定的键小于根节点的键,则赶回该键在左子树中的排名
    四.2若是给定的键大于根节点的键,则赶回该键在右子树中的排行+左子树的节点个数+1
    4.3 即便给定的键等于根节点的键,则赶回左子树的节点个数
  5. 除去最大值和最小值
    deleteMin():假若左子树不为空,则要刨除的节点在左子树;借使左子树为空,则赶回该节点的右子树
  6. 删除操作
    1旦有个别节点左右子树都不为空,删除节点未来,会爆发三个子树而被去除的节点的父节点只空出了二个链接。能够采用被删去节点的后继节点(右子树中的最小节点)补充它的职位。
    陆.一 将本着即将被删去的结点的链接保存为t
    6.二 将x指向它的后继结点min(t.right)
    陆.叁 将x的右链接指向deleteMin(t.right)
    陆.肆 将x的左链接设为t.left

实现

精晓2叉树的规律并不是1件很难的政工, 而实现它才是本身不能够不翻越的一座山.

在时隔四日随后持续来写那篇文章:

小编用了七日的年华才贰叉树用java达成, 时期差不多一贯不参考 算法
那本书中的任何实现, 也从不使用递归的艺术去做那件事,
而是全体使用迭代的情势.

纸上得来终觉浅, 绝知此事要躬行.

代码上传至
https://github.com/zyzdisciple/algorithms4th/tree/master/src/zyx/algorithms4th/unitthree

代码完结

package edu.princeton.cs.algs4.chapter3;

/**
 * 使用二叉查找树实现的符号表
 * Created by tianxianhu on 2017/3/6.
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;
    private class Node{
        private Key key;
        private Value val;
        private Node left;
        private Node right;
        private int N; //维护一个当前节点为根节点的节点总数量

        public Node (Key key, Value val, int N) {
            this.key = key;
            this.val = val;
            this.N = N;
        }
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        else return x.N;
    }

    /**
     * 获取指定键的值,从根节点开始,比较键值
     * 小于当前键值则在左子树中继续寻找,大于则在右子树中继续寻找,等于则返回当前节点的值
     * @param key
     * @return
     */
    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return x.val;
        }
    }

    /**
     * 寻找key,找到则更新它的值,否则为它创建一个新节点,同时更新节点数量
     * @param key
     * @param val
     * @return
     */
    public Node put(Key key, Value val) {
        return put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        // 如果不存在,新建节点插入到字数当中
        if (x == null)
            return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        // 不存在,则继续在左/右子树上寻找
        if (cmp < 0) {
            x.left = put(x.left, key, val);
        } else if (cmp > 0) {
            x.right = put(x.right, key, val);
        } else {
            // 存在,则更新值
            x.val = val;
        }
        // 增加了节点,更新每个子树的数量
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Key min() {
        return min(root).key;
    }

    private Node min(Node x) {
        if (x.left == null)
            return x;
        return min(x.left);
    }

    /**
     * 将要查询的键值和根节点的键值进行比较
     * 1. 与根节点键值相等,返回当前节点的键
     * 1. 小于根节点键值,则在左子树中继续寻找
     * 2. 大于根节点键值,则在右子树中寻找(可能在右子树中,也可能是根节点)
     * 2.1 如果右子树中寻找返回null,则返回根节点
     * 2.2 如果在右子树中寻找到,则返回找到的节点
     * @param key
     * @return
     */
    public Key floor(Key key) {
        Node x = floor(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node floor(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        // 相等,返回当前值
        if (cmp == 0)
            return x;
        // 小于根节点,在左子树当中寻找
        if (cmp < 0)
            return floor(x.left, key);
        // 大于根节点,在右子树中寻找
        Node t = floor(x.right, key);
        // 存在则返回该节点,不存在则返回根节点
        if (t != null)
            return t;
        else
            return x;
    }

    /**
     * 查询排名为k的键(0-based)
     * 计算做子树的节点数量t,与排名k进行比较
     * 1. 如果t>k, 就继续在左子树中查找排名为k的键
     * 2. 如果k>t, 就在右子树中查找排名为k-t-1的键
     * 3. 如果k=t, 就返回当前节点
     * @param k
     * @return
     */
    public Key select(int k) {
        return select(root, k).key;
    }

    private Node select(Node x, int k) {
        if (x == null)
            return null;
        int t = size(x.left);
        if (k < t) {
            return select(x.left, k);
        } else if (t < k) {
            return select(x.right, k - t - 1);
        } else {
            return x;
        }
    }

    /**
     * 查询键key的排名
     * 将要查询的键与当前的键值进行比较
     * 1.如果相等,则返回根节点左子树的节点数
     * 2.小于根节点,则返回该键在左子树中的排名
     * 3.大于根节点,则返回size(x.left)+1+右子树中的排名
     * @param key
     * @return
     */
    public int rank(Key key) {
        return rank(root, key);
    }

    private int rank(Node x, Key key) {
        if (x == null)
            return 0;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return rank(x.left, key);
        else if (cmp > 0)
            return 1 + size(x.left) + rank(x.right, key);
        else
            return size(x.left);
    }

    /**
     * 1.不断检索左子树,直到遇见空的左子树
     * 2.返回该节点的右链接
     * 3.递归调用结束后更新节点计数器
     */
    public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node x) {
        if (x.left == null)
            return x.right;
        x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    /**
     * 1.寻找到要删除节点t的后继节点min(t.right)
     * 2.将后继节点x.right指向deleteMin(x.right),即删除后继节点以后的子树,该子树大于后继节点
     * 3.将后继节点x.left指向t.left
     * @param x
     * @param key
     * @return
     */
    private Node delete(Node x, Key key) {
        if (x == null)
            return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            x.left = delete(x.left, key);
        else if (cmp > 0)
            x.right = delete(x.right, key);
        else {
            if (x.left == null)
                return x.right;
            if (x.right == null)
                return x.left;
            Node t = x;
            x = min(t.right);
            x.right = deleteMin(t.right);
            x.left = t.left;
        }
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

}

Node

private class Node {

    private Node left;

    private Node right;

    private Key key;

    private Value value;

    private int N;

    public Node (Key key, Value value, int N) {

        this.key = key;
        this.value = value;
        this.N = N;
    }

    @Override
    public String toString() {
        return key == null ? null : key.toString();
    }
}

get()

接受2个 key 作为参数, 从root节点不断浓密, 当前节点的key 大于所给值,
向左子树深深, 不然小于向右子树深刻. 直到为 null(未命中) 或 等于(命中).

public Value get(Key key) {
    if (key == null)
        throw new RuntimeException("键值不能为null");

    Node tempNode = getNode(key);

    return tempNode == null ? null : tempNode.value;
}

private Node getNode(Key key) {
    Node temp = root;
    int cmp;

    while (temp != null) {
        cmp = key.compareTo(temp.key);
        if (cmp > 0) {
            temp = temp.right;
        } else if (cmp < 0) {
            temp = temp.left;
        } else {
            return temp;
        }
    }
    return null;
}

put()

办法接受 key, value 作为参数, 从root节点不断深刻, 当前节点key
大于参数key, 左子树深深, 小于则向右子树深深, 直到为null(插入) 或
等于(更新).

内需专注的是, 在 插入删除操作的时候, 都须要更新节点的 N 值.

@Override
public void put(Key key, Value value) {
    if (key == null)
        throw new RuntimeException("键值不能为null");

    Node newNode = new Node(key, value, 1);
    if (root == null) {
        root = newNode;
        return;
    }
    Node parent = root, child;
    int cmp;
    boolean flag; //表示要插入左 true, 右 false;

    while (true) {
        cmp = key.compareTo(parent.key);
        if (cmp > 0) {
            child = parent.right;
            flag = false;
        } else if (cmp < 0) {
            child = parent.left;
            flag = true;
        } else {
            parent.value = value;
            return;
        }

        if (child == null) {
            if (flag) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
            break;
        }

        parent = child;
    }

    updateN(key, 1);
}

private void updateN(Key key, int count) {

    Node temp = root;
    int cmp;
    while (temp != null) {
        cmp = key.compareTo(temp.key);
        if (cmp > 0) {
            temp.N += count;
            temp = temp.right;
        } else if (cmp < 0) {
            temp.N += count;
            temp = temp.left;
        } else {
            return;
        }
    }
}

delete()

delete方法的实现, 作者认为是可是复杂的, 越发是选拔迭代的秘诀,
当在剔除对应节点的同时, 就非得要有所父节点. 才能够删除相应的节点.

核情绪想:
同样的, 不断找到相应的节点. 假诺是叶节点, 删除不影响, 借使非叶节点,
删除的还要, 须要找到左子树的最大节点, 或 右子树的小不点儿节点, 替换当前节点,
同时令替换后的节点 的左右子节点 指向 原节点的左右子节点.

轮换节点意味着, 删除并回到用来替换的节点, 更改被轮换节点即可.
最终不要遗忘更新 N值.

@Override
public void delete(Key key) {
    if (key == null) {
        throw new NullPointerException();
    }

    //找出需要被删除的节点及其父节点
    Node parentNode = getParentNode(key), deleteNode;
    /**
    * 如果未命中, 直接返回
    * 如果删除的节点为根节点, 直接删除
    * 如果删除的节点为叶节点, 需要找到对应的父级节点, 将其指向置空
    * 如果非根节点/叶节点, 则需要找到左/右 树的最大/最小节点, 将置换后删除
    * 在这里我取 被删除节点的左子节点的最大子节点替换.
    */
    if (parentNode == null) {
        return;
    }
    int cmp = key.compareTo(parentNode.key);
    boolean flag;
    Node temp;

    if (cmp > 0) {
        deleteNode = parentNode.right;
        if (isLeaf(deleteNode)) { //如果是叶节点, 直接删除即可.
            updateN(deleteNode.key, -1); //先更新N后删除
            parentNode.right = null;
            return;
        }
        if (deleteNode.left == null) {
            temp = deleteNode.right;
        } else {
            temp = deleteMax(deleteNode.left);
        }
        flag = true;
    } else if (cmp < 0) {
        deleteNode = parentNode.left;
        if (isLeaf(deleteNode)) {
            parentNode.left = null;
            return;
        }
        if (deleteNode.left == null) {
            temp = deleteNode.right;
        } else {
            temp = deleteMax(deleteNode.left);
        }
        flag = false;
    } else {
        //表示当前处于根节点
        root = null;
        return;
    }
    temp.left = deleteNode.left;
    temp.right = deleteNode.right;
    temp.N = deleteNode.N;
    if (flag) {
        parentNode.right = temp;
    } else {
        parentNode.left = temp;
    }
}

private Node getParentNode(Key key) {

    if (root == null) {
        return null;
    }

    Node parent = root, child;
    int cmp = key.compareTo(root.key);

    if (cmp > 0) {
        child = parent.right;
    } else if (cmp < 0) {
        child = parent.left;
    } else {
        return parent;
    }

    while (true) {
        //表示查找未命中
        if (child == null) {
            return null;
        }
        cmp = key.compareTo(child.key);

        if (cmp > 0) {
            parent = child;
            child = parent.right;
        } else if (cmp < 0) {
            parent = child;
            child = parent.left;
        } else {
            return parent;
        }
    }
}

private boolean isLeaf(Node node) {
    return node.left == null && node.right == null;
}

private Node deleteMax(Node node) {

    if (node.right == null) {
        updateN(node.key, -1);
        return node;
    }

    Node parent = node, child;

    while (true) {
        child = parent.right;
        if (child.right == null) {
            //说明当前child为最大节点
            //无论当前是否是叶节点, 都令其指向, child.left;
            /*
                * 几次陷入一个误区, 非叶节点的话, 找child 的左节点的最大节点, 然而最终的目的
                * 仅仅是找到 node 的最大节点, 其实这个时候已经达到目的了.
                */
            parent.right = child.left;
            updateN(child.key, -1);
            return child;
        }
        parent = child.right;
    }
}

其他

二叉树的最要害的四个操作已经完毕, 其余操作一时就不再多说.

与删除操作同样复杂的是, 通过迭代的艺术 达成 迭代器的成效. 在此地,
作者用三个数组, 长度大于等于树最大惊人的数组,
保存当前被遍历节点的父节点.即可达成.

在前边的网站已经有了大部分贯彻, 及有关的测试类. 验证情势等.
就不再写出代码了.

在看习题的时候, 同样给出了几个相比较有趣的不二秘诀:

因为在②叉树生成的时候, 贰叉树自己的求证并不是壹件简单的事, 相比较复杂:

它分别证实了:

二叉树构成:

透过递归的不二等秘书诀遍历那棵树, 每遍历二个节点, 计数 count += 一, 如若 root.N
最终等于 count值, 则表示树中不存在循环等题材,
至少表达了它确实是壹棵2叉树.

2叉树的有序性:

同等通过递归的措施, 以各个节点作为 参数, 求取max 和 min,
保险那棵树中的每一个节点的key值都在两者之间.
且各种节点的子节点都以雷打不动的.

换句话来说, 需求证实每一个节点的 左节点<当前节点<右节点,
即可验证节点有序性.

二叉树键值的不另行:

遍历那棵树, 保险每种节点 它的子节点中不蕴涵和它的键值相同的节点.
在证实有序性之后来做那件事就非凡简单了.

将那三者按序结合, 即可验证1棵二叉树的准头了.

结语

贰叉树的帮助和益处, 毋庸置疑, 那是一种很是强大的数据结构. 但依旧存在难题,
这么些标题留在下节, 红黑树再来研究并缓解这么些难点.

相关文章