数据结构,图文解析

[javaSE] 数据结构(AVL树基本概念),javaseavl

AVL树是莫斯科大学平衡的二叉树,任何节点的四个子树的中度差距<=1

 

实现AVL树

概念三个AVL树,AVLTree,定义AVLTree的节点内部类AVLNode,节点包蕴以下特点:

1.key——关键字,对AVL树的节点举办排序

2.left——左子树

3.right——右子树

4.height——高度

 

假若在AVL树插入节点后或者导致AVL树失衡,具体会有二种境况:

LL:左左,LeftLeft

LR:左右,LeftRight

RL:右左,RightLeft

RR:右右,RightRight

 

竭泽而渔地方的境况

解决LL,须要左单旋转

涸泽而渔陆风X8Evoque,须求右单旋转

减轻LRAV4,要求先右单旋转,再左单旋转

消除福特ExplorerL,需求先左单旋转,再右单旋转

 

福如东海左单旋转

图片 1

 

 

k1,k2

k2的left给k1

k1的right给k2的left

k2给k1的right

 

兑现右单旋转

k1,k2

k1的right给k2

k2的left给k1的right

k1给k2的left

图片 2

 

 

 

节点的莫斯科大学,是它左子树也许右子树中,中度大的充裕 再加1

 

/**
 * AVL树测试
 * @author taoshihan
 * @param <T>
 *
 */
public class AVLTree<T extends Comparable<T>> {
    private AVLNode mRoot;//根节点
    class AVLNode<T extends Comparable<T>>{
        private T key;//键值
        private int height;//高度
        private AVLNode left;//左子树
        private AVLNode right;//右子树
        public AVLNode(T key,AVLNode left,AVLNode right) {
            this.key=key;
            this.left=left;
            this.right=right;
            this.height=0;
        }
    }
    /**
     * 获取节点高度
     * @param tree
     * @return
     */
    public int height(AVLNode<T> tree){
        if(tree!=null){
            return tree.height;
        }
        return 0;
    }
    /**
     * 取出左右子树中高的那个
     * @param a
     * @param b
     * @return
     */
    public int maxHeight(int a,int b){
        return a>b ? a : b;
    }
    /**
     * 左单旋转
     * @param k2
     * @return
     */
    public AVLNode<T> leftLeftRotation(AVLNode<T> k2){
        AVLNode k1;
        k1 = k2.left;
        k2.left=k1.right;
        k1.right=k2;
        k2.height=maxHeight(height(k2.left), height(k2.right));
        k1.height=maxHeight(height(k1.left), height(k1.right));
        return k1;
    }
    /**
     * 右单旋转
     * @param k2
     * @return
     */
    public AVLNode<T> rightRightRotation(AVLNode<T> k1){
        AVLNode k2;
        k2=k1.right;
        k1.right=k2.left;
        k2.left=k1;

        k2.height=maxHeight(height(k2.left), height(k2.right));
        k1.height=maxHeight(height(k1.left), height(k1.right));
        return k2;
    }

 

 

 

] 数据结构(AVL树基本概念),javaseavl
AVL 树是惊人平衡的二叉树,任何节点的多个子树的莫斯中国科学技术大学学差距 =1 落到实处 AVL 树
定义七个 AVL 树,…

k1,k2

AVL树的C完成(完整源码)

AVL树的头文件(avltree.h)

图片 3图片 4

 1 #ifndef _AVL_TREE_H_   2 #define _AVL_TREE_H_   3    4 typedef int Type;   5    6 typedef struct AVLTreeNode{   7     Type key;                    // 关键字(键值)   8     int height;   9     struct AVLTreeNode *left;    // 左孩子  10     struct AVLTreeNode *right;    // 右孩子  11 }Node, *AVLTree;  12   13 // 获取AVL树的高度  14 int avltree_height(AVLTree tree);  15   16 // 前序遍历"AVL树"  17 void preorder_avltree(AVLTree tree);  18 // 中序遍历"AVL树"  19 void inorder_avltree(AVLTree tree);  20 // 后序遍历"AVL树"  21 void postorder_avltree(AVLTree tree);  22   23 void print_avltree(AVLTree tree, Type key, int direction);  24   25 // (递归实现)查找"AVL树x"中键值为key的节点  26 Node* avltree_search(AVLTree x, Type key);  27 // (非递归实现)查找"AVL树x"中键值为key的节点  28 Node* iterative_avltree_search(AVLTree x, Type key);  29   30 // 查找最小结点:返回tree为根结点的AVL树的最小结点。  31 Node* avltree_minimum(AVLTree tree);  32 // 查找最大结点:返回tree为根结点的AVL树的最大结点。  33 Node* avltree_maximum(AVLTree tree);  34   35 // 将结点插入到AVL树中,返回根节点  36 Node* avltree_insert(AVLTree tree, Type key);  37   38 // 删除结点(key是节点值),返回根节点  39 Node* avltree_delete(AVLTree tree, Type key);  40   41 // 销毁AVL树  42 void destroy_avltree(AVLTree tree);  43   44   45 #endif

