Binary Search Tree

Binary search tree is the most common type of binary tree, also called binary search tree. As the name implies, binary search tree is born to achieve fast search, its biggest characteristic is to support dynamic data set fast insert, delete, search operations. So how does binary search tree realize fast search, insert and other operations? These all depend on the special structure of binary search trees. A binary search tree requires that, at any node in the tree, the value of each node in the left subtree is less than the value of this node, and the value of each node in the right subtree is greater than the value of this node.

The search operation of a binary search tree

class Node: def __init__(self, val): self.val = val self.left = None self.right = None class BinarySearchTree(object): Def find(self, root, target): def find(self, root, target): While root: if target < root.val: root = root.left elif target > root.val: root = root.right else: return True return FalseCopy the code

Insert operations in binary lookup trees

Def insert(self, root, target): # if not root: root = Node(target) return root: If the target value is less than the current node value and the current node value does not exist in the left subtree, insert the new node directly into the left child node position; If target < root.val: if not root.left: root.left = Node(target) return else: Root = root.left # If the target value is greater than the current node value, and the current node value does not exist right subtree, insert the new node directly into the right child node location; Else: If not root.right: root.right = Node(target) return else: root = root.rightCopy the code

Delete operation of binary lookup tree

The deletion operation of the binary search tree is slightly more complicated, and the number of children of the deleted node is different, which needs to be processed separately:

  1. If the node to be deleted has no children, simply set the parent pointer to the node to be deleted to None
  2. If the node to be deleted has only one child node, update the pointer in the parent node to point to the child node of the node to be deleted.
  3. If the node to be deleted has two child nodes. We need to find the smallest node in the right subtree of this node and replace it with the node we want to delete. Then delete the minimum node, because the minimum node must have no left child node, so you can apply the second case to delete the minimum node.

There is also a very simple way to delete a node by marking it as deleted, without actually removing it from the tree. In this way, the deleted nodes need to be stored in the memory, which wastes memory space, but the deletion operation becomes much easier. Moreover, this approach does not make it more difficult to insert and find the implementation of the operation code.

Def delete(self, root, target): def delete(self, root, target): def delete(self, root, target): def delete(self, root, target): = target: pp = p if target > p.val: p = p.right else: p = p.ft # Minpp = p # minpp = p # minpp = p # minpp = p # minpp = p # minpp = p P = minpp = minpp # if p has only one node, record its child node if p.ft: Child = p.light: child = p.light # if p has no children, None else: Elif pp. Left == p: pp. Left = child else: pp.right = childCopy the code

Traversal of binary search trees

Because of the properties of binary search trees, we can obtain a well-ordered data sequence by using middle-order traversal. The time is order n.

Def inorderTraversal(self, root): res = [] stack = [] while root: while root: stack.append(root) root = root.left root = stack.pop() res.append(root.val) root = root.right return resCopy the code

Binary trees that support repeated data

  1. With linked lists, nodes can store multiple objects with the same value
  2. Treat objects of the same value as “greater than” the original node value, and insert the right child node – when you find the same object, you don’t stop immediately, but look up until you reach the leaf node.

The time complexity of binary lookup trees

In binary search trees, the time complexity of search, insert, delete and many other operations is proportional to the height of the tree. The time complexity of the two extreme cases is O(n) and O(logn) respectively, corresponding to the case where the binary tree degenerates into a linked list and the complete binary tree respectively.