博客首页 » Arch Java数据结构与算法 - 二叉树
发布于 23 Jul 2015 15:49
标签 blog
有序数组查找数据快，但是插入慢；链表插入快，但是查找慢。二叉树查找等同于有序数组，插入效率等同于链表。
二叉树的查找
沿着路径查找
前序 左节点优先
中序
后序
二叉树的插入
沿着路径查找，然后再末端插入
二叉树的删除
没有子节点的删除
直接删除
有一个子节点的删除
把子节点以及附带子树挪上来到被删除节点的位置
有两个子节点的删除
节点后继，是右子树中键值最小的节点。
评论：同理节点前继，是左子树中键值最大的节点。
先走到右子节点，
如果当前节点没有左子节点，当前节点是后继
如果还有左子节点，则重复寻找
在数大的一边，走一步，然后反向去找没有子节点的方向。
效率
查找 O(logN)
插入 O(logN)
删除 O(logN)
用数组代表二叉树
所有没有值的地方填Null
左子节点 2 * index + 1
右子节点 2 * index + 2
父节点 (index - 1） / 2
如果不再平衡，则每个元素位置固定。
如果有重复值的话，有问题，只有第一个能被查到。
评论：由于是数组，所以构建快，但是扩展性差，做再平衡慢。如果是排序的数组，自然就形成一个平衡二叉树。如果试图保存非平衡二叉树，则会有大量空值。
哈夫曼编码
频次多的信息，用少的bit表达，逐渐添加bit，用长的bit表达低频信息。
是一颗非平衡二叉树树，每一个分支表达0/1，每一个叶节点表达一个具体的信息如字母。每一个分支都是子树合计频次的比较。
评论：哈夫曼编码简单，但是具体信息是简单的元素(固定长)，信息的熵与编码结果的长度匹配得不均匀。所以压缩效率不如字典和滑动窗。
创建
把所有信息作为叶节点放入基于频次的优先级队列。
从优先级队列中删掉两个最低频节点。给这两个节点添加一个合计父节点，形成一个子树，其中父节点的信息字段为空。把子树的这个新的父节点添加回优先级队列。
编码
到达每一个叶节点的路径就是哈夫曼编码。遍历树，形成一个码表。
本页面的文字允许在知识共享 署名-相同方式共享 3.0协议和GNU自由文档许可证下修改和再使用，仅有一个特殊要求，请用链接方式注明文章引用出处及作者。请协助维护作者合法权益。
系列文章
文章列表
- Arch Java数据结构与算法 - 二叉树
这篇文章对你有帮助吗，投个票吧？
留下你的评论