The Application Of Tree Structure And The Research Of Balanced Search Tree

Nowadays, network and database are developing at full speed .Data search is becoming more and more frequent and the data amount is also bigger and bigger .Therefore, it is extremely urgent to deal with the data by using an effective structure. In the field of data expression, the tree structure becomes the basis and forceful implement of the data expression and information organization for its branch and arrangement. In the field of data search, various ordering trees'average time is ideal in insertion, deletion and search operation, but, under the worst condition, the ordering tree becomes a tree having single branch and its height is maximal, these will increase the time of the operations above rapidly. To avoid this from happening, we introduce the concept of "balanced tree". This type of tree not only maintains good operating nature, but also makes the height of the tree as low as possible. Now, balanced tree has been applied to many fields widely.This text divides balanced tree into two kinds for studying. One is balanced binary tree, and the other is non-binary balanced multi-channel tree. If balanced tree has the ordered characters likes the ordering tree at the same time, it becomes balanced search tree. Then, we can divide balanced tree into balanced binary search tree (includes AVL tree, plump tree, complete binary tree, full binary tree etc.) and balanced multi-channel search tree (includes B- tree, B+ tree, B* tree , 2-3-4 tree, etc.).They maintain the trees'balance by the continuing deletion or insertion, which ensures that the time of the dynamic data sets on the basic operation in the worst case is still under the cost of O (logn). This good operating function makes them becoming effective structures in mathematic problem and database searching.The paper introduces various balanced trees and classifies them. Then, it compares and sums up their various operations and algorithms. It focuses on application of balance tree and puts forward new ideas of maze problems and mathematical set problems. Using various kinds of tree structure can resolve the problems of data expression and high complexity. Finally, it introduces the applications of routes search and database index search. Those applications reflect the tree's good characteristics in data expression and high efficiency in data search.