算法笔记（二）

二分搜索、哈希表

散列表的实现叫做散列，散列是一种用来以常数平均时间执行插入，删除和查找的技术。

散列函数

public static int hash(String key,int tableSize){
    int hashVal=0;
    for(char k : key.toCharArray())
    hashVal+=k;
    return hashVal/tableSize;
}

解决冲突的方式

分离连接法

简单来说，类似于hashmap的结构，解决hash冲突的时候，使用链表的方式存储表中。

非链表散列法

• 线性探测法

出现冲突的时候，放在下一个地址位置上。

• 平方探测法

  f(i)=i*i,

并查集算法

树基本概念，二叉树（遍历详解）

• 树

  树可以用几种方式定义，定义树的第一种方式是递归方式。

• 二叉树

  每个节点上都不能多余有两个儿子的节点，二叉查找树，其深度的平均值是O（logN）。

  • 实现

    因为一个二叉树节点最多有两个子节点，我们可以保存直接链接到他们的链，树节点的声明类似于双链表的结构。

    • 中序遍历
    • 后序遍历（后缀表达式）
    • 先序遍历

  • 构造表达式的树

    通过栈的方式，如之前学习栈的时候所说的那样，每遇到操作数的时候，就进栈，遇见操作符的时候，就出栈，形成二叉树。

  • 查找树ADT——二叉查找树

    使用二叉查找树的性质是，左子树中所有的项小于X的值，右子树的所有项大于X的值，由于树的递归定义，通常是使用递归来操作这些例程。

    private static class BinaryNode<Type>{
        BinaryNode(Type element){
            this(element,null,null);
        }
        BinaryNode(Type element, BinaryNode<Type> left,BinaryNode<Type> right){
            this.element=element;
            this.left=left;
            this.right=right;
        }
        Type element;
        BinaryNode<Type> left;
        BinaryNode<Type> right;
    }
    

    • contains方法

      private boolean contains(Type x,BinaryNode<Type> t){
          if(t==null){
              return false;
          }
          int compareResult=x.compareTo(t.element);
          if(compareTo==-1){
              return contains(x,t.left);
          }
          else if(compareTo==1){
              return contains(x.t.right);
          }
            return true;
      }
      

    • insert方法

      注意，当对二叉查找树进行插入操作的时候，它总会插入到最后一个节点的位置上。

    • remove

      如果删除的次数不多，通常采用的方式是惰性删除。

      private BinaryNode<Type> remove(Type x , BinaryNode<Type> t){
          if(t==null){
              return t;
          }
          int compareResult=x.compareTo(t.element);
          if(compareResult<0){
              remove(x,t.left);
          }
          else if(compareResult>0){
              remove(x,t.right);
          }else if(r.right!=null&&r.left!=null){
                   t.element=findMin(t.right).element;
                  t.right=remove(t.element,t.right);
              }
          else{
                  t=(t.right==null)?t.left:t.right;
              }
          return t;
      }
      

  • AVL树

    AVL树是带有平衡条件的二叉查找树，这个平衡条件是它的深度必须是O（log（N）），一颗AVL树要求左子树和右子树的高度最多相差1。

    插入恢复二叉树的方式：

    • 单旋转
    • 双旋转

  • B树

    我们一直觉得可以把数据结构装进内存中去，但是，如果数据过多的话，我们就要把数据结构装进磁盘中去。

    宽松计算的话，一次磁盘访问的时间是，40万条指令。如果把磁盘访问时间缩小一半的话，运行速度也将提高一倍。

    ​ M阶的B树具有以下的特性：

    • 数据项存储在树叶上
    • 非叶节点存储直到M-1个关键字以指引搜索的方向。
    • 树的根或者一片树叶或者儿子树在2到M之间。
    • 除根节点，所有的非树叶节点的儿子树在（M/2）和M之间
    • 所有的树叶都在相同的深度上，并由L/2到L之间的数据项。