算法自学笔记二分查找树
我们之前讲二叉堆的时候使用较不直观的方式实现树的数据结构:使用一个数组保存各节点,索引为k节点父节点为k/2,子节点为k * 2, k * 2 1
这一次,我们使用直观方式实现树结构:构造实际的节点类。类似于链表里的节点,不过每一个节点指向两个节点:left和right
private Class Node {
private Value value;
private Key key;
// Value and Key are generic variables for symbol tables
private Node left;
private Node right;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
}
}
每一个节点都是一个子树的根,而整个树的初始节点叫根节点
二叉堆里每一个节点的值都大于它的两个子节点。而对于二分查找树,其左子节点小于该节点值,而右子节点大于该节点。
在二分查找树里搜索一个值:
从根节点出发,如果这个值大于当前节点则查找其右子节点,如果小于当前节点则查找其左子节点。重复进行此操作,直到找到对应值,或者得到的节点为null,说明已经到达树底端,不存在该值
在二分查找树里插入一个值:
从根节点出发,如果这个值大于当前节点则查找其右子节点,如果小于当前节点则查找其左子节点。(和搜索一模一样的操作)重复进行此操作,直到找到一个节点的子节点为null,把该节点子节点设为要插入的值。
搜索和插入操作需要的比较次数均为:树高度 1
使用二叉树实现符号表put方法:
public void put(Key key, Value value) {
root = put(key, value, root);
}
private Node put(Key key, Value, value, Node x) {
if (x == null) {
return new Node(key, value);
} else {
if (x.value.compareTo(value) > 0) {
x.left = put(key, value, x.left); // move to the left
} else if (x.value.compareTo(value) < 0) {
x.right = put(key, value, x.right); // move to the right
} else {
x.value = value; // replace the original value
}
}
return x;
}
递归修改二叉树符号表需要 1 树高度 次查找
二叉树操作需要的查找次数和树的构型有关,最优情况下,树是完全平衡的,也就是说每一个节点都正好有两个子节点。一般情况下部分节点有两个子节点,部分节点只有一个。而最糟情况,如果输入数据为升序或降序排列,所有节点只有一个子节点,此时二叉树效率将和链表相当。
二叉树的构造原理和快速排序一样。每一个节点对应快速排序一个基准值。因此我们可以使用描述快速排序时间复杂度的方式一样解决二叉树。
对于一个二叉树,插入N个元素需要时间为2lnN,最糟情况为N
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggcgf
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13