View Code

AVL树的贯彻公文(avltree.c)

图片 5图片 6

  1 /**    2  * AVL树(C语言): C语言实现的AVL树。    3  *    4  * @author skywang    5  * @date 2013/11/07    6  */    7     8 #include <stdio.h>    9 #include <stdlib.h>   10 #include "avltree.h"   11    12 #define HEIGHT(p)    ( (p==NULL) ? -1 : (((Node *)(p))->height) )   13 #define MAX(a, b)    ( (a) > (b) ? (a) : (b) )   14    15 /*   16  * 获取AVL树的高度   17  */   18 int avltree_height(AVLTree tree)   19 {   20     return HEIGHT(tree);   21 }   22    23 /*   24  * 前序遍历"AVL树"   25  */   26 void preorder_avltree(AVLTree tree)   27 {   28     if(tree != NULL)   29     {   30         printf("%d ", tree->key);   31         preorder_avltree(tree->left);   32         preorder_avltree(tree->right);   33     }   34 }   35    36    37 /*   38  * 中序遍历"AVL树"   39  */   40 void inorder_avltree(AVLTree tree)   41 {   42     if(tree != NULL)   43     {   44         inorder_avltree(tree->left);   45         printf("%d ", tree->key);   46         inorder_avltree(tree->right);   47     }   48 }   49    50 /*   51  * 后序遍历"AVL树"   52  */   53 void postorder_avltree(AVLTree tree)   54 {   55     if(tree != NULL)   56     {   57         postorder_avltree(tree->left);   58         postorder_avltree(tree->right);   59         printf("%d ", tree->key);   60     }   61 }   62    63 /*   64  * (递归实现)查找"AVL树x"中键值为key的节点   65  */   66 Node* avltree_search(AVLTree x, Type key)   67 {   68     if (x==NULL || x->key==key)   69         return x;   70    71     if (key < x->key)   72         return avltree_search(x->left, key);   73     else   74         return avltree_search(x->right, key);   75 }   76    77 /*   78  * (非递归实现)查找"AVL树x"中键值为key的节点   79  */   80 Node* iterative_avltree_search(AVLTree x, Type key)   81 {   82     while ((x!=NULL) && (x->key!=key))   83     {   84         if (key < x->key)   85             x = x->left;   86         else   87             x = x->right;   88     }   89    90     return x;   91 }   92    93 /*    94  * 查找最小结点:返回tree为根结点的AVL树的最小结点。   95  */   96 Node* avltree_minimum(AVLTree tree)   97 {   98     if (tree == NULL)   99         return NULL;  100   101     while(tree->left != NULL)  102         tree = tree->left;  103     return tree;  104 }  105    106 /*   107  * 查找最大结点:返回tree为根结点的AVL树的最大结点。  108  */  109 Node* avltree_maximum(AVLTree tree)  110 {  111     if (tree == NULL)  112         return NULL;  113   114     while(tree->right != NULL)  115         tree = tree->right;  116     return tree;  117 }  118   119 /*  120  * LL:左左对应的情况(左单旋转)。  121  *  122  * 返回值:旋转后的根节点  123  */  124 static Node* left_left_rotation(AVLTree k2)  125 {  126     AVLTree k1;  127   128     k1 = k2->left;  129     k2->left = k1->right;  130     k1->right = k2;  131   132     k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;  133     k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;  134   135     return k1;  136 }  137   138 /*  139  * RR:右右对应的情况(右单旋转)。  140  *  141  * 返回值:旋转后的根节点  142  */  143 static Node* right_right_rotation(AVLTree k1)  144 {  145     AVLTree k2;  146   147     k2 = k1->right;  148     k1->right = k2->left;  149     k2->left = k1;  150   151     k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;  152     k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;  153   154     return k2;  155 }  156   157 /*  158  * LR:左右对应的情况(左双旋转)。  159  *  160  * 返回值:旋转后的根节点  161  */  162 static Node* left_right_rotation(AVLTree k3)  163 {  164     k3->left = right_right_rotation(k3->left);  165   166     return left_left_rotation(k3);  167 }  168   169 /*  170  * RL:右左对应的情况(右双旋转)。  171  *  172  * 返回值:旋转后的根节点  173  */  174 static Node* right_left_rotation(AVLTree k1)  175 {  176     k1->right = left_left_rotation(k1->right);  177   178     return right_right_rotation(k1);  179 }  180   181 /*  182  * 创建AVL树结点。  183  *  184  * 参数说明:  185  *     key 是键值。  186  *     left 是左孩子。  187  *     right 是右孩子。  188  */  189 static Node* avltree_create_node(Type key, Node *left, Node* right)  190 {  191     Node* p;  192   193     if ((p = (Node *)malloc(sizeof(Node))) == NULL)  194         return NULL;  195     p->key = key;  196     p->height = 0;  197     p->left = left;  198     p->right = right;  199   200     return p;  201 }  202   203 /*   204  * 将结点插入到AVL树中,并返回根节点  205  *  206  * 参数说明:  207  *     tree AVL树的根结点  208  *     key 插入的结点的键值  209  * 返回值:  210  *     根节点  211  */  212 Node* avltree_insert(AVLTree tree, Type key)  213 {  214     if (tree == NULL)   215     {  216         // 新建节点  217         tree = avltree_create_node(key, NULL, NULL);  218         if (tree==NULL)  219         {  220             printf("ERROR: create avltree node failed!\n");  221             return NULL;  222         }  223     }  224     else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况  225     {  226         tree->left = avltree_insert(tree->left, key);  227         // 插入节点后,若AVL树失去平衡,则进行相应的调节。  228         if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)  229         {  230             if (key < tree->left->key)  231                 tree = left_left_rotation(tree);  232             else  233                 tree = left_right_rotation(tree);  234         }  235     }  236     else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况  237     {  238         tree->right = avltree_insert(tree->right, key);  239         // 插入节点后,若AVL树失去平衡,则进行相应的调节。  240         if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)  241         {  242             if (key > tree->right->key)  243                 tree = right_right_rotation(tree);  244             else  245                 tree = right_left_rotation(tree);  246         }  247     }  248     else //key == tree->key)  249     {  250         printf("添加失败:不允许添加相同的节点!\n");  251     }  252   253     tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;  254   255     return tree;  256 }  257   258 /*   259  * 删除结点(z),返回根节点  260  *  261  * 参数说明:  262  *     ptree AVL树的根结点  263  *     z 待删除的结点  264  * 返回值:  265  *     根节点  266  */  267 static Node* delete_node(AVLTree tree, Node *z)  268 {  269     // 根为空 或者 没有要删除的节点,直接返回NULL。  270     if (tree==NULL || z==NULL)  271         return NULL;  272   273     if (z->key < tree->key)        // 待删除的节点在"tree的左子树"中  274     {  275         tree->left = delete_node(tree->left, z);  276         // 删除节点后,若AVL树失去平衡,则进行相应的调节。  277         if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)  278         {  279             Node *r =  tree->right;  280             if (HEIGHT(r->left) > HEIGHT(r->right))  281                 tree = right_left_rotation(tree);  282             else  283                 tree = right_right_rotation(tree);  284         }  285     }  286     else if (z->key > tree->key)// 待删除的节点在"tree的右子树"中  287     {  288         tree->right = delete_node(tree->right, z);  289         // 删除节点后,若AVL树失去平衡,则进行相应的调节。  290         if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)  291         {  292             Node *l =  tree->left;  293             if (HEIGHT(l->right) > HEIGHT(l->left))  294                 tree = left_right_rotation(tree);  295             else  296                 tree = left_left_rotation(tree);  297         }  298     }  299     else    // tree是对应要删除的节点。  300     {  301         // tree的左右孩子都非空  302         if ((tree->left) && (tree->right))  303         {  304             if (HEIGHT(tree->left) > HEIGHT(tree->right))  305             {  306                 // 如果tree的左子树比右子树高;  307                 // 则(01)找出tree的左子树中的最大节点  308                 //   (02)将该最大节点的值赋值给tree。  309                 //   (03)删除该最大节点。  310                 // 这类似于用"tree的左子树中最大节点"做"tree"的替身;  311                 // 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。  312                 Node *max = avltree_maximum(tree->left);  313                 tree->key = max->key;  314                 tree->left = delete_node(tree->left, max);  315             }  316             else  317             {  318                 // 如果tree的左子树不比右子树高(即它们相等,或右子树比左子树高1)  319                 // 则(01)找出tree的右子树中的最小节点  320                 //   (02)将该最小节点的值赋值给tree。  321                 //   (03)删除该最小节点。  322                 // 这类似于用"tree的右子树中最小节点"做"tree"的替身;  323                 // 采用这种方式的好处是:删除"tree的右子树中最小节点"之后,AVL树仍然是平衡的。  324                 Node *min = avltree_maximum(tree->right);  325                 tree->key = min->key;  326                 tree->right = delete_node(tree->right, min);  327             }  328         }  329         else  330         {  331             Node *tmp = tree;  332             tree = tree->left ? tree->left : tree->right;  333             free(tmp);  334         }  335     }  336   337     return tree;  338 }  339   340 /*   341  * 删除结点(key是节点值),返回根节点  342  *  343  * 参数说明:  344  *     tree AVL树的根结点  345  *     key 待删除的结点的键值  346  * 返回值:  347  *     根节点  348  */  349 Node* avltree_delete(AVLTree tree, Type key)  350 {  351     Node *z;   352   353     if ((z = avltree_search(tree, key)) != NULL)  354         tree = delete_node(tree, z);  355     return tree;  356 }  357   358 /*   359  * 销毁AVL树  360  */  361 void destroy_avltree(AVLTree tree)  362 {  363     if (tree==NULL)  364         return ;  365   366     if (tree->left != NULL)  367         destroy_avltree(tree->left);  368     if (tree->right != NULL)  369         destroy_avltree(tree->right);  370   371     free(tree);  372 }  373   374 /*  375  * 打印"AVL树"  376  *  377  * tree       -- AVL树的节点  378  * key        -- 节点的键值   379  * direction  --  0,表示该节点是根节点;  380  *               -1,表示该节点是它的父结点的左孩子;  381  *                1,表示该节点是它的父结点的右孩子。  382  */  383 void print_avltree(AVLTree tree, Type key, int direction)  384 {  385     if(tree != NULL)  386     {  387         if(direction==0)    // tree是根节点  388             printf("%2d is root\n", tree->key, key);  389         else                // tree是分支节点  390             printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");  391   392         print_avltree(tree->left, tree->key, -1);  393         print_avltree(tree->right,tree->key,  1);  394     }  395 }

