文档章节

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

刘军兴
 刘军兴
发布于 2012/03/16 10:08
字数 1279
阅读 297
收藏 0

为学习 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 树。

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 55
博文 185
码字总数 227015
作品 0
昌平
私信 提问
加载中

评论(2)

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

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

天方夜
10/30
0
0
Java Binary Search Tree

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

秋风醉了
2015/06/30
0
0
[译文] 初学者应该了解的数据结构: Tree

原文链接:Tree Data Structures for Beginners 众成翻译地址:初学者应该了解的数据结构: Tree 系列文章,建议不了解树的同学慢慢阅读一下这篇文章,希望对你有所帮助~至于系列的最后一篇自...

sea_ljf
08/11
0
0
Leetcode——二叉树常考算法整理

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

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

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

HenrySun
2016/08/06
15
0

没有更多内容

加载失败,请刷新页面

加载更多

springboot中filter的用法

一、在spring的应用中我们存在两种过滤的用法,一种是拦截器、另外一种当然是过滤器。我们这里介绍过滤器在springboot的用法,在springmvc中的用法基本上一样,只是配置上面有点区别。 二、f...

xiaomin0322
2分钟前
0
0
java项目修改了更换了jdk版本报错进行修改

java项目原来用的是1.8版本的,改成1.7版本后,项目会报错,要进行的修改是 然后是clean一下项目,然后是选中项目的buildpath,然后是configurebuildpath,然后是看jdk是否进行修改...

myAll_myAll
14分钟前
0
0
Gartner 2018 数据库系列报告发布 巨杉数据库连续两年入选

近期,Gartner陆续发布了2018年的数据库系列报告,包括《数据库魔力象限》《数据库核心能力》以及《数据库推荐报告》。其中,SequoiaDB巨杉数据库作为业界领先的金融级分布式交易型数据库产品...

巨杉数据库
16分钟前
0
0
Navicat闲置一段时间卡死问题的解决

先关闭连接,再右键点击所需要设置的链接,进入编辑连接,进入高级项,勾选保持连续间隔(秒):时间设置短一些,比如30秒,完成!!

joyStalker
16分钟前
0
0
理解Java中的弱引用(Weak Reference)

1. What——什么是弱引用? Java中的弱引用具体指的是java.lang.ref.WeakReference<T>类,我们首先来看一下官方文档对它做的说明: 弱引用对象的存在不会阻止它所指向的对象变被垃圾回收器回...

绝地逢生
17分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部