平衡二分探索木から対象文字列を検索する方法

前回

今回

前回は、平衡二分探索木を使い、木構造のバランスを整えた上で構造体内の関数ポインタuを並列処理しました。
今回は、平衡二分探索木から文字列を検索するアルゴリズムを追加します。それに伴い、findNodeAtName関数を追加します。この関数は、TreeNode構造体に定義しているname変数を検索対象にしています。一番最初に見つかったname変数を返しています。

参考ページ

だえうホームページ　【【C言語】AVL 木（平衡２分探索木）の解説と実装】

サメベース. SAMEBASE
【[C言語]二分探索木から要素を削除する関数の実装[コード付]】

双方向リストで関数を管理する方法と関数の並列実行方法

C言語 strlen関数の使い方【文字列の長さを知る仕組み】

参考文献

定本　Ｃプログラマのためのアルゴリズムとデータ構造 1998/3/23
近藤　嘉雪 著

改訂第4版 C言語によるはじめてのアルゴリズム入門　2017年11月25日
河西朝雄　著

［改訂新版］C言語による標準アルゴリズム事典
奥村晴彦　著

準備

console

clang ーlpthread -lm sample.c -o sample
./sample

もしくはオンラインコンパイラを使用します。
オンラインコンパイラ
Cコンパイラを使用します。

ソースコード

sample.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <errno.h>

#define MAX_NAME_LEN 256
#define MAX_HEIGHT 512

#define TREE_LEFT 1
#define TREE_RIGHT 2

typedef struct Hello{
	long i;
	void* (*u)(void *);
}Hello;

typedef void* (*fupo)(void *);

/* 二分探索木のノードを表す構造体 */
typedef struct TreeNode {
  long number;
  char name[MAX_NAME_LEN];
  long type;
  void *data;
  struct TreeNode *left;
  struct TreeNode *right;
}TreeNode;

/* getHeight:二分探索木のノード全てを削除する
   引数１ node : 根ノードのアドレス
   返却値 : nodeを根とした木の高さ */
int getHeight(TreeNode *node) {

  int left_height;
  int right_height;
  int tree_height;

  if (node == NULL) {
	/* nodeが無いなら高さは0 */
	return 0;
  }

  /* 左右の子を根とした木の高さを取得 */
  left_height = getHeight(node->left);
  right_height = getHeight(node->right);

  /* 大きい方に+1したものを木の高さとして返却 */
  if (left_height > right_height) {
	tree_height = left_height;
  } else {
	tree_height = right_height;
  }

  return tree_height + 1;
}

/* leftRotate:nodeを根とする部分木を回転（左）
   引数１ root_node : 根のノードを指すアドレス
   引数２ node : 回転する部分木の根ノードを指すアドレス
   引数３ parent : nodeの親ノードを指すアドレス
   引数４ direction : parentから見たnodeのある方向
   返却値 : 根のノードを指すアドレス */
TreeNode *leftRotate(TreeNode *root_node, TreeNode *node, TreeNode *parent, int direction) {
  /* nodeを根として左回転を行う */

  TreeNode *pivot;
  TreeNode *new_root;

  printf("left_rotate:%ld\n", node->number);

  /* 新しい根とするノードをpivotとして設定 */
  pivot = node->right;

  /* 左回転 */
  if (pivot != NULL) {
	node->right = pivot->left;
	pivot->left = node;
  }

  /* parentもしくはrootに新しい根ノードを参照させる */
  if (parent == NULL) {
	new_root = pivot;
	return new_root;
  }

  /* どちらの子に設定するかはdirectionから判断 */
  if (direction == TREE_LEFT) {
	parent->left = pivot;
  } else {
	parent->right = pivot;
  }
  return root_node;
}

/* rightRotate:nodeを根とする部分木を回転（右）
   引数１ root_node : 根のノードを指すアドレス
   引数２ node : 回転する部分木の根ノードを指すアドレス
   引数３ parent : nodeの親ノードを指すアドレス
   引数４ direction : parentから見たnodeのある方向
   返却値 : 根のノードを指すアドレス */