View Code

AVL树的测量检验程序(avltree_test.c) 

图片 7图片 8

 1 /**   2  * C 语言: AVL树   3  *   4  * @author skywang   5  * @date 2013/11/07   6  */   7 #include <stdio.h>   8 #include "avltree.h"   9   10 static int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};  11 #define TBL_SIZE(a) ( (sizeof(a)) / (sizeof(a[0])) )  12   13 void main()  14 {  15     int i,ilen;  16     AVLTree root=NULL;  17   18     printf("== 高度: %d\n", avltree_height(root));  19     printf("== 依次添加: ");  20     ilen = TBL_SIZE(arr);  21     for(i=0; i<ilen; i++)  22     {  23         printf("%d ", arr[i]);  24         root = avltree_insert(root, arr[i]);  25     }  26   27     printf("\n== 前序遍历: ");  28     preorder_avltree(root);  29   30     printf("\n== 中序遍历: ");  31     inorder_avltree(root);  32   33     printf("\n== 后序遍历: ");  34     postorder_avltree(root);  35     printf("\n");  36   37     printf("== 高度: %d\n", avltree_height(root));  38     printf("== 最小值: %d\n", avltree_minimum(root)->key);  39     printf("== 最大值: %d\n", avltree_maximum(root)->key);  40     printf("== 树的详细信息: \n");  41     print_avltree(root, root->key, 0);  42   43   44     i = 8;  45     printf("\n== 删除根节点: %d", i);  46     root = avltree_delete(root, i);  47   48     printf("\n== 高度: %d", avltree_height(root));  49     printf("\n== 中序遍历: ");  50     inorder_avltree(root);  51     printf("\n== 树的详细信息: \n");  52     print_avltree(root, root->key, 0);  53   54     // 销毁二叉树  55     destroy_avltree(root);  56 }

