平衡二叉树 骑猪看日落 2022-05-17 01:24 238阅读 0赞 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.只要二叉树上有一个节点的平衡因子的绝对值大于1,那么这颗平衡二叉树就失去了平衡。 假设我们已经有棵平衡二叉树,现在让我们来看看插入节点后,原来节点失去平衡后,我们进行选择的处理方式。 ![1337132907_4103.gif][] tip:上述图片lr处有错误,不要信以为真; 平衡二叉树多用于查找数据,所以平衡二叉树又是颗二叉排序树。 那么如何创建一颗平衡二叉树呢? 创建平衡二叉树,我们采用依次插入节点的方式进行。而平衡二叉树上插入节点采用递归的方式进行。递归算法如下: (1) 若该树为一空树,那么插入一个数据元素为e的新节点作为平衡二叉树的根节点,树的高度增加1。 (2) 若待插入的数据元素e和平衡二叉树(BBST)的根节点的关键字相等,那么就不需要进行插入操作。 (3) 若待插入的元素e比平衡二叉树(BBST)的根节点的关键字小,而且在BBST的左子树中也不存在和e有相同关键字的节点,则将e插入在BBST的左子树上,并且当插入之后的左子树深度增加1时,分别就下列情况处理之。 (a) BBST的根节点的平衡因子为-1(右子树的深度大于左子树的深度):则将根节点的平衡因子更改为0,BBST的深度不变; (b) BBST的根节点的平衡因子为0(左右子树的深度相等):则将根节点的平衡因子修改为1,BBST的深度增加1; (c) BBST的根节点的平衡因子为1(左子树的深度大于右子树的深度):若BBST的左子树根节点的平衡因子为1,则需要进行单向右旋转平衡处理,并且在右旋处理后,将根节点和其右子树根节点的平衡因子更改为0,树的深度不变; 若BBST的左子树根节点的平衡因子为-1,则需进行先向左,后向右的双向旋转平衡处理,并且在旋转处理之后,修改根节点和其左,右子树根节点的平衡因子,树的深度不变; (4) 若e的关键字大于BBST的根节点的关键字,而且在BBST的右子树中不存在和e有相同关键字的节点,则将e插入到BBST的右子树上,并且当插入之后的右子树深度加1时,分别就不同的情况处理之。 (a) BBST的根节点的平衡因子是1(左子树的深度大于右子树的深度):则将根节点的平衡因子修改为0,BBST的深度不变; (b) BBST的根节点的平衡因子是0(左右子树的深度相等):则将根节点的平衡因子修改为-1,树的深度加1; (c) BBST的根节点的平衡因子为-1(右子树的深度大于左子树的深度):若BBST的右子树根节点的平衡因子为1,则需要进行两次选择,第一次先向右旋转,再向左旋转处理,并且在旋转处理之后,修改根节点和其左,右子树根节点的平衡因子,树的深度不变; 若BBST的右子树根节点的平衡因子为1,则需要进行一次向左的旋转处理,并且在左旋之后,更新根节点和其左,右子树根节点的平衡因子,树的深度不变; **Think:** 平衡二叉树 AVL 树, 记住基本操作 就大概挺容易了吧 主要操作有 **LL** struct node *LL(struct node *t) { struct node *p = t -> l; t -> l = p -> r; p -> r = t; p -> d = max(deep(p -> l), t -> d) + 1; t -> d = max(deep(t -> l),deep(t -> r)) + 1; return p; } * **RR** struct node *RR(struct node *t) { struct node *p = t -> r; t -> r = p -> l; p -> l = t; p -> d = max(deep(p -> l),t -> d) + 1; t -> d = max(deep(t -> l),deep(t -> r)) + 1; return p; } * **RL** struct node *RL(struct node *t) { t -> r = LL(t -> r); return RR(t); } * **LR** struct node *LR(struct node *t) { t -> l = RR(t -> l); return LL(t); } eg:[https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2563/pid/3374][https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2563_pid_3374] #include<bits/stdc++.h> using namespace std; typedef int Elemtype; struct node { Elemtype data; int d;///纪录深度; struct node *l, *r; }; struct node *creat(struct node *t, int x); int max(int a, int b); int deep(struct node *t); struct node *LL(struct node *t); struct node *RR(struct node *t); struct node *RL(struct node *t); struct node *LR(struct node *t); int main() { int n, m, i; cin >> n; struct node *tree = NULL; for (i = 0; i <= n - 1; i ++) { cin >> m; tree = creat(tree , m); } cout << tree -> data<<endl; return 0; } struct node *creat(struct node *t, int x) { if (t == NULL) { t = new node; t ->data = x; t -> d = 0; t -> l = t -> r = NULL; } else if (t -> data > x) { t -> l = creat(t -> l , x); if (deep(t -> l) - deep(t -> r) > 1) { if (t -> l -> data > x) t = LL(t); else t = LR(t); } } else if (t -> data < x) { t -> r = creat(t -> r, x); if (deep(t -> r) - deep(t -> l) > 1) { if (t -> r -> data < x) t = RR(t); else t = RL(t); } } t -> d = max(deep(t -> l), deep(t -> r)) + 1;///+1,加上当前节点; return t; } int max(int a, int b) { if (a > b) return a; else return b; } int deep(struct node *t) { if (t == NULL) return -1; else return t -> d; } struct node *LL(struct node *t)///左旋 { struct node *p = t -> l; t -> l = p -> r; p -> r = t; p -> d = max(deep(p -> l), t -> d) + 1; t -> d = max(deep(t -> l),deep(t -> r)) + 1; return p; } struct node *RR(struct node *t)///右旋; { struct node *p = t -> r; t -> r = p -> l; p -> l = t; p -> d = max(deep(p -> l),t -> d) + 1; t -> d = max(deep(t -> l),deep(t -> r)) + 1; return p; } struct node *RL(struct node *t) { t -> r = LL(t -> r); return RR(t); } struct node *LR(struct node *t) { t -> l = RR(t -> l); return LL(t); } [1337132907_4103.gif]: https://img-my.csdn.net/uploads/201205/16/1337132907_4103.gif [https_acm.sdut.edu.cn_onlinejudge2_index.php_Home_Contest_contestproblem_cid_2563_pid_3374]: https://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2563/pid/3374
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 225 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 395 阅读
相关 平衡二叉树 请要相信我,30分钟让你掌握AVL树(平衡二叉树) 前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也 爱被打了一巴掌/ 2022年05月19日 04:21/ 0 赞/ 238 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 266 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 239 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 283 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 323 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 438 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 386 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 439 阅读
还没有评论,来说两句吧...