文档章节

学习数据结构 二叉查找树(binary search tree)

刘军兴
 刘军兴
发布于 2012/03/16 10:08
字数 1279
阅读 295
收藏 0
点赞 0
评论 2

为学习 LLVM 的 ImmutableSet,其底层的实现选择为 AVL 树(平衡二叉搜索树),我不很熟悉该树,虽然大致知道但毕竟不精,因此还是先学习学习二叉搜索树吧。

二叉搜索树或叫做二叉查找树,可以用于实现Dictionary辞典,辞典是K,V 键值的对的集合。一般 Dictionary 不含重复的 K。一个 Dictionary 的抽象数据类型规范可定义为:

interface Dictionary<K extends Comparable<K>, V> {
	// 当且仅当辞典为空的时候返回真。
	public boolean isEmpty();
	// 如果存在键值为 k 的 <K,V> 对,则返回它们。 
	public Entry<K, V> get(K k); 
	// 插入给出的 k,v 对,如果键值已经存在则更新相关元素 v。
	public void insert(K k, V v);
	// 删除特定键值的 k,v 对。
	public void remove(K k);
}

二叉查找树的定义有4条,参见书即可。我们最需关注的是在二叉查找树中位于左子树的键小于根的键,右子树的键大于根的键。下面具体学习如何实现 isEmpty, get, insert, remove 等方法。

假设节点与树的结构如下(方法实现在 BSTree 类中):

// 表示一个树节点。
class TreeNode<K, V> {
	TreeNode left;  // 左子树
	TreeNode right; // 右子树
	K key;	       // 键
	V value;        // 元素值
}

// 表示一个二叉查找树。
class BSTree<K, V> implements Dictionary {
	TreeNode<K, V> root;  // 根节点。
}

方法 isEmpty 比较简单,判断 root 是否为空即可。不用多探讨了。

方法 get 如下:

 

// 在 BSTree 类中.
  public TreeNode get(K k) {
    if (this.root == null) return null; // 没有任何节点
    return this.root.find(k);
  }

  // 在 TreeNode 类中。
  public TreeNode find(K k) {
    TreeNode<K, V> node = this;
    while (node != null) {
      int c = k.compareTo(node.getKey());
      if (c < 0) 
        node = node.getLeft();	// 查找左子树。
       else if (c > 0)
        node = node.getRight();	// 查找右子树。
       else
      return node;	// 找到了。(c == 0)
    }
    return null;	// 没有找到。
  }

在这里使用了二叉查找树的核心性质,根据 compare 结果,如果 k 小于当前节点的键则查找左子树,大于则查找右子树,如果相等则就是自己。也可以使用递归方法写查找,但是效率上可能不如这样写好。

insert 方法实现如下:

public void insert(K k, V v) {
    if (k == null) throw new NullPointerException("k");
    TreeNode<K, V> new_node = new TreeNode<K, V>(k, v);
    if (this.root == null) {
      // 特殊情况,没有任何节点的时候。
      this.root = new_node;
      return;
    }
    
    // 在树中搜索 k 的节点 p, pp 表示 p 的父节点。
    TreeNode<K, V> p = this.root, pp = null;
    while (p != null) {
      pp = p;    // 如果 p 走向了子节点,则 pp 恰好是 p 的父节点。
      int c = k.compareTo(p.getKey());
      if (c < 0)   // 走向左节点。
        p = p.getLeft();
      else if (c > 0)    // 走向右节点。
        p = p.getRight();
      else {    // p 的 key 就是 k,找到同键值的,则更新 v 返回。
        p.setValue(v);
        return;
      }
    }
    
    // 如果走到这里,则 p == null, pp 是前一个节点,新的节点应插入到 pp 下面(左、右取决于键值的比较)
    if (k.compareTo(pp.getKey()) < 0)  // k < pp.key 表示应插入到 pp 的左子树
      pp.left = new_node;
    else
      pp.right = new_node;
  }

 remove 实现如下:

