CAJ | 학술논문

针对目前严格平衡二叉树的建立需要借助有序顺序表来实现的问题，提出一种无需借助有序顺序表也可建立严格平衡二叉树的算法。为了建立关键字的严格平衡二叉树，需要首先建立一个关键字的有序双链表，然后用分治法构造严格平衡二叉树的根节点和左右子树。为了验证所建立的二叉树是严格平衡的，还提出了判断一棵二叉树严格平衡的两种检验方法。其中，严格平衡二叉树的定义法是一种直接判断法，而平均查找长度法可以间接判断一棵二叉树的平衡性。算例仿真表明，无需借助有序顺序表也可建立一棵严格平衡二叉树。
침대목전엄격평형이차수적건립수요차조유서순서표래실현적문제，제출일충무수차조유서순서표야가건립엄격평형이차수적산법。위료건립관건자적엄격평형이차수，수요수선건립일개관건자적유서쌍련표，연후용분치법구조엄격평형이차수적근절점화좌우자수。위료험증소건립적이차수시엄격평형적，환제출료판단일과이차수엄격평형적량충검험방법。기중，엄격평형이차수적정의법시일충직접판단법，이평균사조장도법가이간접판단일과이차수적평형성。산례방진표명，무수차조유서순서표야가건립일과엄격평형이차수。
In view of the problem of the previous strict balanced binary tree needing a orderly sequence table to cre -ate,this paper proposes an algorithm which can also establish a strict balanced binary tree without the orderly se -quence table .In order to establish a strict balanced binary tree about keywords ,the algorithm needs to first establish a ascending double linked list about keywords , then it uses partition method to construct strict balanced binary tree root node and left and right subtrees .In order to ensure the correctness of the strict balanced binary tree , at the same time, it presents two test methods to judge balance of the binary tree established .Among them, It is a kind of direct judgment method for the definition of strict balanced binary tree method , and the average search length method can indirectly judge whether or not a binary tree is balanced .An examples of simulation shows thats a strict balanced binary tree can also be established without the orderly sequence table .