二分木を回転しAVL木にするプログラム

実現したいこと

二分木を適切に回転してAVL木にするプログラムを作成しています。
引数で与えられるアドレスの指す節点を根とする木は二分探索木であり、左右の部分木 (葉の場合も含む) は AVL 木の条件を満たし、それらの高さの差は 2 以下であるものと仮定します。

発生している問題・エラーメッセージ

次のように作成したところ、入力によって正しく出力されるものとsegmentaiton faultが発生するものがあります。どこが欠陥なのかが分かりません。教えていただけませんか？

該当のソースコード

C
1#include<stdio.h>
2#include<stdlib.h>
3char buf[128]; /* 関数 get_avl で用いるグローバル変数 */
4
5struct map { int id;};
6typedef struct map datatype; /* ← 格納するデータは構造体 map */
7struct avl_node { datatype data; struct avl_node *left, *right; int height; };
8
9struct avl_node* get_avl() {
10  struct avl_node *t;
11  /* ドットだけなら葉 (NULL) を返す */
12  if(fgets(buf,sizeof(buf),stdin)==NULL || buf[0]=='.')
13    return NULL;
14  else {
15    /* ドットでなければ節点を表す構造体のアドレス t を用意 */
16    t = (struct avl_node*)malloc(sizeof(struct avl_node));
17    /* 高さを t->height に、idを t->data に格納 */
18    sscanf(buf,"[%d]%d",&t->height,&t->data.id);
19    /* 左の子を t->left に、右の子を t->right に格納 */
20    t->left = get_avl();
21    t->right = get_avl();
22    /* t を返す */
23    return t;
24  }
25}
26
27int height(struct avl_node *t){//節点の高さを計算
28  int x=0, y=0;
29  if(t!=NULL){
30   x = height(t->left) + 1;
31   y = height(t->right) + 1;
32   if(x > y){
33    return x;
34   }else{
35     return y;
36   }
37  }else{
38      return 0;
39  }
40}
41void put_height(struct avl_node *t){//節点の高さを設定
42  t->height = height(t);
43  if(t->right != NULL){
44  put_height(t->right);
45  }
46  if(t->left != NULL){
47  put_height(t->left);
48  }
49}
50
51struct avl_node* rotate_right(struct avl_node *t) {//右に回転
52  if(t->left == NULL){
53    return t;
54  }else{
55    struct avl_node *nnode;
56    nnode = t->left;
57    t->left = nnode ->right;
58    nnode->right = t;
59    put_height(t);
60    put_height(nnode);
61    return nnode;
62  }
63}
64struct avl_node* rotate_left(struct avl_node *t) {//左に回転
65  if(t->right == NULL){
66    return t;
67  }else{
68    struct avl_node *nnnode;
69    nnnode = t->right;
70    t->right = nnnode->left;
71    nnnode->left = t;
72    put_height(t);
73    put_height(nnnode);
74    return nnnode;
75  }
76}
77
78struct avl_node* balance(struct avl_node *t) {
79  if(-1 <= (t->left->height - t->right->height) && (t->left->height - t->right->height) <= 1){
80     //左右の木の高さの差が1以内なら
81     return t;//変更せず返す
82  }else if((t->left->height - t->right->height) == 2){//左の部分木の方が右の部分木より2高く、
83     if((t->left)->left->height >= (t->left)->right->height){//左の左の部分木の高さが左の右の部分木の高さ以上なら
84         t = rotate_right(t);
85     }else{//左の左の部分木の高さが左の右の部分木の高さより小さいならば
86         struct avl_node *nnode;
87         nnode = rotate_left(t->left);//左の部分木を回転
88         t->left = nnode;
89         t = rotate_right(t); //全体を右回転
90     }
91  }else{//右の部分木の方が左の部分木より2高く(左右逆のプログラム)
92     if((t->right)->right->height >= (t->right)->left->height){
93         t = rotate_left(t);
94     }else{
95         struct avl_node *nnode;
96         nnode = rotate_right(t->right);
97         t->right = nnode;
98         t = rotate_left(t); 
99     }
100  }
101  put_height(t);
102  return t;
103}
104
105void print_avl(struct avl_node *t) {//出力関数
106  if(t==NULL)
107    printf(".\n");
108  else {
109    printf("[%d]%d\n",t->height,t->data.id);
110    print_avl(t->left);
111    print_avl(t->right);
112  }
113}
114
115int main() {
116/* 厳密にいえば入力は AVL 木とは限らないが、関数 get_avl で入力の木を作れる */
117  struct avl_node *t = get_avl();
118  t = balance(t);
119  print_avl(t);
120  return 0;
121}

入出力例

正しく入出力される例
入力
[4]10567
[3]10345
[2]10123
.
[1]10234
.
.
[1]10456
.
.
[1]10678
.
.
出力
[3]10345
[2]10123
.
[1]10234
.
.
[2]10567
[1]10456
.
.
[1]10678
.
.
正しく入出力されない例
入力
[3]10789
[2]10456
[1]10123
.
.
.
.
出力
[2]10456,David Beckham,77
[1]10123,Ichiro Suzuki,51
.
.
[1]10789,Cristiano Ronaldo,7
.
.