从零开始学数据结构和算法(四)哈希表的思想和二叉树入门

作者: Alvin老师 | 来源:发表于2020-04-28 15:25 被阅读0次

从零开始学数据结构和算法(四)哈希表的思想和二叉树入门
leetcode和牛客网刷题
「Redis源码解读」—数据结构（二）哈希表
安卓开发者的知识清单
数据结构简要
MySQL索引简述--哈希索引
iOSer必须了解的数据结构
hash-table基础以及一些运用例子
第一章、综述
牛皮了！2020最全MySQL索引优化架构+索引系统+数据结构选

哈希表

特点

数组(顺序表)：寻址容易
链表：插入与删除容易
哈希表：寻址容易，插入删除也容易的数据结构

HashTable

哈希表（HashTable, 也叫散列表）

是根据关键码值(Key value)而直接进行访问的数据结构，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
关键码值(Key value)也可以当成是key的hash值

这个映射函数叫做散列函数
存放记录的数组叫做散列表

HashTable 例子

Key : {14, 19, 5, 7, 21, 1, 13, 0, 18} 散列表: 大小为13 的数组 a[13]; 散列函数: f(x) = x mod 13;
hashtable 需要自定义的内容

散列函数与散列表大小 hash 冲突的解决方案装填因子：为什么需要这个值？因为数据越接近数组最大值，可能产生冲突的情况就越多

缺点

扩容需要大量的空间和性能

应用

电话号码、字典、点歌系统、QQ、微信的好友等

设计（拉链法）

JDK 1.8 以前

JDK 1.8 开始

当链表长度超过阈值，就转成红黑树

树

什么是树

树的概念

节点与树的度

结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

层次和深度

森林

树的存储结构

双亲表示法

孩子表示法

双亲孩子表示法

把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中

孩子兄弟表示法

孩子兄弟表示法为每个节点设计三个域：一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域

二叉树

概念

斜树

满二叉树

完全二叉树

定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
1. 所有的叶结点都出现在第k层或k-l层（层次最大的两层）
2. 对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。
一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

二叉树的存储结构

顺序存储

链式存储

二叉树的遍历

前序 ( DLR )

规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树

中序 ( LDR )

规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树

后续 ( LRD )

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点

二叉树简单代码实现

public class BinarayTree {

    Node<String> root;

    public BinarayTree(String data){

        root=new Node<>(data,null,null);

    }

    public void createTree(){

        Node<String> nodeB=new Node<String>("B",null,null);

        Node<String> nodeC=new Node<String>("C",null,null);

        Node<String> nodeD=new Node<String>("D",null,null);

        Node<String> nodeE=new Node<String>("E",null,null);

        Node<String> nodeF=new Node<String>("F",null,null);

        Node<String> nodeG=new Node<String>("G",null,null);

        Node<String> nodeH=new Node<String>("H",null,null);

        Node<String> nodeJ=new Node<String>("J",null,null);

        Node<String> nodeI=new Node<String>("I",null,null);

        root.leftChild=nodeB;

        root.rightChild=nodeC;

        nodeB.leftChild=nodeD;

        nodeC.leftChild=nodeE;

        nodeC.rightChild=nodeF;

        nodeD.leftChild=nodeG;

        nodeD.rightChild=nodeH;

        nodeE.rightChild=nodeJ;

        nodeH.leftChild=nodeI;

}

/**
 * 中序访问树的所有节点
 */
public void midOrderTraverse(Node root){//逻辑
    if(root==null){
        return;
    }
    midOrderTraverse(root.leftChild);//逻辑
    System.out.println("mid:"+root.data);//输出
    midOrderTraverse(root.rightChild);//逻辑
}
/**
 * 前序访问树的所有节点  Arrays.sort();
 */
public void preOrderTraverse(Node root){
    if(root==null){
        return;
    }
    System.out.println("pre:"+root.data);
    preOrderTraverse(root.leftChild);
    preOrderTraverse(root.rightChild);
}
/**
 * 后序访问树的所有节点
 */
public void postOrderTraverse(Node root){
    if(root==null){
        return;
    }
    postOrderTraverse(root.leftChild);
    postOrderTraverse(root.rightChild);
    System.out.println("post:"+root.data);
}
/**
 * 节点
 */
public class Node<T>{
    T data;
    Node<T> leftChild;
    Node<T> rightChild;

    public Node(T data, Node<T> leftChild, Node<T> rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}
}

作者：DevYK
链接：https://juejin.im/post/5c9456f25188252d971438a9