二叉树 练习和hash 基础知识

mood321 · mood321 · commit b6340949b12b · 2019-11-06T01:34:58.000+08:00
diff --git a/src/main/java/algorithm/basic04/Code_08_CompleteTreeNodeNumber.java b/src/main/java/algorithm/basic04/Code_08_CompleteTreeNodeNumber.java
@@ -0,0 +1,54 @@
+package algorithm.basic04;
+
+/**
+ * @Created by mood321
+ * @Date 2019/11/5 0005
+ * @Description TODO
+ */
+public class Code_08_CompleteTreeNodeNumber {
+    public  static class Node{
+        int data;
+        Node left;
+        Node right;
+        public Node(int data){
+            this.data=data;
+        }
+    }
+    public static int nodeNum(Node head) {
+        if(head==null){
+            return 0;
+        }
+        return bs(head,1,mostLealLeft(head,1));
+    }
+
+    private static int bs(Node head, int leavl, int h) {
+        if(leavl == h){
+            return 1;
+        }
+        if(h == mostLealLeft(head.right, leavl +1)){
+            return  (1<< (h-leavl)) +bs(head.right, leavl +1, h); // << 运算等级 很低
+        }else {
+            return (1<<(h -leavl -1)) +bs(head.left,leavl+1,h);
+
+        }
+    }
+
+    private static int mostLealLeft(Node head, int leal) {
+        while(head!=null){
+            leal++;
+            head=head.left;
+        }
+        return leal-1;
+
+    }
+    public static void main(String[] args) {
+        Node head = new Node(1);
+        head.left = new Node(2);
+        head.right = new Node(3);
+        head.left.left = new Node(4);
+        head.left.right = new Node(5);
+        head.right.left = new Node(6);
+        System.out.println(nodeNum(head));
+
+    }
+}
diff --git a/src/main/resources/note/Algorithm/算法学习基本数据结构和算法原型.md b/src/main/resources/note/Algorithm/算法学习基本数据结构和算法原型.md
@@ -72,5 +72,44 @@
         <p>1. 有右子节点 无左子树 一定不是
         <p>2. 有左子树 无右子树  接下来所有节点必须是叶子节点 才是完全二叉树
         <p> 注: 深度遍历用栈 广度用队列
-        
-###  
+   + 8 已知一棵完全二叉树，求其节点的个数
+      <p>要求：时间复杂度低于O(N)，N为这棵树的节点个数    
+      <p> 思路：1. 直接遍历  时间复杂度时O(n)
+      <p> 2. 满二叉树的节点个数是= (1<< 高度)-1   能把一个二叉树 拆分成左子树 和右子树，
+      <p> 在右子树的最左节点存在时 左子树一定是一个满二叉树 ，当最左节点高度比左子树小 右子树一定是一个 高度减1的满二叉树 O(Log N)^2
+      <p>   <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic04/Code_08_CompleteTreeNodeNumber.java">code</a>
+ 
+###  Hash 算法和散列表
+#### Hash 算法
+<p> Hash码 --由Hash算法(MD5、SHA 等) 计算出来的十六进制的数字
+
+##### 经典Hash函数性质：
+<p>1. 输入域是无穷大的
+<p>2. 输出是有范围的
+<p>3. 在输入一样时 输出是一样的
+<p>4. 在输入不一样是,输出也有可能一样（就是hash碰撞 1,2,3 会导致hash碰撞）
+<p>5. 在大量输入的时候,得到的相对应的值是均匀分布在 输出范围内的 叫离散型( 在实际应用中很重要的特性，如负载均衡，分片)
+
+##### Hash函数特性：
+<p>1. 输入和输出是没有关系的
+<p>2. 因为在输出域上均匀分布,得到推论: 一组数据得到的Hash码%m,在0~m-1上也是均匀分布的
+<p>3.Hash 码的每一位是相对独立的 彼此关系不大
+
+##### 应用
+<p>1.安全加密
+<p>2.唯一标识
+<p>3.数据校验
+<p>4.散列函数
+<p>5.负载均衡
+<p>6.数据分片
+<p>7.分布式存储
+
+#### Hash 表
+##### 经典Hash表实现 （java 实现在8中加入了红黑树）
+<p>1. 生成数组 得到大小len
+<p>2. put 时获取key的hashcode  然后 %len 得到他属于数组的位置
+<p>3. 数组里面存链表,检查对应位置 下是否有当前key的节点，有更新，无，链在链表后面
+<p>4. 如果链表长度到达 阈值，因为hash算法的特性 均匀分布，所以数组其他其他位置类似，此时扩容
+<p>5. 扩容 重新调整数组大小，从新hash，分配（在java中 扩容是<<1 所以实际只有一半需要从新分配 具体可以看HashMap的笔记）
+<p> 离线扩容: 在离线时扩容, 扩容完成替换 
+  
