文档章节

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

刘军兴
 刘军兴
发布于 2012/03/16 10:08
字数 1279
阅读 296
收藏 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 树。

© 著作权归作者所有

共有 人打赏支持
刘军兴
粉丝 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
[译文] 初学者应该了解的数据结构: 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

没有更多内容

加载失败,请刷新页面

加载更多

Redis应用之分布式锁(set)

Redis应用之分布式锁(set) 在单机应用的场景下,我们常使用的锁主要是synchronized与Lock;但是在分布式横行的大环境下,显然仅仅这两种锁已经无法满足我们的需求; 需求:秒杀场景下,有若干...

GMarshal
30分钟前
1
0
python实现简单的文件加密与解密

对于任意的一个文件,本质上来讲都是二进制的。 对于任意一个二进制数a,对其用另外任意一个与a的位数相同的二进制数m进行“异或”操作得到结果e,即e=a xor m; 如果再讲上面得到的e用m进行...

Aomo
32分钟前
1
0
Android开发应用程序生成以太坊钱包

Android应用程序以太坊钱包生成,要做的工作不少,不过如果我们一步一步来应该也比较清楚: 1.在app/build.gradle中集成以下依赖项: compile ('org.web3j:core-android:2.2.1') web3j核心是...

geek12345
47分钟前
1
0
ArrayList嘿嘿嘿

数组扩容技术: //扩容技术 将原数组objs类容复制到新数组并且长度为11 Object[] newObjs = Arrays.copyOf(objs,11); 数组比较大那么System.arraycopy比较有优势,因为其使用的是内存复制,省...

熊猫你好
今天
2
0
Android平台下的一个好用的日历库(sxtwl_cpp),支持农历转公历,和公历转农历等功能

python版的sxtwl_cpp传送入口 在build.gradle的allprojects中加入 maven { url 'https://dl.bintray.com/yuangu/sxtwl' } 最终如下面代码所示: allprojects { repositories { ......

元谷
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部