private TreeNode<K, V> internal_remove(K k) {
    if (this.root == null) return null;    // 没有任何节点的特殊情况。
    TreeNode<K, V> p = this.root, pp = null;
    
    // 查找要删除的键值为 k 的节点 p,以及其父节点 pp。
    // 如果 pp 为 null 表示 p 是根节点 root。
    while (p != null) {
      int c = k.compareTo(p.getKey());
      if (c == 0) break;
      pp = p;
      p = (c < 0) ? p.left : p.right;
    }
    if (p == null) return null;     // 没有找到要删除的元素。
    
    // 现在 p 是要删除的节点,pp 是其父节点(可能为 null)。
    if (p.left == null || p.right == null) {
      // 这里 p 至多只有一个子树,则就用这一个子树替代 p 即可。
      set_pp_child(pp, p, p.left != null ? p.left : p.right);
    } else {
      // p 有两个子树。可以用 left.max or right.min 来替代 p。我们选用右边的最左子树(min)。
      TreeNode<K, V> pR = p.right;
      if (pR.left == null) {
        // 右边的子树没有左分支,则用 p_right 替代 p 即可。
        pR.left = p.left;
        set_pp_child(pp, p, pR);
        return p;
      }
      
      // p 的右子树 pR 有左子树,则从中删除最左的节点 -- rmin。
      TreeNode<K, V> rmin = internal_remove_rmin(pR);
      rmin.left = p.left;    // 用 rmin 替代 p,因此设置 rmin.left, .right
      rmin.right = pR;
      set_pp_child(pp, p, rmin);
    }
    return p;
  }
  
  
  // 移除指定节点的最小子节点(pR.min),也即最左子节点。
  private TreeNode<K, V> internal_remove_rmin(TreeNode<K, V> pR) {
    if (pR.left == null) throw new java.lang.RuntimeException("pR.left is null");
    
    TreeNode<K, V> rmin = pR.left, rmin_pp = pR;  // rmin_pp 是 rMin 的父节点。
    while (rmin.left != null) {
      rmin_pp = rmin;
      rmin = rmin.left;    // 向左走到最左子节点,其就是 pR.min。
    }
    
    // 现在 rmin = pR.min, rmin_pp = rmin.parent。
    assert (rmin.left == null);    // 现在 rmin 必然没有左子树了。
    rmin_pp.left = rmin.right;
    rmin.right = null;
    return rmin;
  }
  
  private void set_pp_child(TreeNode<K, V> pp, TreeNode<K, V> p, TreeNode<K, V> child) {
    if (pp == null)
      this.root = child;    // 删除的就是根,设置根为 child
    else if (pp.left == p)
      pp.left = child;    // p 是 pp 的左子树,替代为 child
    else 
      pp.right = child;    // p 是 pp 的右子树,替代为 child
  }

remove 方法的实现显得笨拙一些。

为了方便研究 binary search tree,我编写了一个 java 小程序,位于这里:http://vdisk.weibo.com/s/3dT-U/1331863473

该程序可以通过输入命令 find, insert, delete, dump 等构造和查看二叉查找树。帮助为 help, 退出为 exit。

下一步准备在二叉查找树的基础上实现/学习 AVL 树。

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 54
博文 184
码字总数 226359
作品 0
昌平
加载中

评论(2)

刘军兴
刘军兴
太好了,谢谢。希望一起共同学习。
土卫十六
土卫十六
我在书上看到说,AVL与红黑树有一样的性能,但某些极特殊的情况下AVL仍保持性能,而红黑树不行。果然LLVM 也选择了AVL。过几天我把我的AVL C++代码贴出,包括删除操作,呵呵。
二叉搜索树的简明实现(ES5 & ES6)

二叉树 & 二叉搜索树 二叉树(Binary Tree)是 n(n >= 0)个节点的有限集合,集合为空集时,叫作空二叉树;不为空时,由根节点及左子树、右子树组成,左子树、右子树也都是二叉树。 从这个描...

天方夜
07/04
0
0
Java Binary Search Tree

Java实现二叉查找树(Binary Search Tree) 对数:(底数β的值一定不能是1或0) 数x(对于底数β)的对数通常写为: 最常用做底数的是e、10和2 如果底数是10,简写成 lg,如果底数是e,简写...

秋风醉了
2015/06/30
0
0
Leetcode——二叉树常考算法整理

二叉树常考算法整理 希望通过写下来自己学习历程的方式帮助自己加深对知识的理解,也帮助其他人更好地学习,少走弯路。也欢迎大家来给我的Github的Leetcode算法项目点star呀~~ 前言 二叉树即...

qq_32690999
05/28
0
0
4 张 GIF 图帮助你理解二叉树搜索算法

二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树: 任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 任意节点的右子树不空,...

HenrySun
2016/08/06
15
0
leetcode算法题解(Java版)-12-中序遍历

日子又恢复正常了,浪了半个月。。。 还是学习的时候感觉好~~ 一、动态规划 题目描述 Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For e...

kissjz
05/18
0
0
深入学习二叉树(四) 二叉排序树