TreeNode * rightRotate(TreeNode *root_node, TreeNode *node, TreeNode *parent, int direction) {

  TreeNode *pivot;
  TreeNode *new_root_node;

  printf("right_rotate:%ld\n", node->number);

  /* 新しい根とするノードをpivotとして設定 */
  pivot = node->left;

  /* 右回転 */
  if (pivot != NULL) {
	node->left = pivot->right;
	pivot->right = node;
  }

  /* parentもしくはroot_nodeに新しい根ノードを参照させる */
  if (parent == NULL) {
	new_root_node = pivot;
	return new_root_node;
  }

  /* どちらの子に設定するかはdirectionから判断 */
  if (direction == TREE_LEFT) {
	parent->left = pivot;
  } else {
	parent->right = pivot;
  }

  return root_node;
}

/* leftRightRotate:nodeを根とする部分木を二重回転（右->左）
   引数１ root_node : 根のノードを指すアドレス
   引数２ node : 回転する部分木の根ノードを指すアドレス
   引数３ parent : nodeの親ノードを指すアドレス
   引数４ direction : parentから見たnodeのある方向
   返却値 : 根のノードを指すアドレス */
TreeNode *rightLeftRotate(TreeNode *root_node, TreeNode *node, TreeNode *parent, int direction) {
  /* ２重回転（Right Left Case）を行う */

  TreeNode *new_root_node;
  printf("right_left_rotate:%ld\n", node->number);

  /* nodeの右の子ノードを根として右回転 */
  new_root_node = rightRotate(root_node, node->right, node, TREE_RIGHT);

  /* nodeを根として左回転 */
  return leftRotate(new_root_node, node, parent, direction);
}

/* leftRightRotate:nodeを根する部分木を二重回転（左->右）
   引数１ root_node : 根のノードを指すアドレス
   引数２ node : 回転する部分木の根ノードを指すアドレス
   引数３ parent : nodeの親ノードを指すアドレス
   引数４ direction : parentから見たnodeのある方向
   返却値 : 根のノードを指すアドレス */
TreeNode * leftRightRotate(TreeNode *root_node, TreeNode *node, TreeNode *parent, int direction) {
  /* ２重回転（Left Right Case）を行う */

  TreeNode *new_root_node;

  printf("left_right_rotate:%ld\n", node->number);

  /* nodeの左の子ノードを根として左回転 */
  new_root_node = leftRotate(root_node, node->left, node, TREE_LEFT);

  /* nodeを根として右回転 */
  return rightRotate(new_root_node, node, parent, direction);
}

/* balancing:nodeからbranchで辿ったノードを平衡にする
   引数１ root_node : 根のノードを指すアドレス
   引数２ node : 平衡にするノードを指すアドレス
   引数３ parent : nodeの親ノードを指すアドレス
   引数４ direction : parentから見たnodeのある方向
   引数５ branch : 平衡化を行うノードへの経路
   引数６ num_branch : branchに格納された経路の数
   返却値 : 根のノードを指すアドレス */
