基于数组可根据下标随机访问的特性 通过一个hash函数将key转化为下标,获得数据

• 计算出的hash值得是非负整数
• key相同hash值也相同,key不同hash值也得不同

• 开放寻址法:hash冲突后向后依次寻找空闲位置
• 拉链法:hash冲突后将冲突的value连成链表

链表是特殊情况的树;树是特殊情况的图

递归编码

• 前序:根左右
• 中序:左根右
• 后序:左右根

• 左子树的节点均小于根
• 右子树的节点均大于根
• 左右子树也是二叉搜索树
• 空树也是二叉搜索树
• 二叉搜索树的中序遍历就是升序遍历

可以快速(O(1)时间复杂度)内找到最大或最小值 增加或删除元素可能需要重新排序

• 完全二叉树(叶子节点那层可能不满)实现
• 树中任意节点值>=子节点值
• 通过数组实现
• 索引i的左孩子索引为(2 * i + 1)
• 索引i的右孩子索引为(2 * i + 2)
• 索引i的父索引为floor(( i- 1) / 2)
• 插入:直接插入数组尾部,之后与父节点比较大小,比父节点大交换位置外(heapifyUp)

• 度:边有向时入度出度,进去和出去的变的个数
• 点与点是否相连

• 有向 无向
• 权重:边是否有长度