文档章节

二叉搜索树

pp__qq
 pp__qq
发布于 2015/02/26 00:00
字数 779
阅读 26
收藏 0
点赞 0
评论 0

性质

  • 二叉搜索树;对于树中的每一个节点 x,x 的左子树所有节点的 key 不大于 x.key;x 的右子树的 key 不小于 x.key;如果按照 std::multimap 使用的 Compare 规则来解释,则若 x 的左子树的 key 均在 x.key 之前或之上;x 的右子树的 key 均在 x.key 之上(即位置相同)或者之后.

时间复杂度

  • 树的高度 h 与节点个数 n 的关系;h∈[lgn(以2为底),n],这个很好推的.

  • 遍历操作;Θ(n)

  • 查找;前驱;后继,等其他操作;与 h 成正比,即 Θ(h).

操作算法

  • 查找;最小值,最大值;找前驱,后继;这类不会修改二叉搜索树结构的操作算法,可以参考 libstdcxx/include/bits/stl_tree.h 中实现的红黑树.

// 变量说明;
T;表示一颗二叉搜索树,
    T.root;指针,指向着二叉搜索树的根节点.
节点;
    key;节点的键;
    parent,left,right;指针,指向着节点的父节点,孩子节点;若节点没有父节点,或者孩子节点,则置为0.
使用 < 来确定键值的先后关系;

插入

// z;指针;指向着待插入的节点.其中 z->key 为节点的键;z->parent,left,right 为 0.
insert(T,z)
    y = 0;
    x = T.root;
    insert_left = true; // 若为真,则表明 z 应该插入在 y 的左子树上.

    // 确定 z 的插入位置.
    while(x != 0)
        y = x;
        insert_left = z->key < x->key;
        x = insert_left ? x->left : x->right;
    // 当循环结束时,x==0,y 指向着 z 的父节点,而 insert_left 表明了插入位置.

    // 在 z 与 y 之间建立联系.    
    z->parent = y;
    if( y == 0)
        T.root = z;
    else
        if (insert_left)
            y->left = z;
        else
            y->right = z;

删除

  • 删除,可以分为4种情况来分别对待(见上图),可以从中序遍历的结果来理解,以(c)情况为例;在删除z之前,中序遍历的结果是"l左子树;l;l右子树;z;y;x左子树;x;x右子树";所以在删除 z 之后,中序遍历的结果应该是"l左子树;l;l右子树;y;x左子树;x;x右子树",也即需要对二叉搜索树做一些调整,使得调整后中序遍历结果为"l左子树;l;l右子树;y;x左子树;x;x右子树";具体调整过程见(c)左图--->右图结构.

// u,v;指针,指向着 T 中的某一节点,其中 v 可以为0.
// 该函数在 v 与 u 的父节点之间建立连接,即让 v 替代 u 成为 u 父节点的孩子节点.
traslate(T,u,v){
    up = u->parent;
    
    // up ---> v;
    if(up == 0)
        T.root = v;
    else if(up->left == u)
        up->left = v;
    else
        up->right = v;
    
    // v ---> up;
    if(v!=0)
        v->parent = up;

    // 此时;up <---> v;
}

// z;指针;指向着待删除的节点.
erase(T,z){
    // 情况 b;
    if(z->right == 0)
        translate(T,z,z->left);
    
    // 情况 a;
    else if(z->left == 0)
        translate(T,z,z->right);

    else
        y = 后继(z);
        // 情况 d 
        if(y->parent != z)
            translate(T,y,y->right);
            y->right = z->right;
            z->right->parent = y;
            // 此时情况 d 转化为 情况 c;
        // 情况 c;
        y->left = z->left;
        z->left->parent = y;
        translate(T,z,y);
}




© 著作权归作者所有

共有 人打赏支持
pp__qq
粉丝 17
博文 51
码字总数 97223
作品 0
合肥
程序员
数据结构-二叉搜索树的实现

定义 二叉搜索树(Binary Search Tree,BST),也称为二叉排序树或二叉查找树。 相较于普通的二叉树,非空的二叉搜索树有如下性质: 非空左子树的所有键值小于其根结点的键值; 非空右子树的所有...

IAM四十二 ⋅ 2017/10/27 ⋅ 0

B树文件系统树

二叉排序树或者二叉搜索树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其...

满小茂 ⋅ 2016/01/09 ⋅ 0

javascript算法之二叉搜索树

什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否...

光哥很霸气 ⋅ 2017/09/11 ⋅ 0

4 张 GIF 图帮助你理解二叉树搜索算法

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

HenrySun ⋅ 2016/08/06 ⋅ 0

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

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

刘军兴 ⋅ 2012/03/16 ⋅ 2

二叉搜索树的删,查,插(递归&非递归)

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

triorwy ⋅ 02/27 ⋅ 0

JavaScript 二叉搜索树以及实现翻转二叉树

本文包括:二叉搜索树(创建、遍历、搜索、插入等)、JavaScript 实现翻转二叉树 欢迎关注我的:个人博客、Github。 什么是二叉树? 二叉树的定义:二叉树的每个结点至多只有二棵子树(不存在...

CaiJinyc ⋅ 06/10 ⋅ 0

4 张 GIF 图帮助你理解二叉查找树

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

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

Java Binary Search Tree

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

秋风醉了 ⋅ 2015/06/30 ⋅ 0

平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134 ⋅ 2017/06/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 18分钟前 ⋅ 0

VS2015配置并运行汇编(一步一步照图做)【vs2017的链接在最后】

前言 我是上学期学的汇编,因为有vs又不想用课上教的麻烦的dosbox以及masm32,但是一直没找到高亮插件和能调试的(难在运行不了而找不到答案上,出现的错误在最后放出,还请先达们不吝指点)...

simpower ⋅ 27分钟前 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 30分钟前 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 37分钟前 ⋅ 0

你真的明白RPC 吗?一起来探究 RPC 的实质

你真的明白RPC 吗?一起来探究 RPC 的实质 不论你是科班出身还是半路转行,这么优秀的你一定上过小学语文,那么对扩句和缩句你一定不陌生。缩句就是去除各种修饰提炼出一句话的核心,而不失基...

AI9o後 ⋅ 39分钟前 ⋅ 0

z-index设置失效?

今天碰到了一个问题,就是在给li设置提示框的时候,有用到遮罩效果,本来想把对应的出现在最顶层,可是不管将li设置的z-index值设为多大,li都没有出现在遮罩层之上。 我在网上查了z-index设...

IrisHunag ⋅ 46分钟前 ⋅ 0

CyclicBarrier、CountDownLatch以及Semaphore使用及其原理分析

CyclicBarrier、CountDownLatch以及Semaphore是Java并发包中几个常用的并发组件,这几个组件特点是功能相识很容易混淆。首先我们分别介绍这几个组件的功能然后再通过实例分析和源码分析其中设...

申文波 ⋅ 50分钟前 ⋅ 0

Java对象的序列化与反序列化

Java对象的序列化与反序列化

Cobbage ⋅ 今天 ⋅ 0

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 今天 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部