1 前言 数据结构中,线性表分为无序线性表和有序线性表。 无序线性表的数据是杂乱无序的,所以在插入和删除时,没有什么必须遵守的规则,可以插入在数据尾部或者删除在数据尾部。但是在查找的...

进击的Hello_World
05/14
0
0
数据结构MOOC|二叉搜索树BST

课程内容来自:http://www.icourse163.org/learn/ZJU-93001?tid=1002654021#/learn/content?type=detail&id=1003620986 二叉搜索树(BST,Binary Search Tree) 也称二叉排序树或二叉查找树,......

darlingwood2013
05/30
0
0
前端面试中的常见的算法问题

0. 前言 重要:如果文章内部有图片无法显示,请移步简书 查看。 今天在刷文章的时候,突然看到了一篇专门分享前端面试算法的文章。 趁着现在有时间,赶紧和大家分享一波。 下面直接开始正文。...

mr_lp
2016/12/23
0
0
【6】判断整数序列是不是二元查找树的后序遍历结果

/* 判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、...

SibylY
2016/07/31
10
0
4 张 GIF 图帮助你理解二叉查找树

二叉查找树(Binary Search Tree),也称二叉搜索树,是指一棵空树或者具有下列性质的二叉树: 1.任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 2.任意节点的右子树不...

桃子红了呐
2017/02/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

回想过往,分析当下,着眼未来

好久没有真正的在纸质笔记本上写过东西了,感觉都快不会写字了,笔画都不知道怎么写了。接下来就说说咱们的正事。 2018年7月22日,我做了一个决定,那就是去参加安全培训(可能是我职业生涯中...

yeahlife
38分钟前
1
0
关于工作中的人际交往

关于工作中的人际交往 Intro 写了篇发泄情绪的博客,但不会发布出来。 大概就是,要么忍,要么滚。 以及一些不那么符合社会主义核心价值观,不满于大资本家与小资本家剥削的废话。

uniqptr
43分钟前
0
0
springMVC的流程

1.用户发送请求至前端控制器DispatcherServlet 2.DispatcherServlet收到请求调用HandlerMapping处理器映射器。 3.处理器映射器根据请求url找到具体的处理器,生成处理器对象及处理器拦截器(...

JavaSon712
59分钟前
0
0
大数据教程(3.2):Linux系统软件安装之自动化脚本

博主前面文章有介绍过软件的安装,可以帮助IT人员顺利的完成功能软件安装;但是,对于我们运维人员或者需要管理软件安装的项目经理来说,有些应用一次行需要搭建很多台相同的软件环境(如tom...

em_aaron
今天
0
1
Spring Boot 2.0.3 JDBC整合Oracle 12

整合步骤 1. Oracle驱动引入 Oracle驱动一般不能通过maven仓库直接下载得到,需自行下载并导入到项目的lib目录下,建议通过如下pom依赖引入下载的Oracle驱动 <!-- Oracle 驱动 -->...

OSC_fly
今天
0
0
java 8 并行流 - 1

下面创建一个并行流,与顺序流 //顺序流Stream.iterate(0L, i -> i + 1) .limit(Integer.MAX_VALUE) .reduce(0L, Long::sum);//并行流Stream.iterate(0L, i -> i......

Canaan_
今天
0
0
数据结构与算法5

二分法采用向下取整的方法 使用有序数组的好处是查找的速度比无序数组快的多,不好的方面是因为要将所有靠后的数据移开,所以速度较慢,有序数组和无序数组的删除操作都很慢。 有序数组在查找...

沉迷于编程的小菜菜
昨天
1
1
SpringBoot | 第十一章:Redis的集成和简单使用

前言 上几节讲了利用Mybatis-Plus这个第三方的ORM框架进行数据库访问,在实际工作中,在存储一些非结构化或者缓存一些临时数据及热点数据时,一般上都会用上mongodb和redis进行这方面的需求。...

oKong
昨天
5
0
对基于深度神经网络的Auto Encoder用于异常检测的一些思考

一、前言 现实中,大部分数据都是无标签的,人和动物多数情况下都是通过无监督学习获取概念,故而无监督学习拥有广阔的业务场景。举几个场景:网络流量是正常流量还是攻击流量、视频中的人的...

冷血狂魔
昨天
0
0
并发设计之A系统调用B系统

A-->B A在发送请求之前,用乐观锁,减少对B的重复调用,这样一定程度上是幂等性。 比如A系统支付功能,要调用B系统进行支付操作,但是前端对"支付"按钮不进行控制,即用户会不断多次点击支付...

汉斯-冯-拉特
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部