精华内容
下载资源
问答
  • 平衡二叉树 刚开始接触平衡二叉树,没有什么...平衡二叉树就是每个节点子树高度差不超过1二叉树。可以快速搜索数值一种算法,最糟情况就是一直找到底,但也是log(n)。还是快很多。 #include<stdlib...

    平衡二叉树

    刚开始接触平衡二叉树,没有什么太多要分析的。博客里有很多大佬们都写的很好。平衡二叉树就是每个节点的子树的高度差不超过1的二叉树。可以快速搜索数值的一种算法,最糟的情况就是一直找到底,但也是log(n)的。还是快很多。

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    #define max(a , b) (a > b ? (a) : (b))
    struct tree
    {
        int data, d;
        struct tree *ltree, *rtree;
    };
    
    int deep(struct tree *root)//计算深度
    {
        if(!root)
        {
            return 0;
        }
        else
            return root->d;
    }
    
    struct tree *LL(struct tree *root)//LL型,就是右旋。插入的是左树的左儿子。
    {
        struct tree *p = root->ltree;
        root->ltree = p->rtree;
        p->rtree = root;
        root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//记住每次旋转之后根位置变化了,要从新计算深度。
        return p;
    }
    
    struct tree *RR(struct tree *root)//RR型,就是左旋。插入的是右树的右儿子。
    {
        struct tree *p = root->rtree;
        root->rtree = p->ltree;
        p->ltree = root;
        root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//记住每次旋转之后根位置变化了,要从新计算深度。
        return p;
    }
    
    struct tree *LR(struct tree *root)//LR型,要先左旋再右旋,插入的是左树的右儿子。
    {
        root->ltree = RR(root->ltree);
        root = LL(root);
        return root;
    }
    
    struct tree *RL(struct tree *root)//RL型,要先右旋再左旋,插入的事右树的左儿子。
    {
        root->rtree = LL(root->rtree);
        root = RR(root);
        return root;
    }
    
    struct tree *creat(struct tree *root, int m)
    {
        if(!root)
        {
            root = (struct tree *)malloc(sizeof(struct tree));
            root->data = m;
            root->d = 1;//每次生成把深度记为1,当然0也可以(就是要在计算深度的地方要记得改为 return -1;)
            root->ltree = root->rtree = NULL;
            return root;
        }
        else
        {
            if(root->data > m)//插入二叉树的左树
            {
                root->ltree = creat(root->ltree, m);
                if(deep(root->ltree) - deep(root->rtree) > 1)
                {
                    if(root->ltree->data > m)//左树的左儿子
                    {
                        root = LL(root);
                    }
                    else//左树的右儿子
                    {
                        root = LR(root);
                    }
                }
            }
            else//插入二叉树的右树
            {
                root->rtree = creat(root->rtree, m);
                if(deep(root->rtree) - deep(root->ltree) > 1)
                {
                    if(root->rtree->data > m)//右树的左儿子
                    {
                        root = RL(root);
                    }
                    else//右树的右儿子
                    {
                        root = RR(root);
                    }
                }
            }
        }
        root->d = max(deep(root->ltree), deep(root->rtree)) + 1;//计算根的深度。
        return root;
    }
    
    int main()
    {
        int n, m;
        while(~scanf("%d", &n))
        {
            struct tree *root = NULL;//指针暂时不用的时候要记得初始化为NULL。要不会很恐怖不信你试试。
            while(n--)
            {
                scanf("%d", &m);
                root = creat(root, m);
            }
            printf("%d\n", root->data);
        }
        return 0;
    }
    
    

    转载于:https://www.cnblogs.com/zyysyang/p/11093505.html

    展开全文
  • 数据结构 - 平衡二叉树(C++)

    万次阅读 多人点赞 2019-02-22 15:36:53
    平衡二叉树的定义 平衡二叉树(Balanced Binary Tree)是具有以下性质的二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 判断一棵二叉树是否平衡(C++) ...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    平衡二叉树的定义

    平衡二叉树(Balanced Binary Tree)是具有以下性质的二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    判断一棵二叉树是否平衡(C++)

    /*
     * Created by Chimomo
     */
    
    #include <iostream>
    
    #define NULL 0
    
    using namespace std;
    
    template<class T>
    struct BTNode {
        T data;
        BTNode<T> *lChild, *rChild;
    
        BTNode();
    
        explicit BTNode(const T &val, BTNode<T> *childL = NULL, BTNode<T> *childR = NULL) {
            data = val;
            lChild = childL;
            rChild = childR;
        }
    
        BTNode<T> *CopyTree() {
            BTNode<T> *nl, *nr, *nn;
            if (&data == NULL) {
                return NULL;
            }
    
            nl = lChild->CopyTree();
            nr = rChild->CopyTree();
            nn = new BTNode<T>(data, nl, nr);
    
            return nn;
        }
    };
    
    template<class T>
    BTNode<T>::BTNode() {
        lChild = rChild = NULL;
    }
    
    template<class T>
    class BinaryTree {
    public:
        BTNode<T> *root;
    
        BinaryTree();
    
        ~BinaryTree();
    
        void DestroyTree();
    
        BTNode<T> *MakeTree(const T &element, BTNode<T> *l, BTNode<T> *r) {
            root = new BTNode<T>(element, l, r);
            if (root == NULL) {
                cout << "Failed for applying storage address, system will close the process." << endl;
                exit(1);
            }
    
            return root;
        }
    
    private:
        void Destroy(BTNode<T> *&r);
    };
    
    template<class T>
    BinaryTree<T>::BinaryTree() {
        root = NULL;
    }
    
    template<class T>
    BinaryTree<T>::~BinaryTree() {
        DestroyTree();
    }
    
    template<class T>
    void BinaryTree<T>::DestroyTree() {
        Destroy(root);
    }
    
    template<class T>
    void BinaryTree<T>::Destroy(BTNode<T> *&r) {
        if (r != NULL) {
            Destroy(r->lChild);
            Destroy(r->rChild);
            delete r;
            r = NULL;
        }
    }
    
    template<class T>
    int isBalanced(BTNode<T> *r) {
        if (!r) {
            return 0;
        }
    
        int left = isBalanced(r->lChild);
        int right = isBalanced(r->rChild);
        if ((left >= 0) && (right >= 0) && ((left - right) <= 1) && ((left - right) >= -1)) {
            return (left < right) ? (right + 1) : (left + 1);
        } else {
            return -1;
        }
    }
    
    int main() {
        BTNode<char> *b, *c, *d, *e, *f, *g;
        BinaryTree<char> a;
    
        b = a.MakeTree('F', NULL, NULL);
        c = a.MakeTree('E', NULL, NULL);
        d = a.MakeTree('D', b, NULL);
        e = a.MakeTree('C', NULL, NULL);
        f = a.MakeTree('B', d, c);
        g = a.MakeTree('A', f, e);
    
        if (isBalanced(a.root) >= 0) {
            cout << "This IS a balanced binary tree." << endl;
        } else {
            cout << "This is NOT a balanced binary tree." << endl;
        }
    
        return 0;
    }
    
    // Output:
    /*
    This is NOT a balanced binary tree.
    
    */

     

     

    展开全文
  • 什么是平衡二叉树? 搜索树结点不同插入次序,将导致不同的深度和平均查找...设 nh 高度为h的平衡二叉树的最少结点数。结点数最少时: 给定结点数为n的AVL树的最大高度为O(log2n) 平衡二叉树的调整 1.RR 旋转(右单

    什么是平衡二叉树?
    搜索树结点不同插入次序,将导致不同的深度和平均查找长度ASL。
    平衡因子(Balance Factor,简称BF): BF(T) = hL-hR,其中hL和hR分别为T的左、右子树的高度。
    平衡二叉树(Balanced Binary Tree)(AVL树)空树,或者任一结点左、右子树高度差的绝对值不超过1,即|BF(T) |≤ 1。
    在这里插入图片描述
    设 nh 高度为h的平衡二叉树的最少结点数。结点数最少时:
    在这里插入图片描述

    给定结点数为n的AVL树的最大高度为O(log2n)

    平衡二叉树的调整
    1.RR 旋转(右单旋)在这里插入图片描述
    不平衡的“发现者”是Mar,“麻烦结点”Nov 在发现者右子树的右边,因而叫 RR 插入,需要RR 旋转(右单旋)
    在这里插入图片描述
    2.LL 旋转(左单旋)
    在这里插入图片描述
    “发现者”是Mar,“麻烦结点”Apr 在发现者左子树的左边,因而叫 LL 插入,需要LL 旋转(左单旋)
    在这里插入图片描述
    3.LR 旋转(左-右双旋)
    在这里插入图片描述
    “发现者”是May,“麻烦结点”Jan在左子树的右边,因而叫 LR 插入,需要LR 旋转
    在这里插入图片描述
    4.RL 旋转(右-左双旋)
    在这里插入图片描述
    一般情况调整如下:
    在这里插入图片描述
    注意:有时候插入元素即便不需要调整结构,也可能需要重新计算一些平衡因子。

    问:在下列平衡树中插入3后,该树是否还平衡?如果不平衡应该做什么旋转进行调整?(C)
    在这里插入图片描述
    A.还是平衡的
    B.不平衡了,应该做LL旋转
    C.不平衡了,应该做RR旋转
    D.不平衡了,应该做LR旋转

    (以上笔记总结自浙江大学数据结构课程)

    展开全文
  • . word 资料 平衡二叉树操作的演示 需求分析 本程序是利用平衡二叉树实现动态...平衡二叉树的显示采用凹入表现形式 合并两棵平衡二叉树 把一棵二叉树分裂为两棵平衡二叉树使得在一棵树中的所有关键字都小于或等于x另一
  • ????什么是平衡二叉树 ????平衡二叉树的调整 ????右右旋转LL ????左左旋转LL ????左右旋转LR ????右左旋转RL ↓左右旋转LR ↓右右旋转RR ↓ 学习资源来源: 浙大 数据结构

    📖什么是平衡二叉树

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    📖平衡二叉树的调整

    🌿右右旋转LL
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    🌿左左旋转LL
    在这里插入图片描述
    🌿左右旋转LR
    在这里插入图片描述
    🌿右左旋转RL
    右左旋转RL在这里插入图片描述
    在这里插入图片描述
    ↓左右旋转LR
    在这里插入图片描述

    在这里插入图片描述
    ↓右右旋转RR
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    学习资源来源:
    浙大 数据结构

    展开全文
  • 数据结构 平衡二叉树

    2021-03-27 19:03:31
    平衡二叉树的基本概念1.1二叉查找树的问题1.2平衡二叉树的概念1.3平衡二叉树的作用2. 平衡二叉树的左旋右旋2.1 左旋或者右旋的触发时机2.2 左旋的过程2.3右旋的过程2.4平衡二叉树旋转的四种情况2.4.1左左2.4.2 左右...
  • 平衡二叉树操作的演示 1. 需求分析 本程序是利用平衡...更新平衡二叉树的显示 2 平衡二叉树的显示采用凹入表现形式 3 合并两棵平衡二叉树 4 把一棵二叉树分裂为两棵平衡二叉树使得在一棵树中的所有关键字都小于或 等
  • 平衡二叉树的实现广工数据结构课设源码加报告,实现完整。
  • 数据结构平衡二叉树的平衡因子BF 的计算
  • 数据结构之平衡二叉树平衡二叉树概念平衡二叉树的调整LL型调整RR型调整LR型调整RL型调整代码示例 平衡二叉树概念 平衡二叉查找树:简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的...
  • 数据结构课程设计任务书 设计题目 二叉树操作演示 指导教师 汤晓兵 班 级 计本03 学 生 已知技术参数和设计要求 [问题描述] 利用平衡二叉树实现一个动态查找表。 [基本要求] 实现动态查找表三种基本功能:...
  • 建议学习此数据结构可以先观看此视频 https://www.bilibili.com/video/BV1xE411h7dd 平衡二叉树的定义: 1.必须是一颗二叉查找树; 2.每一个节点的左子树和右子树的高度差至多为1。 平衡因子:二叉树节点的左...
  • 数据结构课程设计&平衡二叉树的实现;数据结构课程设计&平衡二叉树的实现;数据结构课程设计&平衡二叉树的实现
  • 数据结构-平衡二叉树

    2021-01-05 19:05:40
    数据结构-平衡二叉树什么是平衡二叉树旋转RR型,左旋LL型,右旋LR型,先左旋再右旋RL型,先右旋再左旋源码AVLTreeAVLSetAVLMap 什么是平衡二叉树 阅读本篇博客前最好对二叉搜索树有一定了解。二叉搜索树 二叉搜索树在...
  • 平衡二叉树的结构 如基本概念所树,它具有一个左子树和一个左子树,且对于任意一个子树而言,左子树和右子树高度只差不超过1. 三。 平衡因子 我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF...
  • 数据结构平衡二叉树的建立

    千次阅读 2017-02-09 09:14:02
    Problem Description根据给定的输入序列建立一棵平衡二叉树,求出建立的平衡二叉树的树根。 Input输入一组测试数据数据的第1行给出一个正整数N(n ),N表示输入序列的元素个数;第2行给出N个正整数,按数据给定...
  • *有时需要在大量增加、删除...*可以使用“平衡二叉树数据结构存放数据,体现在STL中,就是以下四种“排序容器”:multiset &set &multimap &map (就是使用该容器时候,边添加边自动排序了,很方便...
  • 文章目录目录平衡二叉树 平衡二叉树 平衡二叉查找树具有如下性质: 若左子树不空,则左子树上所有节点值均小于它根节点值; 若右子树不空,则右子树上所有节点值均大于或等于它根节点值; 每个非叶子...
  • 平衡二叉树各种操作递归实现
  • 博客思维导图 ...二叉树数据结构,顾名思义,只有两个叉,在数据结构中,操作性能要远高于线性结构,有O(height)索引性能。与线性结构有相同空间复杂度,特性如下: 每个节...
  • 主要介绍了C语言 数据结构平衡二叉树实例详解相关资料,需要朋友可以参考下
  • 数据结构学习之:平衡二叉树一、 平衡二叉树概述二、平衡二叉树单旋转1、右旋转2、右旋转三、平衡二叉树双旋转四、代码实现平衡二叉树的单、双旋转 一、 平衡二叉树概述 平衡二叉树(AVL树)按个人理解其实是对二叉...
  • 文章目录数据结构平衡二叉树剖析概述原理时间复杂度分析实现实现平衡二叉树使用平衡二叉树实现映射和集合Leetcode 349.Intersection of Two Arrays 两个数组交集Leetcode 350.Intersection of Two Arrays II 两...
  • 我们的数据结构实验课里的关于平衡二叉树的代码。 包含二叉树的插入和平衡,先序、中序和后序遍历。 基本全是按照清华的那本教科书里的思路写的,清晰易懂。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,460
精华内容 2,184
关键字:

平衡二叉树的数据结构

数据结构 订阅