TreeNode * balancing(TreeNode *root_node, TreeNode *node, TreeNode *parent, int direction, int *branch, int num_branch) {

  TreeNode *next;
  TreeNode *new_root_node;

  int left_height, right_height;
  int balance;

  if (node == NULL || root_node == NULL) {
	return root_node;
  }

  if (num_branch > 0) {
	/* 辿れる場合はまず目的のノードまで辿る */

	/* 辿る子ノードを設定 */
	if (branch[0] == TREE_LEFT) {
	  next = node->left;
	} else {
	  next = node->right;
	}

	/* 子ノードを辿る */
	new_root_node = balancing(root_node, next, node, branch[0], &branch[1], num_branch - 1);
  }
	
  /* 平衡係数を計算 */
  left_height = getHeight(node->left);
  right_height = getHeight(node->right);
  balance = right_height - left_height;
  
  if (balance > 1) {
	/* 右の部分木が高くて並行状態でない場合 */

	/* ２重回転が必要かどうかを判断 */
	if (getHeight(node->right->left) > getHeight(node->right->right)) {
	  /* ２重回転（Right Left Case）*/
	  return rightLeftRotate(new_root_node, node, parent, direction);

	} else {
	  /*１重回転（左回転）*/
	  return leftRotate(new_root_node, node, parent, direction);
	}
  
  } else if (balance < -1) {
	/* 左の部分木が高くて並行状態でない場合 */

	/* ２重回転が必要かどうかを判断 */
	if (getHeight(node->left->right) > getHeight(node->left->left)) {
	  /* ２重回転（Left Right Case）*/
	  return leftRightRotate(new_root_node, node, parent, direction);
	} else {
	  /* １重回転（右回転）*/
	  return rightRotate(new_root_node, node, parent, direction);
	}
  }

  return root_node;
}

/* deleteTree:二分探索木のノード全てを削除する
   引数１ root_node : 根ノードのアドレス
   返却値 : なし */
void deleteTree(TreeNode *root_node){
  if(root_node == NULL){
	return;
  }

  if(root_node->left != NULL){
	deleteTree(root_node->left);
  }
  if(root_node->right != NULL){
	deleteTree(root_node->right);
  }

  printf("free:%ld(%s)\n", root_node->number, root_node->name);
  free(root_node);

}

/* mallocNode:ノードの構造体のメモリを確保し、データを設定
   引数１ number : 追加する会員番号
   引数２ name : 追加する会員の名前
   返却値 : 追加したノードのアドレス */
TreeNode *mallocNode(long number, char *name, long type, void *data){
  TreeNode *add;

  add = (TreeNode*)malloc(sizeof(TreeNode));
  if(add == NULL){ 
	return NULL;
  }

  add->left = NULL;
  add->right = NULL;
  add->number = number;
  strcpy(add->name, name);
  add->type=type;
  add->data=data;

  return add;
}

/* insertNode:指定されたnumberとname持つノードを追加する
   引数１ root_node : 根ノードのアドレス
   引数２ number : 追加する会員番号
   引数３ name : 追加する会員の名前
   返却値 : 根ルートのアドレス */
TreeNode *insertNode(TreeNode *root_node, long number, char *name,long type, void *data){
  TreeNode *node;
  int branch[MAX_HEIGHT] = {0};
  int num_branch = 0;

  /* まだノードが一つもない場合 */
  if(root_node == NULL){
	/* 根ノードとしてノードを追加 */
	root_node = mallocNode(number, name, type, data);
	if(root_node == NULL){
	  printf("malloc error\n");
	  return NULL;
	}
	return root_node;
  }

  /* 根ノードから順に追加する場所を探索 */
  node = root_node;
  while(1) {
	if(number < node->number){
	  /* 追加する値がノードの値よりも小さい場合 */

	  if(node->left == NULL){
		/* そのノードの左の子が無い場合（もう辿るべきノードが無い場合）*/

		/* その左の子の位置にノードを追加 */
		node->left = mallocNode(number, name, type, data);

		/* 追加完了したので処理終了 */
		break;
	  }

			  /* 左ノードを辿ったことを覚えておく */
	  branch[num_branch] = TREE_LEFT;
	  num_branch++;
	  
	  /* 左の子がある場合は左の子を新たな注目ノードに設定 */
	  node = node->left;

	} else if(number > node->number){
	  /* 追加する値がノードの値よりも大きい場合 */

	  if(node->right == NULL){
		/* そのノードの右の子が無い場合（もう辿るべきノードが無い場合）*/

		/* その右の子の位置にノードを追加 */
		node->right = mallocNode(number, name, type, data);

		/* 追加完了したので処理終了 */
		break;
	  }

	  /* 右ノードを辿ったことを覚えておく */
	  branch[num_branch] = TREE_RIGHT;
	  num_branch++;

	  /* 右の子がある場合は右の子を新たな注目ノードに設定 */
	  node = node->right;
	} else {
	  /* 追加する値とノードの値が同じ場合 */

	  printf("%ld already exist\n", number);
	  break;
	}
  }
	
  return balancing(root_node, root_node, NULL, 0, branch, num_branch);
}

