Python describes the data structure of the binary sort tree

Article Directory

Preface

This chapter mainly introduces one of the applications of binary trees-binary sort trees, including the definition, search, insertion, construction, deletion and search efficiency analysis of binary sort trees.

1. Definition of Binary Sort Tree

Binary Sort Tree (B i n a r y (Binary ( B i n a r y  S o r t Sort S o r t  T r e e, B S T) Tree,BST) T r e e ,B S T ), Also known as a binary search tree, has the following properties:
(1) If the left subtree is not empty, the value of all nodes on the left subtree is less than the value of the root node;
(2) If the right subtree is not empty , Then the values ​​of all nodes on the right subtree are greater than the value of the root node;
(3) The left and right subtrees are also a binary sort tree respectively.
In summary, in the binary sorting tree:, 左子树结点的值 < 根结点的值 < 右子树结点的值so the middle-order traversal of the binary sorting tree can get an increasing ordered sequence.

2. Search for Binary Sort Tree

The search of a binary sorting tree is a process of comparing from the root node down to a certain branch level by level. If the binary sort tree is not empty, first compare the given key with the key of the root node. If it is equal, the search is successful; if not, if it is less than the key of the root node, then it is at the root node. Search on the left subtree of. If it is greater than the key of the root node, search on the right subtree of the root node.
Search algorithm of binary sort tree:

    def BSTSearch(self, k):
        TreeNode = self.RootNode
        while TreeNode is not None and k != TreeNode.data:
            if k < TreeNode.data:
                TreeNode = TreeNode.lchild
            else:
                TreeNode = TreeNode.rchild
        return TreeNode

3. Insertion of Binary Sort Tree

Binary sort tree is a dynamic tree table, its structure is usually not generated at one time, but inserted in the search process when there is no node with a key equal to a given value in the tree.
The insertion process is as follows: if the binary sort tree is empty, insert the node directly; if it is not empty, first compare the given keyword with the keyword of the root node, if it is less than the keyword of the root node, insert the left If the subtree is greater than the key of the root node, insert the right subtree. The inserted node must be a newly added leaf node, and it is the left child or right child of the last node visited on the search path when the search fails.
The insertion algorithm of the binary sort tree:

    def BSTInsert(self, k):
        TreeNode = self.RootNode
        if TreeNode is None:
            self.RootNode = BiTreeLinkNode(k)
            return True
        while True:
            if k < TreeNode.data:
                if TreeNode.lchild is None:
                    TreeNode.lchild = BiTreeLinkNode(k)
                    return True
                TreeNode = TreeNode.lchild
            elif k > TreeNode.data:
                if TreeNode.rchild is None:
                    TreeNode.rchild = BiTreeLinkNode(k)
                    return True
                TreeNode = TreeNode.rchild
            else:
                return False

4. Construction of Binary Sort Tree

The construction process of a binary sort tree is as follows: Starting from an empty tree, input elements one by one, and insert them into appropriate positions in the tree. The sequence of keywords is different, the binary sorting tree constructed will also be different, such as the following figure:

Insert picture description here

The construction algorithm of the binary sort tree:

    def CreateBST(self):
        for val in self.data_list:
            self.BSTInsert(val)
        return self.RootNode

5. Deletion of Binary Sort Tree

When deleting a node in a binary sorting tree, you cannot delete all the nodes on the subtree rooted at that node. The deleted node must be removed from the linked list storing the binary sorting tree. Reconnect the binary linked list that was broken by deleting the node, while ensuring that the nature of the binary sorting tree will not be lost. There are three specific cases:
(1) If the deleted node is a leaf node, it can be deleted directly;
(2) If the deleted node has only one left subtree or right subtree, you need to let the node's The subtree becomes the subtree of the parent node of the node to replace the location of the deleted node;

Insert picture description here

(3) The deleted node has a left subtree and a right subtree. It is necessary to replace the position of the node with the direct successor of the node, and then delete the direct successor from the binary sort tree.

Insert picture description here

6. Analysis of search efficiency of binary sort tree

If the absolute value of the difference between the heights of the left and right subtrees of a binary sort tree does not exceed 1, then such a binary tree is called a balanced binary tree, and its average search length is O (l o g 2 n) O(log_2n) O ( l o g2​n ); If the binary sort tree is a single tree with only a left subtree or a right subtree (similar to an ordered singly linked list), its average search length is O (n) O(n) O ( n ).
In the case of equal probability, there is a sequence {2, 1, 4, 3} \{2,1,4,3\} { 2 ,1 ,4 ,3 }The average search length of a successful search of a sorted binary tree is
 A S L = 1 + 2 × 2 + 3 4 = 2 ASL=\frac {1+2\times2+3} {4}=2 A S L=41+2X2+3​=2 Sequenced {1, 2, 3, 4} \{1,2,3,4\} { 1 ,2 ,3 ,4 }The average search length of a successful search of a sorted binary tree is
 A S L = 1 + 2 + 3 + 4 4 = 2.5 ASL=\frac {1+2+3+4} {4}=2.5 A S L=41+2+3+4​=2 . 5 The search efficiency of a binary sort tree mainly depends on the height of the tree. If you want to improve the search efficiency, it is best not to use an ordered sequence when constructing a binary sort, and try to construct a balanced binary tree.

About average search length A S L ASL A S LThe knowledge will be discussed in this part of the search.