来自  资质荣誉 2019-09-22 00:30 的文章
当前位置: 澳门太阳娱乐手机登录 > 资质荣誉 > 正文

平衡二叉树,二叉平衡树

平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树

图片 1

都是排序二叉树,但是查找的93节点就供给搜索6次,查找的93节点就供给研究3次,所以的功效不高。

平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称AVL树。它依然是一颗空树,或许是具备下列性质的二叉树:它的左子树和右子树的纵深只差的相对值不超越1。若将二叉树上节点的平衡因子BF(Balance Factor)定义为该节点的左子树的深浅减去它右子树的深浅,则平衡二叉树上全体节点的平衡因子只恐怕是-1,0,1。只要二叉树上有四个节点的平衡因子的断然值超越1,则该二叉树正是不平衡的。

图片 2

上海体育场所是平衡二叉树,不是平衡二叉树,因为某个节点的平衡因子大于1了。

平衡二叉树(Balanced Binary Tree)又被称之为AVL(Adelson-Velskii and Landis)树,是包涵平衡条件(balance condition)的二叉查找树。

布置节点的差不离思路:

  • 第一找到插入节点的职责,插入节点
  • 布置节点后,调度有关节点的平衡因子
  • 调节平衡因子后,倘诺发掘树不平衡了,就要举行节点的调节(单左旋转,或单右旋转,或双转悠(先左后又,大概先右后左)。

avl_tree.h

#ifndef __AVLTREE__#define __AVLTREE__#include<stdio.h>#include<malloc.h>#include<assert.h>#include "nodestack.h"#define Type int#define FALSE 0#define TRUE 1#define BOOL inttypedef struct AVLNode{  Type data;  struct AVLNode* left;  struct AVLNode* right;  int bf;//平衡因子}AVLNode;typedef struct AVLTree{  struct AVLNode* root;}AVLTree;void init_avl_tree(AVLTree* avl);//插入节点BOOL insert_avl(AVLTree* avl, Type t);#endif

avl_tree.c

#include "avl_tree.h"void init_avl_tree(AVLTree* avl){  avl->root = NULL;}AVLNode* malNode{    AVLNode* t = malloc(sizeof;    assert(NULL != t);    t->data  = x;    t->left  = NULL;    t->right = NULL;    t->bf    = 0;    return t;}//右旋转void rotateR(AVLNode** t){  AVLNode* subR = *t;  *t = ->left;  subR->left = ->right;  ->right = subR;  ->bf = 0;  subR->bf = 0;}//左旋转void rotateL(AVLNode** t){  AVLNode* subL = *t;  *t = ->right;  subL->right = ->left;  ->left = subL;  ->bf = 0;  subL->bf = 0;}//左右旋转void rotateLR(AVLNode** t){  AVLNode* subR = *t;  AVLNode* subL = subR->left;  *t = subL->right;  subL->right = ->left;  ->left = subL;  if->bf <= 0){///??    subL->bf = 0;  }  else{    subL->bf = -1;  }  subR->left = ->right;  ->right = subR;  if->bf == -1){    subR->bf = 1;//???  }  else{    subR->bf = 0;//???  }  ->bf = 0;  }//右左旋转void rotateRL(AVLNode** t){  AVLNode* subL = *t;  AVLNode* subR = subL->right;  *t = subR->left;    subR->left = ->right;  ->right = subR;  if->bf >= 0){    subR->bf = 0;  }  else{    subR->bf = 1;  }  subL->right = ->left;  ->left = subL;  if->bf == 1){    subL->bf = -1;  }  else{    subL->bf = 0;  }  ->bf = 0;}//插入树的节点BOOL insert_avl_node(AVLNode** t, Type x){  AVLNode* p = *t;  AVLNode* parent = NULL;  nodestack st;  init;    while(p != NULL){    if(x == p->data)      return FALSE;    parent = p;    push(&st, parent);    if(x < p->data)      p = p->left;    else      p = p->right;  }  p = malNode;  //插入节点为root节点  if(parent == NULL){    *t = p;    return TRUE;  }  //插入节点不是root节点  if(x < parent->data)    parent->left = p;  else    parent->right = p;  //调整BF  while(length != 0){    parent = getTop;    pop;    if(parent->left == p){      parent->bf--;    }    else{      parent->bf++;    }        if(parent->bf == 0){      break;    }    if(parent->bf == 1 || parent->bf == -1){      p = parent;    }    else{      //旋转树,让树变成平衡树      int flag = (parent->bf < 0) ? -1 : 1;      //符号相同,说明是一条直线,不是折线,所以单旋转      if(p->bf == flag){    //因为是撇/,所以右旋转    if(flag == -1){      rotateR(&parent);    }    //因为是捺,所以左旋转    else{      rotateL(&parent);    }      }      //符号不同,说明是折线,所以双旋转      else{    //折线的角指向右>    if(flag == 1){      rotateRL(&parent);    }    //折线的角指向左<    else{      rotateLR(&parent);    }      }      break;    }  }      if(length == 0){    *t = parent;  }  else{    AVLNode* q = getTop;    if(q->data > parent->data){      q->left = parent;    }    else{      q->right = parent;    }  }    clear;  return TRUE;}//插入节点BOOL insert_avl(AVLTree* avl, Type t){  return insert_avl_node(&avl->root, t);}

avl_treemain.c

#include "avl_tree.h"int main(){  AVLTree avl;  init_avl_tree;  //Type ar[] = {13,24,37,90,53};  //Type ar[] = {30,20,10};    //Type ar[] = {30,20,40,10,25,5,22,28,21};    //Type ar[] = {30,20,10};  //Type ar[] = {50,40,60,10,45,70,5,30,20,12};  Type ar[] = {30,20,50,10,40,70,60,80,55};  int n = sizeof / sizeof;  for(int i = 0; i < n; ++i){    insert_avl(&avl, ar[i]);  }  return 0;}

完整代码

编写翻译方法:g++ -g nodestack.c avl_tree.c avl_treemain.c

性质

它依然是空树,或者负有下列性质

  • 它的左右七个子树的冲天差的相对值不超过1
  • 它的左右七个子树都以平衡二叉树
  • 拥有二叉排序树的性质
术语
  • 平衡因子:某结点的左子树与右子树的可观(深度)差即为该结点的平衡因子(BF,Balance Factor)。
    平衡二叉树上全体结点的平衡因子只可能是 -1,0 或 1。
  • 结点中度定义:空结点的莫斯中国科学技术大学学为0;非空结点的莫斯中国科学技术大学学为以该结点为根结点的树的惊人。
  • 微小不平衡子树: 以离插入结点这段日子,且平衡因子相对值大于1的结点作为根结点的树。
  • 旋转:对小小不平衡树进行调节的操作
规则
  • 行使二叉链表的协会实行仓库储存
  • 结构体中追加结点的万丈,用以总结结点的平衡因子
  • 插入节点的惊人为0,并恐怕导致树失去平衡需求调动平衡
  • 除去节点,调节成叶子节点后去除(左子树最大依然右子树最小),删除后或然导致树失去平衡须求调动平衡
旋转
  • 右旋
       4                                2
      /           节点4右旋转           / 
     2          ------------->         1  4
    /                                    /
   1  3                                  3
  • 左旋
    5 7
    结点5左旋转 /
    7 --------------> 5 8
    /
    6 8 6
平衡决断

4种旋转方式:LL型,LR型,RL型,RR型

  • LL型(右旋)
    当根结点左子树的左子树中的节点导致根结点的平衡因子为2时,采纳LL型旋转进行调度。

  • RR型(左旋)
    当根结点右子树的右子树中的节点导致根结点的平衡因子为-2时,采纳锐界本田UR-V型旋转进行调节。

  • LR型(先左旋,再右旋)
    当根结点左子树的右子树中的节点导致根结点的平衡因子为2时,接纳LLAND型旋转实行调治。

  • RL型(先右旋,再左旋)
    当根结点右子树的左子树中的节点导致根结点的平衡因子为-2时,采纳GL450L型旋转进行调节。

实现
  • 数据结构
typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node * left;
    struct Node * right;
    int height;
} AVLNode, * AVLTree;
  • 函数
int GetHeight(AVLTree T)
int LLRotate(AVLTree  T)
int RRRotate(AVLTree  T)
int LRRotate(AVLTree  T)
int RLRotate(AVLTree  T)
int AVLInsert(AVLTree  T, DataType key)
int AVLDelete(AVLTree T, DataType key)
链接:
  • 《数据结构与算法分析:C语言描述(原书第3版)》
  • http://www.cnblogs.com/Camilo/p/3917041.html

本文由澳门太阳娱乐手机登录发布于 资质荣誉,转载请注明出处:平衡二叉树,二叉平衡树

关键词: