平衡二叉树(AVL)
2018-12-13 08:55:48来源:博客园 阅读 ()
AVL就是优化二叉查找树
平衡因子不大于1
左 < 根 < 右
具体看代码
#include<bits/stdc++.h> using namespace std; typedef struct node; typedef node * tree; struct node { int v; int heigh; tree L,R; }; //获取以root为根结点的子树的当前height int getheigh(tree root) { if(root==NULL) return 0; return root->heigh; } //更新结点root的heigh void updataheigh(tree root) { //max(左孩子结点的height,有孩子结点的height)+1 root->heigh=max(getheigh(root->L),getheigh(root->R))+1; } //计算平衡因子 int getBalance(tree root) { //左-右 return getheigh(root->L)-getheigh(root->R); } //左旋 注意原理 对于RR是root的右孩子的平衡因子是-1 void L(tree &root) { tree temp; temp=root->R; root->R=temp->L; temp->L=root; updataheigh(root); updataheigh(temp); root=temp; } void R(tree &root) { tree temp; temp=root->L; root->L=temp->R; temp->R=root; updataheigh(root); updataheigh(temp); root=temp; } void insertt(tree &root,int v) { if(root==NULL){//当结点是空的时候 就是插入的时候 root=new node; root->v=v; root->heigh=1; root->L=root->R=NULL; return; } if(v<root->v){ insertt(root->L,v); updataheigh(root);//注意更新树高 if(getBalance(root)==2){ if(getBalance(root->L)==1){ R(root); } else if(getBalance(root->L)==-1){ L(root->L); R(root); } } } else{ insertt(root->R,v); updataheigh(root); if(getBalance(root)==-2){ if(getBalance(root->R)==-1){ L(root); } else if(getBalance(root->R)==1){ R(root->R); L(root); } } } } int main() { int n; scanf("%d",&n); int x; tree root; root=NULL; for(int i=0;i<n;i++){ scanf("%d",&x); insertt(root,x); } printf("%d\n",root->v); return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:c++简单学习
下一篇:学习 Qt 编程的好书精品推荐!
- 二叉搜索树_BST 2020-05-30
- 二叉树 2020-05-02
- 二叉排序树 2020-05-02
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 二叉堆(3)SkewHeap 2020-02-20
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash