精华内容
下载资源
问答
  • 关键字序列1,2,3,4,5构造而得的二叉排序树 ASL=(1,2,3,4,5)/5=3 按关键字3,1,2,5,4构造而得的二叉排序树 ASL=(1+2+2+3+3)/5=2.2 很明显第二种序列的ASL要快。至于二叉排序树怎么构成的其实就是根据它的性质(若...

    打算就说说标题的方法,和介绍一下查找成功和非成功二叉树中结点的方法

    关键字序列1,2,3,4,5构造而得的二叉排序树

    这里写图片描述

    ASL=(1,2,3,4,5)/5=3

    按关键字3,1,2,5,4构造而得的二叉排序树

    这里写图片描述

    ASL=(1+2+2+3+3)/5=2.2

    很明显第二种序列的ASL要快。至于二叉排序树怎么构成的其实就是根据它的性质(若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值,若它的右子树不空,则右子树上的所有结点的值均大于它的根结点的值)

    ASL怎么求

    分别分为成功和非成功的情况

    成功

    每个结点的深度相加除以结点个数

    非成功

    我拿个书上的例子把
    这里写图片描述

    首先,先补全二叉树,可以看到有12个非成功的结点,这里我假设每个非成功查找结点概率相同,然后深度为3的非成功结点有4个,深度为4的非成功结点有8个。所以是3*4+4*8

    所以该图非成功的ASL=(3*4+4*8)/12

    展开全文
  • 文章目录二叉排序树1.... 平衡二叉排序树 二叉排序树 1. 二叉排序树 二叉排序树的检索 def bt_search(btree, key): bt = btree: while bt: if key < bt.val: bt = bt.left elif key > bt.val: ...

    二叉排序树

    1. 二叉排序树

    二叉排序树的检索

    def bt_search(btree, key):
        bt = btree:
        while bt:
            if key < bt.val:
                bt = bt.left
            elif key > bt.val:
                bt = bt.right
            else:
                return bt.val
        
        return None
    

    二叉排序树数据插入
    思路:

    • 若树为空,直接新建结点
    • 若树不为空:
      • 应该向左走而左结点为空,插入;
      • 应该向右走而右结点为空,插入;
      • 覆盖原有结点
    def bt_insert(btree, key):
        if btree is None:
            return TreeNode(key)
        bt = btree
        while True:
            if key < bt.val:
                if bt.letf is None:
                    bt.left = TreeNode(key)
                    return btree
                bt = bt.left
            elif key > bt.val:
                if bt.right is None:
                    bt.right = Tree.Node(key)
                    return btree
                bt = bt.right
            else:
                bt.val = key
                return btree
    

    二叉排序树数据删除
    思路:

    • 找到待删除数值和它的父节点在树中的位置
    • 若子结点的左子树为空,则直接将子节点的右子树挂到父节点,此处有3种情况
      • 父节点为空(子节点为根节点),则直接将根节点设为子节点的右子树
      • 子节点是父节点的左结点,则将子节点的右子树挂到父节点的左结点
      • 子节点是父节点的右结点,则将子节点的右子树挂到父节点的右结点
    • 若子节点的左子树不为空,先找到左子树的最右结点,并将子节点的右子树挂到最右结点的右结点上,后续同样有三种情况
      • 父节点为空(子节点为根节点),则直接将根节点设为子节点的左子树
      • 子节点是父节点的左结点,则将子节点的左子树挂到父节点的左结点
      • 子节点是父节点的右结点,则将子节点的左子树挂到父节点的右结点

    def delete(btree, key):
        bt = btree
        father, child = None, btree
        while child and child.val != key:
            father = child
            if key < child.val:
                child = child.left
            elif key > child.val:
                child = child.right
        if child is None:
            return 
        
        # 子节点左子树为空
        if child.left is None:
            if father is None:
                btree = child.right
            elif child is father.left:
                father.left = child.right
            else:
                father.right = child.right
            return btree
    
        # 子节点左子树不为空
        most_right = child.left
        while most_right.right:
            most_right = most_right.right
        
        most_right.right = child.right
        if father is None:
            btree = child.left
        elif child is father.left:
            father.left = child.left
        else:
            father.right = child.left
        return btree
    

    2. 平衡二叉排序树

    记结点左子树和右子树的高度差为平衡因子(Balance Factor),平衡因子的取值为-1,0,1.

    • 如果数据插入位置到根节点途径上每一个结点的BF都为0,那么新插入的结点不会影响导致树失衡,此时只需更新途径上结点的BF值即可.
    • 如果途径上结点BF值不全为0,则可以从插入节点位置沿着途径向上查找,找到第一个BF值不为0的结点,以该节点为根节点的树称为最小非平衡子树,后续的调整都在最小非平衡子树上进行. 记最小非平衡子树的根节点为a, 有左右两棵子树,BF都为0,但两棵树高度差1
      • 如果数据插入较低子树,则a的高度不变,且BF变为0.只需调整插入位置到a路径上结点的BF值即可,其他结点的BF值不变
      • 如果数据插入较高子树,则要调整高子树一部分数据到低子树中,以平衡高度.
        • LL型调整,a左子树较高,新节点插入到左子树的左子树
        • LR型调整,a左子树较高,新节点插入到左子树的右子树
        • RR型调整,a右子树较高,新节点插入到右子树的左子树
        • LL型调整,a右子树较高,新节点插入到左子树的左子树

    LL调整

    (1) 插入结点前,中序遍历的序列为 AbBaCA b B a C
    (2) 插入结点后,导致结点a的BF变为2,不满足平衡二叉树的要求
    (3) 要保持中序遍历的顺序不变,AbBaCA^{\prime} b B a C,将b作为最小非平衡子树的根节点,AA^{\prime}为左子树,BaCBaC为右子树,即可达到平衡.

    给树节点增加一个BF属性:

    class TreeNode():
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
            self.bf = 0
    

    LL调整python实现:

    def LL(a, b):
        a.left = b.right
        b.right = a
    
        a.bf = 0
        b.bf = 0
        return b
    

    RR调整
    RR调整与LL调整类似:

    def RR(a, b):
        a.right = b.left
        b.left = a
    
        a.bf = 0
        b.bf = 0
        return b
    

    LR调整

    (1) 记根节点a左子树的右子树的根节点为c.由于a是最小非平衡子树的跟,所以b,c的bf都为0,以a为根的中序遍历序列是AbBcCaDAbBcCaD
    (2) 新节点可能插入c的左子树(B)或右子树©,插入后b结点的BF=-1, a结点的BF为2,失衡!
    (3) 将c提升为最小非平衡子树的根节点,左右结点分别为b,a,如图所示,中序遍历的结果为AbBcCaDAbB^{\prime}cCaDAbBcCaDAbBcC^{\prime}aD,保持不变,且c结点BF变为0,b和a结点的BF为-1,0或者1,取决于新节点位置.

    def LR(a,b):
        c = b.right
        b.right = c.left
        c.left = b
        a.left = c.right
        c.right = a
    
        # 以下情况是失衡后二叉树的情况
        if c.bf == 0:# c本身为插入节点
            a.bf = b.bf = 0
        elif c.bf == 1: # 新节点在左子树
            b.bf = 0
            a.bf = -1
        else:   # 新节点在右子树
            b.bf = -1
            a.bf = 0
        
        c.bf = 0
        return c
    

    c本身为插入结点的情况如下:

    RL调整

    def RL(a,b):
        c = b.left
        b.left = c.right
        c.right = b
        a.right = c.left
        c.left = a
    
        if c.bf == 0:
            a.bf = b.bf = 0
        elif c.bf == 1:
            a.bf = 0
            b.bf = -1
        else:
            a.bf = -1
            b.bf = 0
        c.bf = 0
        return c
    

    平衡二叉排序树的插入操作:

    • 查找新节点的插入位置,并在查找过程中记录最小不平衡子树的根
    • 修改插入位置到最小不平衡子树根路径上各节点的平衡因子
    • 检查以a为根的子树是否失衡,若失衡则依据情况进行调整.
    def insert(btree, key):
        if btree is None:
            return TreeNode(key)
        a = btree   # 最终是最小不平衡树的根
        p = btree   # 指针
        fa = None   # a的父节点
        q = None    # p的父节点
    
        # 1. 查找插入位置并记录最小非平衡树根节点
        while p:
            # 若BF值不为0,则有可能为最小不平衡树的结点
            if p.bf != 0:
                fa, a = q, p
            
            # 查找插入位置:
            if p.val == key:
                return btree
            elif key < p.val:
                q = p
                p = p.left
            else:
                q = p
                p = p.right
        # 2. 插入节点
        # 此时q是待插入结点的父节点
        node = TreeNode(key)
        if key < q.val:
            q.left = node
        else:
            q.right = node
        
        # 3. 更新BF值,只需更新插入位置到a结点路径上结点的BF值.
        # 先判断插入节点在a的左子树还是右子树
        if key < a.val:
            p = a.left  # 指针
            b = a.left  # a深度较大子树的根节点,用于后续调整
            d = 1
        else:
            p = a.right
            b = a.right
            d = -1
    
        while p != node:
            if key < p.val:
                p.bf = 1    # p原来BF为0
                p = p.left
            else:
                p.bf = -1
                p = p.right
            
        # 4. 判断是否需要调整
        if a.bf == 0:   # a本身平衡,无需调整
            a.bf = d
            return btree
        elif a.bf == -d:    # 增加的结点在较低的树上,无需调整
            a.bf = 0
            return btree
        else:   # 增加的结点在较高的树上
            if d == 1:  # 增加在左子树
                if b.bf == 1: # 增加在左子树的左子树
                    b = LL(a, b)
                else:   # 增加在左子树的右子树
                    b = LR(a, b)
            else:
                if b.bf == 1:
                    b = RL(a, b)
                else:
                    b = RR(a, b)
        
        # 5.将调整好的树接回去
        # a为根节点
        if pa is None:
            btree = b
        elif pa.left == a:
            pa.left = b
        else:
            pa.right = b
        
        return btree
    
    展开全文
  • 108 根据有序数组构造平衡二叉排序树 点击此处返回总目录 ... 109 根据有序链表构造平衡二叉排序树 一、108 根据有序数组构造平衡二叉排序树 【题目】 ...

    108  根据有序数组构造平衡的二叉排序树                                                                      点击此处返回总目录

    109  根据有序链表构造平衡的二叉排序树

     

     

     

    一、108  根据有序数组构造平衡的二叉排序树

    【题目】

     

    【分析】

    二叉排序树定义就是,左边的值都小于root,右边的值都大于root。左右子树分别是一棵二叉排序树。

    定义就是递归定义的。

     

    所以,每次取数组的中间的值当做root。然后左边的数组建立左子树,右边的数组建立右子树即可。

     

    【代码】

     

    【结果】

     

     

     

     

    --------------------------------------------------------------------------------------------------------------------------------------

    二、109  根据有序链表构造平衡的二叉排序树

     

    【题目】

     

    【分析】

    这道题跟上一题一样,只不过把有序数组改成了有序链表。

    不要想得太复杂,还是同样的思路解决。只不过要解决怎么在有序链表中找中点。

    我们使用快慢指针来找链表中点。

     

    【代码】

     

     

    【结果】

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 26. 平衡二叉排序树

    万次阅读 多人点赞 2018-03-05 21:21:25
    平衡二叉排序树的生成,查找和删除

      对于给定的数组,如果按照之前的方式进行排序的话,有的时候会得到如下的结果

    在其中查找数字 5 ,很幸运只需要两步比较就可以得到最后的结果。但是也有可能变为如下的这种情况

    如果这个时候我们是要查找 9 的话就需要一直找到最后,所以这种情况是不好的。为了避免这种效率极端低下的查找过程,可以使用平衡二叉树排序树这种数据结构

    1. 相关定义

      平衡二叉排序树要求每个节点的左右子树有着相同高度,或者要求任何节点的左右节点的左右子树高度差不超过1。

      根据定义我们可以判断以下的几棵树是否属于平衡二叉排序树

      上面这个满足定义的要求,是一棵平衡二叉排序树。

      这棵树看起来像是平衡二叉排序树,因为他的深度满足要求;但实际上它并不是,因为首先不是一棵二叉排序树。

      这个也不是平衡二叉排序树,因为它虽然满足了二叉排序树的要求,但是并没有达到平衡的要求。比如说结点 9 的左子树的深度要比右子树的深度大 2,这就超过 1 了。

      这是平衡二叉排序树。

    2. 实现原理

      对于一个给定的数组 [3, 2, 1, 4, 5, 6, 7, 10, 9, 8],如果不适用平衡二叉排序树的生成方法,很有可能得到如下的结果

    这个结果明显是查找效率极低的,所以使用如下的平衡二叉排序树的方法。前三个数字组成的数组如下图所示

    明显这已经是一个不平衡的二叉排序树,我们可以看到左子树的深度减去右子树的深度都是大于零的,所以树向右旋转得到如下图所示的结果

      之后再加上 4 5 两个元素可以得到如下的图像

    我们可以看到这个二叉排序树中,对于 2 3 两个结点都是不平衡的,且两者的不平衡因子都是 2 ,在这里是 3 的不平衡导致了 2 不平衡,所以调整 3 4 5 这棵不平衡术就可以了,因为在这两个不平衡点中不平衡因子(BF)都是负数,所以应该将这棵最小不平衡树进行左旋转,如下图所示

      再向其中加入 6 这个结点,如下图所示

    在这棵树中可以看到只有根节点 2 是不平衡的,且 BF = -2 < 0,所以需要将根节点 2 向左旋转,得到如下的结果

    这个时候可以看到树已经不是一个二叉树,所以需要对 3 进行处理,由于 3 小于 4 ,所以将 3 连接在 4 的左子树的最右端,得到如下图所示的结果

      然后向其中加入数据节点 7 ,得到如下的结果

    其中的 5 6 7 构成了最小不平衡树,将它进行左旋转,得到如下结果

      再向其中加入 10 9 两个点,可以发现对于4 6 7 三个结点,它们的 bf = 2 ,所以需要调整二叉排序树,如下图所示

    但是这个结点不可以像之前一样通过旋转 7 10 9 这棵子树,因为这个时候, 10 结点的 BF 符号与之前的符号均不相同,所以要首先将 9 10 旋转,之后再将不平衡子树进行旋转,如下图所示
    这里写图片描述

    其中左侧是将 9 10 旋转之后得到的结果,而右侧是再经过一层旋转得到二叉平衡树。

      最后向树中添加结点 8,得到的结果如下图所示

    明显结点 4 的 BF 为正,结点 6 的 BF 为正,但是结点 9 的 BF 为负,这个时候应该先将 8 7 9 10 进行旋转,使得 BF 值相等,然后再调整二叉排序树,如下图所示

    这里写图片描述

    经过第一次旋转之后得到的结果如上图中左图所示,明显 4 6 结点不平衡,所以对 6 结点进行左旋转,得到上图中中间的图,这个时候的树不是二叉树,所以需要对 8 进行处理,因为 8 的值比对应的根节点 7 大,所以将它放在根节点 7 右子树的最左侧,得到上图中右图所示的情况,至此完成了平衡二叉树的生成。

    3. 代码

    #define LH 1
    #define EH 0
    #define RH -1
    
    typedef struct BiTNode
    {
        int data;
        int bf;
        struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    
    void R_Rotate(BiTree *p)
    {
        BiTree L;
        L = (*p)->lchild;
        (*p)->lchild = L->rchild;
        L->rchild = (*p);
        *p = L;
    
    }
    
    void LeftBalance(BiTree *T)
    {
        BiTree L, Lr;
        L = (*T)->lchild;
    
        switch(L->bf)
        {
            case LH:
                (*T)->bf = L->bf = EH;
                R_Rotate(T);
                break;
            case RH:
                Lr = L->rchild;
                switch(Lr->bf)
                {
                    case LH:
                        (*T)->bf = RH;
                        L->bf = EH;
                        break
                    case EH:
                        (*T)->bf = L->bf = EH;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        L->bf = LH;
                        break;
                }
                Lr->bf = EH;
                L_Rotate(&(*T)->lchild);
                R_Rotate(T);
        }
    }
    
    int InsertAVL(BiTree *T, int e, int *taller)
    {
        if( !*T )
        {
            *T = (BiTree)malloc(sizeof(BiTNode));
            (*T)->data = e;
            (*T)->lchild = (*T)->rchild = NULL;
            (*T)->bf = EH;
            *taller = TRUE;
        }
        else
        {
            if(e == (*T)->data)
            {
                *taller = FALSE;
                return FALSE;
            }
            if(e < (*T)->data)
            {
                if(!InsertAVL(&(*T)->lchild, e, taller))
                {
                    return FALSE;
                }
                if(*taller)
                {
                    switch((*T)->bf)
                    {
                        case LH:
                            LeftBalance(T);
                            *taller = FALSE;
                            break;
                        case EH:
                            (*T)->bf = LH;
                            *taller = TRUE;
                            break;
                        case RH:
                            (*T)->bf = EH;
                            *taller = FALSE;
                            break;
                    }
                }
            }
            else
            {
                if(!InsertAVL(&(*T)->rchild, e, taller))
                {
                    return FALSE;
                }
                if(*taller)
                {
                    switch((*T)->bf)
                    {
                        case LH:
                            (*T)->bf = EH;
                            *taller = FALSE;
                            break;
                        case EH:
                            (*T)->bf = RH;
                            *taller = TRUE;
                            break;
                        case RH:
                            RightBalance(T);
                            *taller = FALSE;
                            break;
                    }
                }
            }
        }
    }
    展开全文
  • /** * 实验题目: * 判断一个序列是否是二叉排序树中的一...* 设计程序,构造一颗二叉排序树bt,判断一个序列a是否是 * 二叉排序树bt中的一个合法的查找序列。 */ #include &lt;stdio.h&gt; #include &...
  • 引言:为啥会引入这些的数据结构呢?在学习数据结构的时候,这块内容放到“查找”的章节中,文中提到,很多的查找算法都是基于顺序存储而言的,且没有考虑 对查找数据进行维护的问题,也就是说只对一组静态数据...
  • 平衡二叉排序树

    2020-03-28 14:09:00
    解决:平衡二叉排序树。(平衡:高度差不大于1) 不平衡 >> 平衡:旋转 旋转: ①RR:左旋(上两个旋) ②LL:右旋(上两个旋) ③RL:先右旋(下两个旋)再左旋(上两个旋) ④LR:先左旋(下两个旋)再右旋...
  • 一、问题描述 根据给定的关键字序列,实现二叉排序树的基本操作。 输入格式:8, 10, 5, 6, 3, 13 二、实验目的 ...1、构造二叉排序树的存储结构。 2、实现创建、查找、插入、删除、平均查找长度等操作。
  • 编写一个程序,对于给定的一个有序的关键字序列,创建一棵高度最小的二叉排序树。并判断一个序列是否为该二叉排序树中的一个合法的查找序列 #include #include typedef struct node { int data; struct node *...
  • 二叉排序树 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上...
  • 二叉排序树的目的不是为了排序,而是为了提高查找(有序)、和删除关键字(树型结构)的速度; 特点:左子树<根节点<右子树 1.构造一颗二叉排序树 bool create_BST(BiTree &T,Elem *elem_list,int n){//...
  • 如何根据序列构建平衡二叉搜索?什么是平衡二叉搜索(AVL)?1、AVL的定义2、AVL的特点什么是右单旋转?什么是左单旋转?什么是双旋转?RR RL LR什么意思?实例题目过程 什么是平衡二叉搜索(AVL)? 1、...
  • //计算树bt的叶结点的个数 往年的真题都比较简单 (1)由于只要求构建二叉排序树不要求平衡,在查找失败的位置插入二叉排序树即可 (构造过程要写,我这里省去) 最后应该如图 (2)没有对系统开销作出限制,那我们...
  • 给定一个数组,如何构造一个二叉排序树(ADL)

    万次阅读 多人点赞 2016-09-26 11:54:11
    构造二叉排序树 构造一棵二叉排序树就是依次输入数据元素,将它们插入到二叉排序树中的适当位置上的过程。具体过程是:每次读入一个元素,就建立一个新的节点,若二叉排序树非空,则将新节点的值与根节点的值比较,...
  • 平衡二叉排序树

    2020-05-30 11:50:35
    平衡二叉排序树 问题:依次输入表(30,15,28,20,24,10,68,35,50)中的元素,生成一棵平衡二叉排序树。请画出构造过程,并在其中注明每一次平衡化的类型(LL型、RR型、LR型、RL型) 题目解析 本题考查的是二叉...
  • 二叉排序树平衡二叉树

    万次阅读 多人点赞 2019-07-10 23:26:38
    1. 二叉排序树 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。 二叉排序树定义: 二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: 若左子树不空,则左子树上...
  • 给定序列 6 8 5 7 9 3构建二叉排序树 并画出先序索二叉树
  • 当我们对上图的二叉排序树进行中序遍历时,便可以得到有序的序列;但构造一个排序二叉树的目的,其实并不是为了排序,而是为了提高查找和插入删除关键字的速度。 二叉排序树的操作 首先提供下二叉树的结构:
  • 二叉排序树

    千次阅读 多人点赞 2019-07-26 18:14:27
    一、二叉排序树的定义 二叉排序树(BST),也叫二叉查找树。二叉排序树或者是一颗空树,或者是一颗具有下列特性的非空二叉树: 1.若左子树非空,则左子树上所有结点关键字值均小于根结点的关键字值; 2.若右子...
  • 二叉排序树1、定义2、性质3、操作3.1 查找 1、定义 \quad \quad二叉排序树又称二叉搜索树、二叉查找树。 \quad \quad二叉排序树或是空树,或是满足以下性质的二叉树: (1)若其左子树非空,则左子树上所有结点的值...
  • 输入一组无序关键字(整数)序列构造一棵二叉排序树并对其进行中序遍历输出;在二叉排序树中查找某一关键字,若存在,显示查找成功;若不存在,将其插入到二叉排序树中,再中序遍历输出。 二叉排序树就是将一组数据...
  • 文章目录二叉搜索树/二叉排序树/二叉查找树.1 定义.2 性质二叉搜索树创建二叉搜索树查找.1 查找步骤.2 查找性能分析二叉树插入与删除 二叉搜索树/二叉排序树/二叉查找树 .1 定义 二叉排序树(Binary Sort Tree)...
  • 1、二叉排序树二叉排序树又称为二叉查找树。...构造二叉排序树的目的:提高查找和插入删除关键字的速度。 注意:二叉排序树中不允许有重复或相等的key值出现。1)删除操作 当删除的节点为叶子节点时,直接
  • 平衡二叉树和二叉排序树

    千次阅读 2020-05-27 20:30:51
    平衡二叉树是在二叉排序树的基础上发展而来的。平衡二叉树,又称AVL树,指的是左子树上的所有节点的值都比根节点的值小,而右子树上的所有节点的值都比根节点的值大,且左子树与右子树的高度差最大为1。因此,平衡...
  • 文章目录5.6 森林5.6.1 树的存储结构5.6.1.1 双亲表示法5.6.1.2 孩子表示...构造5.7.5 二叉排序树的删除5.7.6 二叉排序树的查找效率分析5.8 平衡二叉树5.8.1 平衡二叉树的定义5.8.2 平衡二叉树的插入5.8.2.1 LL平衡旋转...
  • 6.3二叉排序树

    2019-08-30 16:26:19
    6.3二叉排序树 定义:二叉排序树(Binary Search Tree也叫二叉搜索树)或者是空树或者是具有以下性质的二叉树;...对二叉排序树进行中序遍历可以得到一个递增的有序序列二叉排序树的目的,不是为了排序,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,416
精华内容 2,566
关键字:

关键字序列构造平衡二叉排序树