/* findNode:指定されたnumberを持つノードを探索する
   引数１ root_node : 探索を開始するノードのアドレス
   引数２ number : 探索する会員番号
   返却値 : number を持つノードのアドレス（存在しない場合は NULL）*/
TreeNode *findNode(TreeNode *root_node, long number){
  TreeNode *node;
  
  node = root_node;

  /* 探索を行うループ（注目ノードがNULLになったら終了 */
  while(node){
	if(number < node->number){
	  /* 探索値がノードの値よりも小さい場合 */

	  /* 注目ノードを左の子ノードに設定 */
	  node = node->left;
	} else if(number > node->number){
	  /* 探索値がノードの値よりも大きい場合 */

	  /* 注目ノードを右の子ノードに設定 */
	  node = node->right;
	} else {
	  /* 探索値 = ノードの値の場合 */
	  return node;
	}
  }
  
  /* 探索値を持つノードが見つからなかった場合 */
  return NULL;
}

/* deleteNoChildeNode:指定された子の無いノードを削除する
   引数１ root_node : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ parent：削除するノードの親ノードのアドレス
   返却値 : 根ノードのアドレス */
TreeNode *eraseNoChildNode(TreeNode *root_node, TreeNode *node, TreeNode *parent){

  if(parent != NULL){
	/* 親がいる場合（根ノード以外の場合）は
	削除対象ノードを指すポインタをNULLに設定 */
	if(parent->left ==  node){
	   /* 削除対象ノードが親ノードから見て左の子の場合 */
		parent->left = NULL;
	} else {
	  /* 削除対象ノードが親ノードから見て右の子の場合 */
	  parent->right = NULL;
	}
	free(node);
  }  else {
	/* 削除対象ノードが根ノードの場合 */
	free(node);
	  
	/* 根ノードを指すポインタをNULLに設定 */
	root_node = NULL;
  }
	
  return root_node;
}

/* deleteOneChildeNode:指定された子が一つのノードを削除する
   引数１ root_node : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   引数３ child : 削除するノードの子ノードのアドレス
   返却値 : 根ノードのアドレス */
TreeNode *eraseOneChildNode(TreeNode *root_node, TreeNode *node, TreeNode * child){
   
  /* 削除対象ノードにその子ノードのデータとポインタをコピー */
  node->number = child->number;
  strcpy(node->name, child->name);
  node->left = child->left;
  node->right = child->right;
	
  /* コピー元のノードを削除 */
  free(child);
  
  return root_node;
}

/* deleteTwoChildeNode:指定された子が二つのノードを削除する
   引数１ root_node : 木の根ノードのアドレス
   引数２ node : 削除するノードのアドレス
   返却値 : 根ノードのアドレス */
TreeNode *eraseTwoChildNode(TreeNode *root_node, TreeNode *node, int *branch, int *num_branch){

  TreeNode *max;
  TreeNode *maxParent;
  
  /* 左の子から一番大きい値を持つノードを探索 */
  max = node->left;
  maxParent = node;

  /* 左の子ノードを辿ったことを覚えておく */
  branch[*num_branch] = TREE_LEFT;
  (*num_branch)++;
	
  while(max->right != NULL){
	maxParent = max;
	max = max->right;

	/* 右の子ノードを辿ったことを覚えておく */
	branch[*num_branch] = TREE_RIGHT;
	(*num_branch)++;
  }
  printf("max number is %ld\n", max->number);
	
  /* 最大ノードのデータのみ削除対象ノードにコピー */
  node->number = max->number;
  strcpy(node->name, max->name);
	
  /* 最大ノードを削除 */
  
  /* maxは最大ノードなので必ずmax->rightはNULLになる */
  if(max->left == NULL){
	/* 最大ノードに子がいない場合 */
	root_node = eraseNoChildNode(root_node, max, maxParent);      
	} else {
	  /* 最大ノードに子供が一ついる場合 */
	  root_node = eraseOneChildNode(root_node, max, max->left);
	}

	return root_node;
}



