精华内容
下载资源
问答
  • 平衡二叉树调整例题
    2019-10-30 21:24:08

    平衡二叉树的调整整理

    相关概念

    二叉排序树

    二叉排序树或者是一颗空树;或者是具有下列性质的二叉树:
    1、若它的左子树不空,则左子树上所有结点的值均小于她的根结点的值
    2、若它的右子树不空,则右子树上所有结点的值均大于她的根结点 的值
    3、它的左右子树也分别为二叉排序树

    平衡二叉树

    平衡二叉树又称AVL树,特点是它的左子树和右子树都是平衡二叉树,而且左子树和右子树的深度之差不超过1

    平衡因子

    二叉树结点上左子树的深度减去右子树的深度,平衡二叉树的平衡因子只可能是-1、0、1

    最小平衡子树

    以距离插入结点最近的,平衡因子绝对值大于1的结点为跟的子树
    在这里插入图片描述

    平衡二叉树的调整部分

    平衡二叉树的调整分为LL、RR和LR、RL两种,其中LL、RR一组相对简单,LR、RL则需要分两步走

    实例

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

    技巧总结

    • RR左旋,LL右旋
    • RL先将右子树以右孩子为轴右旋,再将原根结点落下去,类似于RR的左旋
    • LR先将左子树以左孩子为轴左旋,再将原根结点落下去,类似于LL的右旋
    更多相关内容
  • 定义: 平衡二叉树(AVL):是一种平衡的二叉搜索树。 平衡因子:将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor),|BF|。 性质: 空二叉树是一个 AVL 树 如果 T 是一棵 AVL 树...

    定义:

    平衡二叉树(AVL):是一种平衡的二叉搜索树。
    平衡因子:将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor),|BF|<=1。

    性质:

    1. 空二叉树是一个 AVL 树
    2. 如果 T 是一棵 AVL 树,那么其左右子树也是 AVL 树,并且|h(ls)-h(rs)| <= 1 ,h 是其左右子树的高度
    3. 树高为O(log n)
    4. 它必须是二叉搜索树。

    插入节点:

    与 BST(二叉搜索树)中类似,先进行一次失败的查找来确定插入的位置,插入节点后根据平衡因子来决定是否需要调整。

    参考代码

    //获取高度
    int getHeight(Node *root)
    {
    	if (root == NULL)
    		return 0;
    	return max(getHeight(root->l), getHeight(root->r)) + 1;
    }
    //获取平衡因子
    int getBalance(Node *root)
    {
    	return getHeight(root->l) - getHeight(root->r);
    }
    
    //节点插入
    void insert(Node *&root, int x)
    {
    	if (root == NULL)
    	{
    		root = new Node();
    		root->data = x;
    		root->l = root->r = NULL;
    		return;
    	}
    	if (x <= root->data)
    	{
    		//插入完成后
    		insert(root->l, x);
    		//进行平衡调整
    		if (getBalance(root) == 2)
    		{
    			// LL型,右旋
    			if (getBalance(root->l) == 1)
    			{
    				R(root);
    			}
    			// LR型,先对左子树左旋,再整体右旋
    			else if (getBalance(root->l) == -1)
    			{
    				LR(root);
    			}
    		}
    	}
    	else
    	{
    		insert(root->r, x);
    		if (getBalance(root) == -2)
    		{
    			// RR型,左旋
    			if (getBalance(root->r) == -1)
    			{
    				L(root);
    			}
    			// RL型,先对右子树右旋再整体左旋
    			else if (getBalance(root->r) == 1)
    			{
    				RL(root);
    			}
    		}
    	}
    }
    

    删除节点(未实现,待补):

    1. 删除和 BST 类似,将结点与后继交换后再删除。
    2. 删除会导致树高以及平衡因子变化,这时需要沿着被删除结点到根的路径来调整这种变化。

    平衡的维护:

    主要分以下4种平衡维护情况
    1.LL型
    由于在A的左子树(L)的左子树(L)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由1增至2。下图是LL型的最简单形式,显然,按照大小关系,结点B应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,A结点就好像是绕结点B顺时针旋转一样。(这里我们称为右旋)
    在这里插入图片描述

    一般形式如下图所示,表示在A的左孩子B的左子树BL(不一定为空)中插入结点C而导致不平衡( h 表示子树的深度)。
    这种情况调整如下:
    a.将A的左孩子B提升为新的根结点;
    b.将原来的根结点A降为B的右孩子;
    c.各子树按大小关系连接(BL和AR不变,BR调整为A的左子树)。
    在这里插入图片描述

    参考代码

    //右旋
    void R(Node *&root)
    {
    	Node *tmp = root->l;
    	root->l = tmp->r;
    	tmp->r = root;
    	root = tmp;
    }
    

    2.RR型
    由于在A的右子树(R)的右子树(R)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由-1变为-2。下图是RR型的最简单形式。显然,按照大小关系,结点B应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,A结点就好像是绕结点B逆时针旋转一样。(这里我们称为左旋)
    在这里插入图片描述

    RR型调整的一般形式如下图所示,表示在A的右孩子B的右子树BR(不一定为空)中插入结点C而导致不平衡( h 表示子树的深度)。
    这种情况调整如下:
    a.将A的右孩子B提升为新的根结点;
    b.将原来的根结点A降为B的左孩子
    c.各子树按大小关系连接(AL和BR不变,BL调整为A的右子树)。
    在这里插入图片描述

    参考代码

    //左旋
    void L(Node *&root)
    {
    	Node *tmp = root->r;
    	root->r = tmp->l;
    	tmp->l = root;
    	root = tmp;
    }
    

    3.LR型
    由于在A的左孩子(L)的右子树(R)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由1变为2。下图是LR型的最简单形式。显然,按照大小关系,结点C应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡。
    在这里插入图片描述

    LR型调整的一般形式如下图所示,表示在A的左孩子B的右子树(根结点为C,不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。
    这种情况调整如下:
    将B的左孩子C提升为新的根结点;
    将原来的根结点A降为C的右孩子;
    各子树按大小关系连接(BL和AR不变,CL和CR分别调整为B的右子树和A的左子树)。
    在这里插入图片描述

    示例操作:
    在这里插入图片描述

    参考代码

    //先左旋再右旋
    void LR(Node *&root)
    {
    	L(root->l);
    	R(root);
    }
    

    4.RL型
    由于在A的右孩子(R)的左子树(L)上插入新结点,使原来平衡二叉树变得不平衡,此时A的平衡因子由-1变为-2。下图是RL型的最简单形式。显然,按照大小关系,结点C应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡。

    在这里插入图片描述

    RL型调整的一般形式如下图所示,表示在A的右孩子B的左子树(根结点为C,不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。
    这种情况调整如下:
    将B的左孩子C提升为新的根结点;
    将原来的根结点A降为C的左孩子;
    各子树按大小关系连接(AL和BR不变,CL和CR分别调整为A的右子树和B的左子树)。
    在这里插入图片描述

    示例操作:
    在这里插入图片描述

    参考代码

    //先右旋再左旋
    void RL(Node *&root)
    {
    	R(root->r);
    	L(root);
    }
    

    例题:PAT-甲级 1123 Is It a Complete AVL Tree(板子题)

    Question:

    An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
    Now given a sequence of insertions, you are supposed to output the level-order traversal sequence of the resulting AVL tree, and to tell if it is a complete binary tree.

    Input Specification:

    Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 20). Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

    Output Specification:

    For each test case, insert the keys one by one into an initially empty AVL tree. Then first print in a line the level-order traversal sequence of the resulting AVL tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line. Then in the next line, print YES if the tree is complete, or NO if not.

    Sample Input 1:

    5
    88 70 61 63 65
    

    Sample Output 1:

    70 63 88 61 65
    YES
    

    Sample Input 2:

    8
    88 70 61 96 120 90 65 68
    

    Sample Output 2:

    88 65 96 61 70 90 120 68
    NO
    

    参考代码:

    
    #include <bits/stdc++.h>
    #define io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
    #define LL long long
    #define PII pair<int, int>
    #define PLL pair<LL, LL>
    #define PIII pair<int, PII>
    #define PSI pair<string, int>
    #define PIIS pair<int, pair<int, string>>
    #define PDD pair<double, double>
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int N = 2e5 + 5;
    const int M = 1e5;
    const int mod = 1e9 + 7;
    
    struct Node
    {
    	int data, pos;
    	Node *l, *r;
    };
    //获取高度
    int getHeight(Node *root)
    {
    	if (root == NULL)
    		return 0;
    	return max(getHeight(root->l), getHeight(root->r)) + 1;
    }
    //获取平衡因子
    int getBalance(Node *root)
    {
    	return getHeight(root->l) - getHeight(root->r);
    }
    //左旋
    void L(Node *&root)
    {
    	Node *tmp = root->r;
    	root->r = tmp->l;
    	tmp->l = root;
    	root = tmp;
    }
    //右旋
    void R(Node *&root)
    {
    	Node *tmp = root->l;
    	root->l = tmp->r;
    	tmp->r = root;
    	root = tmp;
    }
    // LR型
    void LR(Node *&root)
    {
    	L(root->l);
    	R(root);
    }
    // RL型
    void RL(Node *&root)
    {
    	R(root->r);
    	L(root);
    }
    void insert(Node *&root, int x)
    {
    	if (root == NULL)
    	{
    		root = new Node();
    		root->data = x;
    		root->l = root->r = NULL;
    		return;
    	}
    	if (x <= root->data)
    	{
    		//插入完成后
    		insert(root->l, x);
    		//进行平衡调整
    		if (getBalance(root) == 2)
    		{
    			// LL型,右旋
    			if (getBalance(root->l) == 1)
    			{
    				R(root);
    			}
    			// LR型,先对左子树左旋,再整体右旋
    			else if (getBalance(root->l) == -1)
    			{
    				L(root->l);
    				R(root);
    			}
    		}
    	}
    	else
    	{
    		insert(root->r, x);
    		if (getBalance(root) == -2)
    		{
    			// RR型,左旋
    			if (getBalance(root->r) == -1)
    			{
    				L(root);
    			}
    			// RL型,先对右子树右旋再整体左旋
    			else if (getBalance(root->r) == 1)
    			{
    				R(root->r);
    				L(root);
    			}
    		}
    	}
    }
    int n;
    int main()
    {
    	// io;
    	cin >> n;
    	Node *root = NULL;
    	for (int i = 0, x; i < n; i++)
    	{
    		cin >> x;
    		insert(root, x);
    	}
    
    	queue<Node *> heap;
    	root->pos = 1;
    	heap.push(root);
    	int m = 0;
    	while (heap.size())
    	{
    		auto tmp = heap.front();
    		heap.pop();
    		if (tmp->pos == 1)
    			cout << tmp->data;
    		else
    			cout << " " << tmp->data;
    		m = max(m, tmp->pos);
    
    		if (tmp->l != NULL)
    		{
    			tmp->l->pos = (tmp->pos) * 2;
    			heap.push(tmp->l);
    		}
    		if (tmp->r != NULL)
    		{
    			tmp->r->pos = (tmp->pos) * 2 + 1;
    			heap.push(tmp->r);
    		}
    	}
    	if (m <= n)
    		cout << "\nYES";
    	else
    		cout << "\nNO";
    	// system("pause");
    	return 0;
    }
    /*
    
    */
    
    
    展开全文
  • 二叉树相关OJ题目——二叉树的高度,平衡二叉树的判断

    ✅作者简介:大家好,我是小鱼儿,大家可以叫我鱼儿

    📒博客首页:是小鱼儿哈

    🔥系列专栏:一起刷好题

    🌻每日一句:勤奋这把可能变成现实,懒惰者把甜作苦受

    💖博主也在学习阶段,如发现问题请告知,非常感谢💖

    再解答平衡二叉树这个问题前,我们先来看这样一个题目

     

    📝这个问题我们可以转换为子问题求解,如果我们知道了该二叉树的左子树和右子树的最大深度就相当于知道了该二叉树的深度,同样左子树和右子树也有各自他们所对应的左子树和右子树,这样我们还需要求他们各自的左右子树的深度,这就是一个从上到下的递归过程。

    把一个大规模的问题,拆分为多个小规模的子问题
    🌰要求3为根节点的二叉树深度:
    🌰以9为根节点的二叉树的深度x
    🌰以20为根节点的二叉树的深度y
    答案=Max(9为根节点的二叉树的深度x,20为根节点的二叉树的深度y)+1

     

     

    public int maxDepth(TreeNode root) {
            if (root == null) return 0; // 递归结束的条件,root节点为null,深度自然为0
            int leftHeight = maxDepth(root.left); // 求左子树的高度
            int rightHeight = maxDepth(root.right);  // 求右子树的高度
            //单层逻辑
            //左子树的深度和右子树的深度最大的值+1就是二叉树的深度
            return Math.max(leftHeight, rightHeight) + 1;
        }

     

    有了上面的基础,我们回过头来看我们的平衡二叉树问题

     
    分析:

    二叉树的每个节点的左右子树的高度差的绝对值不超过 1,则二叉树是平衡二叉树。高度差的绝对值不超过1好办(我们上面那个题不就是求高度的吗?)但问题是怎样确保每个结点的左右子树高度差都不超过1呢?

    我们不妨换一种思路,如果一个树是平衡二叉树,那么他的左子树和右子树也都必须是平衡二叉树才行。然后如果左子树想是一个平衡二叉树,那么该左子树他的左右子树是不是也必须是平衡二叉树呀!

    这样从上往下递归下去,在递归的过程中我们一定是通过求当前结点的左右子树的高度来进行是否是平衡树的判断的,那么在递归过程中我们其实就完成了对每个结点左右子树高度的判断。

     

    class Solution {
        // 求当前结点高度的函数
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
        // 一个树既然是平衡二叉树,那么他的所有子树都是平衡二叉树
        public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            int left = maxDepth(root.left); // 递归求当前树左右子树的深度
            int right = maxDepth(root.right);
            if (left - right < -1 || left - right > 1) return false; // 如果差的绝对值大于一就返回false
            return isBalanced(root.left) && isBalanced(root.right); 
            // 递归判断每个节点是否是平衡二叉树,就该结点的左子树和右子树是否为平衡二叉树
            // 只有当左子树和右子树都是平衡二叉树时,该树才是平衡二叉树
        }
    }

    上面我们对每个结点其实都算了他的左右子树的高度,但很多情况下对每个结点都判断其实是没必要的,比如:

    🌰 在这个二叉树中,很明显就不是一个平衡二叉树,比如结点9他的左子树的高度是2,右子树高度是0,这明显就不符合题目中平衡二叉树的定义啊!那么我们能不能在求高度的时候,如果遇到高度差的绝对值大于1了,就直接说明该二叉树不平衡呢

    📝所以我们可以对于当前遍历到的节点,先递归地判断其左右子树是否平衡,再判断以当前节点为根的子树是否平衡。如果一棵子树是平衡的,则返回其高度(高度一定是非负整数),否则返回 -1(仅仅只是把不平衡的子树标记起来,只要他与正常的高度返回值不同就行也可以是-100)。如果存在一棵子树不平衡,即返回了负数,则整个二叉树一定不平衡

    class Solution {
        // 求当前结点高度的函数
        public int maxDepth(TreeNode root) {
            if (root == null) return 0;
            // 在求高度的过程中其实也进行了平衡二叉树的判断,
            // 如果返回值为负数说明已经有一个子树不是平衡二叉树了,即整个树已经不是平衡二叉树了
            int leftHeight = maxDepth(root.left);  // 所以接下来if里要加上leftHeight >= 0 && rightHeight >= 0这样的判断
            int rightHeight = maxDepth(root.right);  // 如果为-1,已经不是正常情况,所以不能进入到接下来的if语句里
            if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
                return Math.max(leftHeight, rightHeight) + 1; // 正常情况下返回的一定大于0的
            }
            else {
                return -1;  // 说明该子树的不是平衡二叉树,即整个树就不是平衡二叉树
            }
        }
        // 一个树既然是平衡二叉树,那么他的所有子树都是平衡二叉树
        public boolean isBalanced(TreeNode root) {
            return maxDepth(root)>=0; // 只有每个子树都是平衡二叉树,该数才是平衡二叉树
            // 如果每个子树都是平衡的,累加的返回值不可能为负数(因为每个相加的高度都是整数)
            // 如果一个子树返回了-1,及时其他的子树是正常的但因为我们再maxDepth的if语句里加了
            // leftHeight >= 0 && rightHeight >= 0,所以正常的高度也不会返回,也不会把负数冲掉
        }
    }

     

    再回顾一下就是:

    • 一是我们需要先处理子树的深度再进行 比较
    • 二是如果我们在处理子树时发现其已经不平衡了,则可以返回一个-1,使得所有其长辈节 点可以避免多余的判断  
    展开全文
  • 平衡二叉树

    2022-04-07 19:15:35
    定义:平衡二叉树是一棵二叉排序树,或者为空,或者满足以下条件: (1)左右子树高度差的绝对值不大于1; (2)左右子树都是平衡二叉树。 平衡因子:对于二叉树中任一结点T,其平衡因子(Balance Factor,简称 BF)...

    定义:平衡二叉树是一棵二叉排序树,或者为空,或者满足以下条件:

               (1)左右子树高度差的绝对值不大于1;

               (2)左右子树都是平衡二叉树。

    平衡因子:对于二叉树中任一结点T,其平衡因子Balance Factor,简称 BF)定义为BF(T) = hL-hR,其中hLhR分别为T的左、右子树的高度。

    平衡化旋转:如果在一棵 AVL 树中插入一个新结点后造成失衡,则必重新调整树的结构,使之恢复平衡。我们称此调整平衡的过程为平衡旋转

    平衡化旋转的类别

    • LL型:新插入结点在A的左孩子(L)的左子树(L)中;
    • LR型:新插入结点在A的左孩子(L)的右子树(R)中;
    • RL型:新插入结点在A的右孩子(R)的左子树(L)中;
    • RR型:新插入结点在A的右孩子(R)的右子树(R)中。

    构造平衡二叉树(AVL)

    例题1:输入关键字序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 },构成一棵平衡二叉排序树。

    ①插入16        ②插入3                     ③插入7   ----->          LR双旋                 

    ④插入11                             ⑤插入9       -------->   LL单旋

    ⑥插入26                            -------->      RR单旋

     

     ⑦插入18                                         -------->        RL双旋

     

     ⑧插入14                                                ⑨插入15                -------->        LR双旋

     

     例题2:给出如下平衡树,平衡二叉树中删除结点22,展示输出后的结果。

     答案:

    展开全文
  • 平衡二叉树调整(详解 LL、RR、LR、RL)

    万次阅读 多人点赞 2019-05-21 21:46:50
    当向一棵AVL树中插入一个新的结点,有可能会破坏树的平衡,这时就需要调整这棵树,本文将详细讲解各种调整的过程
  • 平衡二叉树习题

    千次阅读 2020-05-18 09:56:40
    1、给定一个二叉树,判断它是否是高度平衡二叉树。 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4] 1 / \ 2 2 / \ 3 ...
  • 首先我们来思考一下一个普通二叉树保存数据,如果想查找一个数据,由于普通二叉树保存数据是随机的,要找到数据的时间复杂度为O(n)。后面为了方便 ,我们又学习二叉搜索树,它的定义是将比根节点小的数放左边,比根...
  • 平衡二叉树的构造过程实例

    万次阅读 多人点赞 2019-04-14 09:13:08
    平衡二叉树实现的实例 选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树。 首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的,再插入0是,2的平衡因子变为2,此时出现了不平衡...
  • 平衡二叉树的旋转以及简便方法

    千次阅读 多人点赞 2021-04-06 22:24:33
    刚开始听这个平衡二叉树的旋转,一听就蒙了,后来看了很多视频,有很多的说法。下面来介绍平衡二叉树 平衡二叉树:就是每个节点的平衡因子(Balance Factor)(以下简称BF)的绝对值小于等于1,即为0或1。 而BF就是每...
  • 现在通过实例来分析平衡二叉树的实现过程,以便更好的理解。 选取一组数据分别为2,1,0,3,4,5,6,9,8,7的10个结点来构造平衡二叉树。 (1)首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的...
  • 平衡二叉树、二叉树的经典题 1 平衡二叉树 题目 输入一棵二叉树,判断该二叉树是否是平衡二叉树平衡二叉树:每个子树的深度之差不超过1 思路 后续遍历二叉树,在遍历二叉树每个节点前都会遍历其左右子树 ...
  • 平衡二叉树专题

    千次阅读 2021-02-12 02:06:04
    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找...
  • 平衡二叉树(AVL树)

    2021-08-17 18:21:54
    假设现在已有一棵平衡二叉树,那么可以预见,在往其中插入一个结点时,一定会有结点的平衡因子发生变化,此时可能会有结点的平衡因子的绝对值大于1(这些平衡因子只可能是2或者-2),这样以该结点为根结点的子树就是...
  • 构造平衡二叉树 期末题一: 对关键字序列{23,76,47,53,41,12,85,30,90,100},构造一棵平衡二叉树并画图。 按照顺序依次插入,第一数是23,作为根节点。 第二个是76,比23大,作为23的右孩子。 第三个是47...
  • 数据结构(八)平衡二叉树

    千次阅读 多人点赞 2018-11-02 12:01:46
    平衡二叉树的定义和四种调整策略
  • AVL树本质上还是一棵二叉搜索树,AVL=BST+AVL = BST +AVL=BST+ 平衡操作。 AVL树的特点是: 本身首先是一棵二叉搜索树。 带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为 111。 树中的...
  • 3.1为什么要用平衡二叉树 3.2平衡二叉树的定义 3.3平衡二叉树失衡的调整 3.3.1四种失衡二叉排序树的具体过程 3.4给出数值构造平衡二叉树例题 1、为什么要用树表查询 2、二叉排序树 2.1二叉排序树的定义 注意子树...
  • 由于二叉排序树的查找效率与树的高度有关,为了避免树的高度增长过快,降低BST查找性能,规定在插入和删除二叉树的时候,要保证任意结点的左右子树高度差的绝对值不超过1,这样的二叉树就是平衡二叉树,即AVL树。...
  • 【数据结构】——平衡二叉树(插入)

    千次阅读 热门讨论 2016-12-07 16:35:15
    平衡二叉树,是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。高度平衡?意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树...
  • 《数据结构与算法》——树与二叉树之平衡二叉树(AVL)总结 emmm,该来的总会来的,终于复习到了平衡二叉树部分。在写这份总结之前平衡二叉树操作是一个噩梦,之后,这是我知识库里的一个知识点,嗯,该把他供到...
  • AVL平衡二叉树总结

    2018-12-19 16:51:56
    四种类型的调整_哔哩哔哩_bilibili 数据结构与算法基础--第13周4--7.3树表的查找9--7.3.2平衡二叉树4--平衡调整方法3--例题_哔哩哔哩_bilibili 旋转原则: 下面看一张图: PS: 以下 p 是A q是B LL型: 1) 定义一...
  • 平衡二叉树 - 打印》中已经给出了创建、插入、查询、打印以及销毁平衡二叉树的C语言实现过程,在此篇中出现的一些结构体、宏、枚举、函数等相关定义可以到以上两篇中找到。之所以现在才来写平衡二叉树的删除操作...
  • 插入值插入在叶子节点上 例题: 就是一个点一个点的加就行,加入某个点后如果失衡,则调整调整后在加点,再调整,知道所有的点都加上,且不失衡就ok了
  • 数据结构——树表的查找(平衡二叉树平衡二叉树 平衡二叉树 平衡二叉树(balanced binary tree) 又称AVL树(Adelson-Velskii and Landis) 一棵平衡二叉树或是空树,或者是具有下列性质的二叉排序树:  ①左子树...
  • AVL树(平衡二叉树) 四种AVL树的插入,说白了就是四种调整方法的使用 判断平衡与否 首先四种调整方法的定位,关键是两个节点的寻找 影响节点:影响AVL树平衡位置的节点,例如图中的 NOV 被影响节点:因为新插入节点...
  • 数据结构-树和二叉树(六)二叉平衡树; 本文详细介绍了二叉平衡树的定义、平衡二叉树的插入调整以及查找效率分析!Let’s go!
  • 平衡二叉树(AVL)

    2018-09-25 20:34:41
    对于而查找树来说序列{1,2,3,4...于是就产生了平衡二叉树   平衡因子:左子树与右子树的高度之差称为该结点的平衡因子。   只要能随时保证每个结点平衡因子的绝对值不超过1,AVL的高度就始终能保持O(logn)...
  • ① 如下左图二叉排序中,看根节点的左子树高度为2,右子树高度为3,高度差为-1,左右各子树高度差如图计算所示,所以该二叉排序树为平衡二叉树。 ② 如下右图二叉排序树中,看根节点的左子树高度为2,右子树高度为3...
  • 本文是[数据结构基础系列(8):查找]中第8课时[平衡二叉树]的例程。 平衡二叉树相关算法 #include <stdio.h> #include <malloc.h> typedef int KeyType; //定义关键字类型 typedef char InfoTyp...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 689
精华内容 275
关键字:

平衡二叉树调整例题