View Code

 

RL:右左,RightLeft

概要

本章介绍AVL树。和后面介绍”二叉查找树”的流程同样,本章先对AVL树的理论知识实行简易介绍,然后交由C语言的落到实处。本篇完结的二叉查找树是C语言版的,前边章节再分别交付C++和Java版本的兑现。
提议:若您对”二叉查找树”不熟知,建议先学完”二叉查找树”再来学习AVL树。

目录

1. AVL树的介绍
2. AVL树的C实现
3. AVL树的C完结(完整源码)
4. AVL树的C测量试验程序

转发请表明出处:


越来越多内容: 数据结构与算法连串 目录 

(01) AVL树(一)之 图像和文字剖判 和 C语言的兑现
(02) AVL树(二)之 C++的实现
(03) AVL树(三)之 Java的实现

 

 

AVL树的C实现

1. 节点

1.1 定义

typedef int Type;    typedef struct AVLTreeNode{      Type key;                    // 关键字(键值)      int height;      struct AVLTreeNode *left;    // 左孩子      struct AVLTreeNode *right;    // 右孩子  }Node, *AVLTree;

AVL树的节点包蕴的多少个组成对象:
(01) key — 是器重字,是用来对AVL树的节点开始展览排序的。
(02) left — 是左孩子。
(03) right — 是右孩子。
(04) height — 是高度。

 

1.2 节点的创办

/*   * 创建AVL树结点。   *   * 参数说明:   *     key 是键值。   *     left 是左孩子。   *     right 是右孩子。   */  static Node* avltree_create_node(Type key, Node *left, Node* right)  {      Node* p;        if ((p = (Node *)malloc(sizeof(Node))) == NULL)          return NULL;      p->key = key;      p->height = 0;      p->left = left;      p->right = right;        return p;  }

 

1.3 树的万丈

#define HEIGHT(p)    ( (p==NULL) ? 0 : (((Node *)(p))->height) )    /*   * 获取AVL树的高度   */  int avltree_height(AVLTree tree)  {      return HEIGHT(tree);  }

关于中度,有的小说上校”空二叉树的冲天定义为-1″,而本文采用维基百科上的概念:树的万丈为最大等级次序。即空的二叉树的中度是0,非空树的莫斯中国科学技术大学学等于它的最大档期的顺序(根的层系为1,根的子节点为第2层,依次类推)。

 

1.4 非常的大小

#define MAX(a, b)    ( (a) > (b) ? (a) : (b) )

 

2. 旋转
前边说过,如若在AVL树中展开插队或删除节点后,可能导致AVL树失衡。这种失衡的可以包涵为4种态度:LL(左左),L传祺(左右),福特Explorer奥迪Q5(右右)和君越L(右左)。下边给出它们的暗意图:

图片 9

上海教室中的4棵树都是”失衡的AVL树”,从左往右的情景种种是:LL、LOdyssey、索罗德L、CR-VTiguan。除了下面的场所之外,还应该有别的的失衡的AVL树,如下图:

图片 10
地方的两张图都认为着便于精通,而列举的关于”失衡的AVL树”的例证。总的来讲,AVL树失衡时的事态自然是LL、L奥迪Q5、大切诺基L、普拉多Evoque那4种之一,它们都由各自的概念:

(1)
LL:LeftLeft,也可以称作”左左”。插入或删除叁个节点后,根节点的左子树的左子树还恐怕有非空子节点,导致”根的左子树的惊人”比”根的右子树的可观”大2,导致AVL树失去了平衡。
   
 诸如,在上头LL情状中,由于”根节点(8)的左子树(4)的左子树(2)还也许有非空子节点”,而”根节点(8)的右子树(12)未有子节点”;导致”根节点(8)的左子树(4)中度”比”根节点(8)的右子树(12)”高2。

(2)
LR:LeftRight,也堪当”左右”。插入或删除三个节点后,根节点的左子树的右子树还会有非空子节点,导致”根的左子树的冲天”比”根的右子树的冲天”大2,导致AVL树失去了平衡。
   
 比如,在地点L冠道景况中,由于”根节点(8)的左子树(4)的左子树(6)还应该有非空子节点”,而”根节点(8)的右子树(12)未有子节点”;导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(3)
RL:RightLeft,称为”右左”。插入或删除二个节点后,根节点的右子树的左子树还也可能有非空子节点,导致”根的右子树的万丈”比”根的左子树的高度”大2,导致AVL树失去了平衡。
   
 举例,在上头大切诺基L意况中,由于”根节点(8)的右子树(12)的左子树(10)还应该有非空子节点”,而”根节点(8)的左子树(4)未有子节点”;导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

(4)
RR:RightRight,称为”右右”。插入或删除一个节点后,根节点的右子树的右子树还恐怕有非空子节点,导致”根的右子树的莫斯科大学”比”根的左子树的惊人”大2,导致AVL树失去了平衡。
   
 举个例子,在上边LAND智跑景况中,由于”根节点(8)的右子树(12)的右子树(14)还应该有非空子节点”,而”根节点(8)的左子树(4)未有子节点”;导致”根节点(8)的右子树(12)中度”比”根节点(8)的左子树(4)”高2。

日前说过,如若在AVL树中举行插队或删除节点后,可能引致AVL树失去平衡。AVL失衡之后,能够通过旋转使其回复平衡,上面分别介绍”LL(左左),LEvoque(左右),大切诺基科雷傲(右右)和福睿斯L(右左)”那4种景况相应的团团转格局。

 

2.1 LL的旋转

LL失衡的情形,能够通过二遍旋转让AVL树苏醒平衡。如下图:

图片 11

图中侧面是旋转之前的树,侧边是旋转之后的树。从中能够窥见,旋转之后的树又改为了AVL树,並且该旋转只供给贰回就可以完结。
对于LL旋转,你能够那样敞亮为:LL旋转是环绕”失衡的AVL根节点”进行的,也正是节点k2;并且由于是LL情状,即左左意况,就用手抓着”左孩子,即k1″使劲摇。将k1形成根节点,k2产生k1的右子树,”k1的右子树”形成”k2的左子树”。

LL的团团转代码

/*   * LL:左左对应的情况(左单旋转)。   *   * 返回值:旋转后的根节点   */  static Node* left_left_rotation(AVLTree k2)  {      AVLTree k1;        k1 = k2->left;      k2->left = k1->right;      k1->right = k2;        k2->height = MAX( HEIGHT(k2->left), HEIGHT(k2->right)) + 1;      k1->height = MAX( HEIGHT(k1->left), k2->height) + 1;        return k1;  }

 

2.2 RR的旋转

了解了LL之后,科雷傲中华V就卓绝容易领悟了。GranCabrio奥迪Q3是与LL对称的情况!CRUISERPAJERO苏醒平衡的转动方式如下:

图片 12

图中左侧是旋转在此之前的树,右侧是旋转之后的树。LANDR旋转也只要求一回就可以成功。

 

Qashqai科雷傲的团团转代码

/*   * RR:右右对应的情况(右单旋转)。   *   * 返回值:旋转后的根节点   */  static Node* right_right_rotation(AVLTree k1)  {      AVLTree k2;        k2 = k1->right;      k1->right = k2->left;      k2->left = k1;        k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;      k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;        return k2;  }

 

2.3 LR的旋转

LEnclave失衡的景观,须要通过四回旋转技术让AVL树苏醒平衡。如下图:

图片 13
首次旋转是环绕”k1″进行的”ENVISIONPRADO旋转”,第一遍是围绕”k3″实行的”LL旋转”。

 

LQX56的团团转代码

/*   * LR:左右对应的情况(左双旋转)。   *   * 返回值:旋转后的根节点   */  static Node* left_right_rotation(AVLTree k3)  {      k3->left = right_right_rotation(k3->left);        return left_left_rotation(k3);  }

 

2.4 RL的旋转
冠道L是与L中华V的集思广益意况!福睿斯L苏醒平衡的团团转方式如下:

图片 14

率先次旋转是环绕”k3″进行的”LL旋转”,第壹遍是环绕”k1″实行的”昂科雷锐界旋转”。

途乐L的旋转代码

/*   * RL:右左对应的情况(右双旋转)。   *   * 返回值:旋转后的根节点   */  static Node* right_left_rotation(AVLTree k1)  {      k1->right = left_left_rotation(k1->right);        return right_right_rotation(k1);  }

3. 插入
安排节点的代码

/*    * 将结点插入到AVL树中,并返回根节点   *   * 参数说明:   *     tree AVL树的根结点   *     key 插入的结点的键值   * 返回值:   *     根节点   */  Node* avltree_insert(AVLTree tree, Type key)  {      if (tree == NULL)       {          // 新建节点          tree = avltree_create_node(key, NULL, NULL);          if (tree==NULL)          {              printf("ERROR: create avltree node failed!\n");              return NULL;          }      }      else if (key < tree->key) // 应该将key插入到"tree的左子树"的情况      {          tree->left = avltree_insert(tree->left, key);          // 插入节点后,若AVL树失去平衡,则进行相应的调节。          if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)          {              if (key < tree->left->key)                  tree = left_left_rotation(tree);              else                  tree = left_right_rotation(tree);          }      }      else if (key > tree->key) // 应该将key插入到"tree的右子树"的情况      {          tree->right = avltree_insert(tree->right, key);          // 插入节点后,若AVL树失去平衡,则进行相应的调节。          if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)          {              if (key > tree->right->key)                  tree = right_right_rotation(tree);              else                  tree = right_left_rotation(tree);          }      }      else //key == tree->key)      {          printf("添加失败:不允许添加相同的节点!\n");      }        tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;        return tree;  }

 

4. 删除
删除节点的代码

/*    * 删除结点(z),返回根节点   *   * 参数说明:   *     ptree AVL树的根结点   *     z 待删除的结点   * 返回值:   *     根节点   */  static Node* delete_node(AVLTree tree, Node *z)  {      // 根为空 或者 没有要删除的节点,直接返回NULL。      if (tree==NULL || z==NULL)          return NULL;        if (z->key < tree->key)        // 待删除的节点在"tree的左子树"中      {          tree->left = delete_node(tree->left, z);          // 删除节点后,若AVL树失去平衡,则进行相应的调节。          if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)          {              Node *r =  tree->right;              if (HEIGHT(r->left) > HEIGHT(r->right))                  tree = right_left_rotation(tree);              else                  tree = right_right_rotation(tree);          }      }      else if (z->key > tree->key)// 待删除的节点在"tree的右子树"中      {          tree->right = delete_node(tree->right, z);          // 删除节点后,若AVL树失去平衡,则进行相应的调节。          if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)          {              Node *l =  tree->left;              if (HEIGHT(l->right) > HEIGHT(l->left))                  tree = left_right_rotation(tree);              else                  tree = left_left_rotation(tree);          }      }      else    // tree是对应要删除的节点。      {          // tree的左右孩子都非空          if ((tree->left) && (tree->right))          {              if (HEIGHT(tree->left) > HEIGHT(tree->right))              {                  // 如果tree的左子树比右子树高;                  // 则(01)找出tree的左子树中的最大节点                  //   (02)将该最大节点的值赋值给tree。                  //   (03)删除该最大节点。                  // 这类似于用"tree的左子树中最大节点"做"tree"的替身;                  // 采用这种方式的好处是:删除"tree的左子树中最大节点"之后,AVL树仍然是平衡的。                  Node *max = avltree_maximum(tree->left);                  tree->key = max->key;                  tree->left = delete_node(tree->left, max);              }              else              {                  // 如果tree的左子树不比右子树高(即它们相等,或右子树比左子树高1)                  // 则(01)找出tree的右子树中的最小节点                  //   (02)将该最小节点的值赋值给tree。                  //   (03)删除该最小节点。                  // 这类似于用"tree的右子树中最小节点"做"tree"的替身;                  // 采用这种方式的好处是:删除"tree的右子树中最小节点"之后,AVL树仍然是平衡的。                  Node *min = avltree_maximum(tree->right);                  tree->key = min->key;                  tree->right = delete_node(tree->right, min);              }          }          else          {              Node *tmp = tree;              tree = tree->left ? tree->left : tree->right;              free(tmp);          }      }        return tree;  }    /*    * 删除结点(key是节点值),返回根节点   *   * 参数说明:   *     tree AVL树的根结点   *     key 待删除的结点的键值   * 返回值:   *     根节点   */  Node* avltree_delete(AVLTree tree, Type key)  {      Node *z;         if ((z = avltree_search(tree, key)) != NULL)          tree = delete_node(tree, z);      return tree;  }

 

注意:关于AVL树的”前序遍历”、”中序遍历”、”后序遍历”、”最大值”、”最小值”、”查找”、”打字与印刷”、”销毁”等接口与”二叉查找树”基本一致,这么些操作在”二叉查找树”中已经介绍过了,这里就不再单独介绍了。当然,后文给出的AVL树的总体源码中,有付出这一个API的完毕代码。这个接口很简短,Please
RTFSC(Read The Fucking Source Code)!

 

LL:左左,LeftLeft

 

贯彻右单旋转

AVL树的牵线

AVL树是基于它的发明者G.M. Adelson-Velsky和E.M.
Landis命名的。
它是首首发明的自平衡二叉查找树,也被喻为低度平衡树。比较于”二叉查找树”,它的表征是:AVL树中其他节点的五个子树的冲天最大差异为1。
(关于树的万丈等基本概念,请参照他事他说加以考察”二叉查找树(一)之 图文剖析 和
C语言的落实 “)

图片 15

地点的两张图纸,侧面的是AVL树,它的别的节点的三个子树的惊人差距都<=1;而左侧的不是AVL树,因为7的两颗子树的冲天相差为2(以2为根节点的树的万丈是3,而以8为根节点的树的中度是1)。

AVL树的寻觅、插入和删除在平均和最坏景况下都以O(logn)。
倘诺在AVL树中插入或删除节点后,使得中度之差大于1。此时,AVL树的平衡情状就被毁损,它就不再是一棵二叉树;为了让它再也维持在叁个平衡意况,就需求对其举行旋转管理。学AVL树,着重的地点约等于它的转动算法;在后文的介绍中,再来对它实行详尽介绍。

 

消除EnclavePAJERO,要求右单旋转

AVL树的C测验程序

AVL树的测验程序运维结果如下:

== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9   == 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16   == 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16   == 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7   == 高度: 5  == 最小值: 1  == 最大值: 16  == 树的详细信息:    7 is root   4 is  7's   left child   2 is  4's   left child   1 is  2's   left child   3 is  2's  right child   6 is  4's  right child   5 is  6's   left child  13 is  7's  right child  11 is 13's   left child   9 is 11's   left child   8 is  9's   left child  10 is  9's  right child  12 is 11's  right child  15 is 13's  right child  14 is 15's   left child  16 is 15's  right child    == 删除根节点: 8  == 高度: 5  == 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16   == 树的详细信息:    7 is root   4 is  7's   left child   2 is  4's   left child   1 is  2's   left child   3 is  2's  right child   6 is  4's  right child   5 is  6's   left child  13 is  7's  right child  11 is 13's   left child   9 is 11's   left child  10 is  9's  right child  12 is 11's  right child  15 is 13's  right child  14 is 15's   left child  16 is 15's  right child

 

下边,我们对测验程序的流水生产线实行剖判!

1. 新建AVL树
   新建AVL树的根节点root。

 

2. 一一拉长”3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9″
到AVL树中,进度如下。

2.01 添加3,2
增添3,2都不会损坏AVL树的平衡性。

图片 16

 

2.02 添加1
增多1之后,AVL树失衡(LL),此时须求对AVL树进行旋转(LL旋转)。旋转进程如下:

图片 17

 

2.03 添加4
增添4不会破坏AVL树的平衡性。

图片 18

 

2.04 添加5
增添5之后,AVL树失衡(陆风X8福特Explorer),此时急需对AVL树进行旋转(奥迪Q5翼虎旋转)。旋转进度如下:

图片 19

 

2.05 添加6
增多6之后,AVL树失衡(宝马7系CRUISER),此时急需对AVL树举办旋转(瑞鹰昂Cora旋转)。旋转进程如下:

图片 20

 

2.06 添加7
增添7之后,AVL树失去平衡(PRADO奥迪Q5),此时急需对AVL树进行旋转(GL450Sportage旋转)。旋转进度如下:

图片 21

 

2.07 添加16
拉长16不会破坏AVL树的平衡性。

图片 22

 

2.08 添加15
增加15之后,AVL树失衡(PRADO大切诺基),此时需求对AVL树举办旋转(PAJEROTiguan旋转)。旋转进程如下:

图片 23

 

2.09 添加14
增添14从此,AVL树失衡(卡宴L),此时需求对AVL树进行旋转(CRUISERL旋转)。旋转进程如下:

图片 24


k2给k1的right

k1给k2的left

解决地点的景观

 

 

LR:左右,LeftRight

节点的中度,是它左子树可能右子树中,中度大的格外 再加1

 

k2的left给k1

 

 

减轻LL,供给左单旋转

 

k1,k2

2.left——左子树

k1的right给k2的left

/**
 * AVL树测试
 * @author taoshihan
 * @param <T>
 *
 */
public class AVLTree<T extends Comparable<T>> {
    private AVLNode mRoot;//根节点
    class AVLNode<T extends Comparable<T>>{
        private T key;//键值
        private int height;//高度
        private AVLNode left;//左子树
        private AVLNode right;//右子树
        public AVLNode(T key,AVLNode left,AVLNode right) {
            this.key=key;
            this.left=left;
            this.right=right;
            this.height=0;
        }
    }
    /**
     * 获取节点高度
     * @param tree
     * @return
     */
    public int height(AVLNode<T> tree){
        if(tree!=null){
            return tree.height;
        }
        return 0;
    }
    /**
     * 取出左右子树中高的那个
     * @param a
     * @param b
     * @return
     */
    public int maxHeight(int a,int b){
        return a>b ? a : b;
    }
    /**
     * 左单旋转
     * @param k2
     * @return
     */
    public AVLNode<T> leftLeftRotation(AVLNode<T> k2){
        AVLNode k1;
        k1 = k2.left;
        k2.left=k1.right;
        k1.right=k2;
        k2.height=maxHeight(height(k2.left), height(k2.right));
        k1.height=maxHeight(height(k1.left), height(k1.right));
        return k1;
    }
    /**
     * 右单旋转
     * @param k2
     * @return
     */
    public AVLNode<T> rightRightRotation(AVLNode<T> k1){
        AVLNode k2;
        k2=k1.right;
        k1.right=k2.left;
        k2.left=k1;

        k2.height=maxHeight(height(k2.left), height(k2.right));
        k1.height=maxHeight(height(k1.left), height(k1.right));
        return k2;
    }

 

实现AVL树

概念二个AVL树,AVLTree,定义AVLTree的节点内部类AVLNode,节点富含以下特点:

4.height——高度

 

福寿双全左单旋转

1.key——关键字,对AVL树的节点进行排序

 

假定在AVL树插入节点后恐怕导致AVL树失去平衡,具体会有各类景况:

图片 25

AVL树是惊人平衡的二叉树,任何节点的四个子树的莫斯中国科学技术大学学差异<=1

 

图片 26

k1的right给k2

 

RR:右右,RightRight

k2的left给k1的right

3.right——右子树

化解LCRUISER,需求先右单旋转,再左单旋转

杀鸡取蛋路虎极光L,须求先左单旋转,再右单旋转

 

 

Post Author: admin

发表评论

电子邮件地址不会被公开。 必填项已用*标注