/* eraseNode:指定されたnumberを持つノードを削除する
   引数１ root_node : 木の根ノードのアドレス
   引数２ number : 削除する会員番号
   返却値 : 根ノードのアドレス */
TreeNode *eraseNode(TreeNode *root_node, long number){
  TreeNode *node;
  TreeNode *parent;
  int branch[MAX_HEIGHT] = {0};
  int num_branch = 0;

  if(root_node == NULL){
	return NULL;
  }

  /* 削除対象ノードを指すノードを探索 */
  node = root_node;
  parent = NULL;
  
  while(node !=  NULL){
	if(number < node->number){
	  parent = node;
	  node = node->left;

	  /* 左の子ノードを辿ったことを覚えておく */
	  branch[num_branch] = TREE_LEFT;
	  num_branch++;
	} else if(number > node->number){
	  parent = node;
	  node = node->right;

	  /* 右の子ノードを辿ったことを覚えておく */
	  branch[num_branch] = TREE_RIGHT;
	  num_branch++;
	} else {
	  break;
	}
  }
  
  /* 指定されたnumberを値として持つノードが存在しない場合は何もせず終了 */
  if(node == NULL){
	printf("%ld を持つノードが存在しません\n", number);
	return root_node;
  }

  printf("Delete %ld(%s) node\n", node->number, node->name);

  if(node->left == NULL && node->right == NULL){    
	/* 子がいないノードの削除 */
	root_node = eraseNoChildNode(root_node, node, parent);
  } else if((node->left != NULL && node->right == NULL) ||
	(node->right != NULL && node->left == NULL)){
	/* 子が一つしかない場合 */
	
	if(node->left != NULL){
	  root_node = eraseOneChildNode(root_node, node, node->left);
	} else {
	  root_node = eraseOneChildNode(root_node, node, node->right);
	}
  } else {
	/* 左の子と右の子両方がいるノードの削除 */
	root_node = eraseTwoChildNode(root_node, node, branch, &num_branch);
  }
  
  return balancing(root_node, root_node, NULL, 0, branch, num_branch);
}

/* displayTree:root_nodeを根ノードとする二分探索木をの全ノードを表示する
   引数１ root_node : 木の根ノードのアドレス
   引数２ depth: 関数呼び出しの深さ
   返却値 : なし */
void displayTree(TreeNode *root_node, int depth){
  int i;

  if(root_node == NULL){
	return ;
  }

  /* 右の子孫ノードを表示 */
  displayTree(root_node->right, depth+1);
 
  /* 深さをスペースで表現 */ 
  for(i = 0; i < depth; i++){
	printf("  ");
  }

  /* ノードのデータを表示 */
  printf("+%3ld(%s),%ld,%d\n", root_node->number, root_node->name, root_node->type, depth);

  /* 左の子孫ノードを表示 */
  displayTree(root_node->left, depth+1);

  depth++;
}

Hello *structHelloAllocation(){
	return (Hello*)malloc(sizeof(Hello));
}

void* f(void *data){
	Hello *lo=(Hello*)data;
	printf("hello,%ld. \n",lo->i);
	return (void*)lo;
}

void * thread1(void *pNode){
	TreeNode *root_node=(TreeNode*)pNode;
	printf("%ld, ", root_node->number);
	printf("%s, ", root_node->name);
	if(root_node->type==0){
		((Hello*)root_node->data)->u(root_node->data);
	}
	pthread_exit((void*)root_node);
	return (void*)root_node;
}

void executeTreeNodeFunction(TreeNode* root_node) {
	int rc;
    pthread_attr_t attr;
    pthread_t thid;
    
	rc = pthread_attr_init(&attr);
    if (rc == -1) {
        perror("error in pthread_attr_init");
        exit(1);
    }
	if (root_node == NULL) {
		//printf("exit.\n");
		return;
	}else {

        rc = pthread_create(&thid, &attr, thread1, root_node);
        if (rc == -1) {
            perror("error in pthread_create");
            exit(2);
        }
		
		executeTreeNodeFunction(root_node->right);
		executeTreeNodeFunction(root_node->left);
		
		void *s=NULL;
		if (pthread_join(thid, &s) != 0) {
			perror("pthread_create() error\n");
			exit(3);
		}
	}
	return;
}

TreeNode* findNodeAtName(TreeNode *q,char *key){
	TreeNode *p=q;
	if(p!=NULL){
		
		if(strcmp(p->name,key)==0){
			return p;
		}
	
		
		p=findNodeAtName(p->right,key);
		if(p!=NULL){
			return p;
		}
		else{
			p=q;
		}
		
		p=findNodeAtName(p->left,key);
		if(p!=NULL){
			return p;
		}
		else{
			return NULL;
		}
	}
	else{
		return NULL;
	}
	return q;
}


int main(void){
  TreeNode *root_node, *node;
  long input;
  long number;
  char name[MAX_NAME_LEN];
  long loop;
  fupo v=f;
  Hello data[22]={0};
  long i=0;
  for(i=0;i<22;i++){
  	data[i].i=0;
  	data[i].u=v;
  }

  /* まだ木がないのでroot_nodeをNULLにセット */
  root_node = NULL;

  /* 最初にてきとうにノードを追加しておく */
  root_node = insertNode(root_node, 100, "100", 0, (void*)&data[ 0]);
  root_node = insertNode(root_node, 200, "200", 0, (void*)&data[ 1]);
  root_node = insertNode(root_node, 300, "300", 0, (void*)&data[ 2]);
  root_node = insertNode(root_node,  50,  "50", 0, (void*)&data[ 3]);
  root_node = insertNode(root_node, 150, "150", 0, (void*)&data[ 4]);
  root_node = insertNode(root_node, 250, "250", 0, (void*)&data[ 5]);
  root_node = insertNode(root_node,  10,   "1", 0, (void*)&data[ 6]);
  root_node = insertNode(root_node, 125, "125", 0, (void*)&data[ 7]);
  root_node = insertNode(root_node,   5,   "5", 0, (void*)&data[ 8]);
  root_node = insertNode(root_node,  25,  "25", 0, (void*)&data[ 9]);
  root_node = insertNode(root_node, 500, "500", 0, (void*)&data[10]);
  root_node = insertNode(root_node, 175, "175", 0, (void*)&data[11]);
  root_node = insertNode(root_node, 501, "501", 0, (void*)&data[12]);
  root_node = insertNode(root_node, 502, "502", 0, (void*)&data[13]);
  root_node = insertNode(root_node, 503, "503", 0, (void*)&data[14]);
  root_node = insertNode(root_node, 504, "504", 0, (void*)&data[15]);
  root_node = insertNode(root_node, 505, "505", 0, (void*)&data[16]);
  root_node = insertNode(root_node, 506, "506", 0, (void*)&data[17]);
  root_node = insertNode(root_node, 507, "507", 0, (void*)&data[18]);
  root_node = insertNode(root_node, 508, "508", 0, (void*)&data[19]);
  root_node = insertNode(root_node, 509, "509", 0, (void*)&data[20]);
  root_node = insertNode(root_node, 510, "510", 0, (void*)&data[21]);

  loop = 1;
  while(loop){
	printf("処理を選択(1:add, 2:delete, 3:search, 4:execute, 5:searchName, 6:exit)");
	scanf("%ld", &input);

	switch(input){
	case 1:
	  printf("会員番号(1 - 999):");
	  scanf("%ld", &number);
	  if(number < 1 || number > 999){
		printf("値が範囲外です\n");
		continue;
	  }

	  printf("名前:");
	  scanf("%s", name);
	  Hello *lo=structHelloAllocation();
	  lo->i=0;
	  lo->u=v;
	  root_node = insertNode(root_node, number, name, 0, lo);
	  break;
	case 2:
	  printf("会員番号(1 - 999):");
	  scanf("%ld", &number);
	  if(number < 1 || number > 999){
		printf("値が範囲外です\n");
		continue;
	  }

	  root_node = eraseNode(root_node, number);
	  
	  break;
	case 3:
	  printf("会員番号(1 - 999):");
	  scanf("%ld", &number);
	  if(number < 1 || number > 999){
		printf("値が範囲外です\n");
		continue;
	  }
	  
	  node = findNode(root_node, number);
	  if(node == NULL){
		printf("number %ld is not found\n", number);
	  } else {
		printf("number %ld : %s\n", number, node->name);
	  }
	  break;
	case 4:
	  executeTreeNodeFunction(root_node);
	  break;
	case 5:
	  printf("名前:");
	  scanf("%s", name);
	  if(strlen(name)>MAX_NAME_LEN){
		printf("値が範囲外です\n");
		continue;
	  }
	  
	  node = findNodeAtName(root_node,name);
	  if(node == NULL){
		printf("name %s is not found\n", name);
	  } else {
		printf("number %ld : %s\n", node->number, node->name);
	  }
	  
	  break;
	default:
	  loop = 0;
	  break;
	}
	displayTree(root_node, 0);
  }

  deleteTree(root_node);   
  
  return 0;
}

実行結果

console1

left_rotate:100
right_rotate:50
right_rotate:200
left_rotate:500
left_rotate:300
left_rotate:502
left_rotate:200
left_rotate:504
left_rotate:503
left_rotate:506
left_rotate:100
left_rotate:508
処理を選択(1:add, 2:delete, 3:search, 4:execute, 5:searchName, 6:exit)5
名前:200
number 200 : 200
        +510(510),0,4
      +509(509),0,3
        +508(508),0,4
    +507(507),0,2
      +506(506),0,3
  +505(505),0,1
      +504(504),0,3
    +503(503),0,2
      +502(502),0,3
+501(501),0,0
        +500(500),0,4
      +300(300),0,3
        +250(250),0,4
    +200(200),0,2
        +175(175),0,4
      +150(150),0,3
        +125(125),0,4
  +100(100),0,1
      + 50(50),0,3
        + 25(25),0,4
    + 10(1),0,2
      +  5(5),0,3
処理を選択(1:add, 2:delete, 3:search, 4:execute, 5:searchName, 6:exit)6
        +510(510),0,4
      +509(509),0,3
        +508(508),0,4
    +507(507),0,2
      +506(506),0,3
  +505(505),0,1
      +504(504),0,3
    +503(503),0,2
      +502(502),0,3
+501(501),0,0
        +500(500),0,4
      +300(300),0,3
        +250(250),0,4
    +200(200),0,2
        +175(175),0,4
      +150(150),0,3
        +125(125),0,4
  +100(100),0,1
      + 50(50),0,3
        + 25(25),0,4
    + 10(1),0,2
      +  5(5),0,3
free:5(5)
free:25(25)
free:50(50)
free:10(1)
free:125(125)
free:175(175)
free:150(150)
free:250(250)
free:500(500)
free:300(300)
free:200(200)
free:100(100)
free:502(502)
free:504(504)
free:503(503)
free:506(506)
free:508(508)
free:510(510)
free:509(509)
free:507(507)
free:505(505)
free:501(501)