In the first part, the relative basic information of binary tree is sorted out In depth understanding of data structure - binary tree (basic chapter)

Next, we will explain the advanced content of binary tree

## Binary lookup tree

Binary search tree, as its name suggests, is used to find data. It adds several rules on the basis of binary tree:

- If the left subtree is not empty, the values of all nodes on the left subtree are less than those of the root node.
- If the right subtree is not empty, the values of all nodes on the right subtree are greater than those of the root node.
- The left and right subtrees are also binary search trees.

The following figure is a standard binary search tree:

The code structure of binary tree is realized by the structure of go as follows:

type binaryTree struct { value int leftNode *binaryTree rightNode *binaryTree }

Binary lookup tree has three operations: find, insert and delete

### Search of binary tree

Assuming that the value we want to find is 4, the search process is as follows:

- Access root node 6 and find 4 < 6

- Visit the left child node 3 of root node 6 and find that 4 > 3

- Access the right child node 4 of node 3 and find that it is the node to be found

For a binary lookup tree with relatively balanced node distribution, if the total number of nodes is n, the time complexity of finding nodes is O(logn), which is directly proportional to the depth of the tree

The implementation code is as follows:

//Node lookup func findNode(num int,tree *binaryTree) bool{ targetNode := tree for targetNode != nil{ if targetNode.value == num { return true }else if targetNode.value > num { targetNode = targetNode.leftNode }else { targetNode = targetNode.rightNode } } return false }

### Insertion of binary tree

The insertion traversal process of binary tree is similar to that of search. Here we write code directly

//Node insertion func insertNode(tree *binaryTree,node *binaryTree) *binaryTree { if tree.value == 0 { return node } if tree.value == node.value { return tree }else if tree.value > node.value { //Go to the left subtree. If it is empty, insert the node directly if tree.leftNode == nil { tree.leftNode = node }else { tree.leftNode = insertNode(tree.leftNode,node) } }else { //Go to the right subtree. If it is empty, insert the node directly if tree.rightNode == nil { tree.rightNode = node }else { tree.rightNode = insertNode(tree.rightNode,node) } } return tree }

### Deletion of binary tree

Compared with search and insertion, the deletion process of binary tree is relatively complex, and there is corresponding logic in code implementation

The deletion of binary tree can be divided into three cases:

Case 1: the node to be deleted has no child nodes

In the above figure, the node 12 to be deleted is a leaf node without children, so it can be deleted directly

In case 2, the node to be deleted has a child

In the above figure, the node 13 to be deleted has only the left child, so we let the left child node 11 replace the deleted node, and the node relationship below node 11 does not need to be changed

In case 3, the node to be deleted has two children

In the above figure, node 5 to be deleted has two children, which is complex. You need to select the node closest to the node to be deleted to replace it.

In the above example, node 3 is only smaller than node 5 and node 6 is only larger than node 5. Both are appropriate choices. However, it is customary for us to select a node that is only larger than the node to be deleted, that is, replace it with node 6.

The selected node 6 is only larger than node 5, so there must be no left child. Therefore, we delete redundant node 6 in the way of case 1 or case 2.

The code implementation is as follows. The implementation is relatively complex and needs to be processed recursively:

//Delete node func deleteNode(num int,tree *binaryTree) *binaryTree{ //First check whether the deleted value exists in the tree find := findNode(num,tree) if find { //Configure the node value and perform the deletion operation if tree.value == num { //The deleted node has no left and right nodes if tree.leftNode == nil && tree.rightNode == nil { tree = &binaryTree{} }else if tree.leftNode == nil && tree.rightNode != nil { //The left node is empty, and the right node is not empty tree = tree.rightNode }else if tree.rightNode == nil && tree.leftNode != nil { //The right node is empty, and the left node is not empty tree = tree.leftNode }else{ //Both left and right nodes exist tree = replaceNode(tree) } }else if tree.value > num { tree.leftNode = deleteNode(num,tree.leftNode) }else { tree.rightNode = deleteNode(num,tree.rightNode) } } return tree } //Replace delete node func replaceNode(tree *binaryTree) *binaryTree{ //The deleted node has no left and right nodes if tree.leftNode == nil && tree.rightNode == nil { tree = &binaryTree{} }else if tree.leftNode == nil && tree.rightNode != nil { //The left node is empty, and the right node is not empty tree = tree.rightNode }else if tree.rightNode == nil && tree.leftNode != nil { //The right node is empty, and the left node is not empty tree = tree.leftNode }else{ //If both left and right nodes exist, find the node from the right subtree to replace the parent node //If there are no left and right nodes under the right node, it is directly replaced with the value of the right node and the right node is deleted if tree.rightNode.leftNode == nil && tree.rightNode.rightNode == nil { tree.value = tree.rightNode.value tree.rightNode = &binaryTree{} }else if tree.rightNode.leftNode == nil && tree.rightNode.rightNode != nil { //If the left node under the right node is empty and the right node is not empty, the value of the right node is replaced and the right node of the right node is replaced tree.value = tree.rightNode.value tree.rightNode = tree.rightNode.rightNode }else{ //If the left node of the right node is not empty tree.value = tree.rightNode.leftNode.value tree.rightNode.leftNode = replaceNode(tree.rightNode.leftNode) } } return tree }

The complete code to realize the binary search tree is as follows. The sorted nodes can be obtained through the middle order traversal of the binary search tree, so the middle order traversal is used to judge whether the execution is successful

package main import "fmt" type binaryTree struct { value int leftNode *binaryTree rightNode *binaryTree } func main(){ var numArr = []int{10,11,4,2,8,1,3,6,9,5,7} tree := createBinarySearchTree(numArr) find := findNode(9,tree) fmt.Print(find) tree = deleteNode(4,tree) node := &binaryTree{13,nil,nil} tree = insertNode(tree,node) node = &binaryTree{1,nil,nil} var middle []int middle = middleForeach(*tree,middle) fmt.Println(middle) } //Create balanced binary tree func createBinarySearchTree(nums []int) *binaryTree{ tree := new(binaryTree) for index := range nums{ node := &binaryTree{nums[index],nil,nil} tree = insertNode(tree,node) } return tree } //Delete node func deleteNode(num int,tree *binaryTree) *binaryTree{ //First check whether the deleted value exists in the tree find := findNode(num,tree) if find { //Configure the node value and perform the deletion operation if tree.value == num { //The deleted node has no left and right nodes if tree.leftNode == nil && tree.rightNode == nil { tree = &binaryTree{} }else if tree.leftNode == nil && tree.rightNode != nil { //The left node is empty, and the right node is not empty tree = tree.rightNode }else if tree.rightNode == nil && tree.leftNode != nil { //The right node is empty, and the left node is not empty tree = tree.leftNode }else{ //Both left and right nodes exist tree = replaceNode(tree) } }else if tree.value > num { tree.leftNode = deleteNode(num,tree.leftNode) }else { tree.rightNode = deleteNode(num,tree.rightNode) } } return tree } //Replace delete node func replaceNode(tree *binaryTree) *binaryTree{ //The deleted node has no left and right nodes if tree.leftNode == nil && tree.rightNode == nil { tree = &binaryTree{} }else if tree.leftNode == nil && tree.rightNode != nil { //The left node is empty, and the right node is not empty tree = tree.rightNode }else if tree.rightNode == nil && tree.leftNode != nil { //The right node is empty, and the left node is not empty tree = tree.leftNode }else{ //If both left and right nodes exist, find the node from the right subtree to replace the parent node //If there are no left and right nodes under the right node, it is directly replaced with the value of the right node and the right node is deleted if tree.rightNode.leftNode == nil && tree.rightNode.rightNode == nil { tree.value = tree.rightNode.value tree.rightNode = &binaryTree{} }else if tree.rightNode.leftNode == nil && tree.rightNode.rightNode != nil { //If the left node under the right node is empty and the right node is not empty, the value of the right node is replaced and the right node of the right node is replaced tree.value = tree.rightNode.value tree.rightNode = tree.rightNode.rightNode }else{ //If the left node of the right node is not empty tree.value = tree.rightNode.leftNode.value tree.rightNode.leftNode = replaceNode(tree.rightNode.leftNode) } } return tree } //Node lookup func findNode(num int,tree *binaryTree) bool{ targetNode := tree for targetNode != nil{ if targetNode.value == num { return true }else if targetNode.value > num { targetNode = targetNode.leftNode }else { targetNode = targetNode.rightNode } } return false } //Node insertion func insertNode(tree *binaryTree,node *binaryTree) *binaryTree { if tree.value == 0 { return node } if tree.value == node.value { return tree }else if tree.value > node.value { //Go to the left subtree. If it is empty, insert the node directly if tree.leftNode == nil { tree.leftNode = node }else { tree.leftNode = insertNode(tree.leftNode,node) } }else { //Go to the right subtree. If it is empty, insert the node directly if tree.rightNode == nil { tree.rightNode = node }else { tree.rightNode = insertNode(tree.rightNode,node) } } return tree } //Medium order traversal func middleForeach(tree binaryTree,num []int) []int{ var leftNum,rightNum []int //If there is a left node, traverse the left node tree if tree.leftNode != nil { leftNum = middleForeach(*tree.leftNode,leftNum) for _,value := range leftNum{ num = append(num,value) } } //Traverse the root node first if tree.value != 0 { num = append(num,tree.value) } //If there is a right node, traverse the right node tree if tree.rightNode != nil { rightNum = middleForeach(*tree.rightNode,rightNum) for _,value := range rightNum{ num = append(num,value) } } return num }

### Defects of binary tree

Suppose that the initial binary lookup tree has only three nodes, the root node is 9, the left child is 8, and the right child is 12

Next, we insert the following five nodes in turn: 7, 6, 5, 4 and 3. According to the characteristics of binary search tree, what will the result be like?

Although such a tree also conforms to the characteristics of binary lookup tree, the time complexity of finding nodes degenerates to O(n)

## Binary balanced tree

Binary balanced tree is a characteristic binary search tree, also known as AVL tree. It can "self balance" after inserting and deleting nodes each time, that is, it can reach the balance state again through a series of adjustments.

### Equilibrium factor

The following figure is a typical AVL tree with balance factors marked next to each node

The left subtree height of node 4 is 1, and the right subtree does not exist, so the balance factor of this node is 1-0 = 1

The left subtree of 7 does not exist, and the height of the right subtree is 1, so the balance factor is 0-1 = - 1

All leaf nodes do not have left and right subtrees, so the balance factor is 0

The restriction of AVL tree on the balance factor (only - 1, 0, 1) ensures that the height difference between two trees at any node does not exceed 1. This state is called height balance

The following is the code implementation of calculating the tree balance factor. First, calculate the height of the left and right subtrees, and then obtain the balance factor. A method is also added to judge whether the tree reaches balance

//Check that the tree is balanced func (tree binaryTree) isBalance() bool { if tree.RightNode == nil && tree.LeftNode == nil { return true } //Equilibrium factor of nodes factor := tree.getTreeFactor() if factor > 1 || factor < -1 { return false } return true } //Gets the balance factor of the node func (tree binaryTree) getTreeFactor() int{ leftFactor,rightFactor := 0,0 if tree.RightNode != nil { rightFactor = tree.RightNode.getTreeHeight() } if tree.LeftNode != nil { leftFactor = tree.LeftNode.getTreeHeight() } factor := float64(leftFactor - rightFactor) return int(factor) } //Get node tree height, depth first func (tree binaryTree) getTreeHeight() int{ //Node none if tree.RightNode == nil && tree.LeftNode == nil { return 1 } leftHeight,rightHeight := 1,1 if tree.LeftNode != nil && tree.LeftNode.Value != 0 { leftHeight = 1 + tree.LeftNode.getTreeHeight() } if tree.RightNode != nil && tree.RightNode.Value != 0{ rightHeight = 1 + tree.RightNode.getTreeHeight() } //Compare left and right node tree heights height := math.Max(float64(leftHeight),float64(rightHeight)) return int(height) }

### Tree balance adjustment

When the balance factor is broken due to inserting nodes, the tree needs to be adjusted. AVL tree adjustment can be divided into four cases

- Left (LL)

As the name implies, grandfather node A has A left child node B to the right, and node B has A left child node C. Triangles labeled 1, 2, 3 and 4 are subtrees of each node.

In this situation, we take node A as the axis and carry out right rotation operation:

- Right situation (RR)

Grandfather node A has A right child node B, and node B has A right child node C.

In this situation, we take node A as the axis for left rotation operation.

- Left right situation (LR)

Grandfather node A has A left child node B, and node B has A right child node C.

In this situation, we first take node B as the axis for left rotation operation.

This has turned into A left-left situation. We continue the right rotation operation with node A as the axis.

- Right left situation (RL)

Grandfather node A has A right child node B to the right, and node B has A left child node C.

In this situation, we first take node B as the axis for right rotation operation.

This turned into A right-right situation. We continue the left rotation operation with node A as the axis.

The code implementation is as follows:

//Left left situation func LeftLeftRotate(tree *binaryTree) *binaryTree{ //The left node of the original node becomes the root node mainNode := tree.LeftNode changeNode := &binaryTree{} //Judge whether the left node of the original node exists if mainNode.RightNode != nil { changeNode = mainNode.RightNode } mainRightNode := tree mainRightNode.LeftNode = changeNode //Refresh tree height mainRightNode.Height = mainRightNode.getTreeHeight() mainNode.RightNode = mainRightNode mainNode.Height = mainNode.getTreeHeight() return mainNode } //Right right situation func RightRightRotate(tree *binaryTree) *binaryTree{ mainNode := tree.RightNode changeNode := &binaryTree{} if mainNode.LeftNode != nil { changeNode = mainNode.LeftNode } mainLeftNode := tree mainLeftNode.RightNode = changeNode mainLeftNode.Height = mainLeftNode.getTreeHeight() mainNode.LeftNode = mainLeftNode mainNode.Height = mainNode.getTreeHeight() return mainNode } //Control situation func LeftRightRotate(tree *binaryTree) *binaryTree{ mainLeftNode := tree.LeftNode changeNode := &binaryTree{} mainNode := mainLeftNode.RightNode if mainNode.LeftNode != nil { changeNode = mainNode.LeftNode } mainLeftNode.RightNode = changeNode mainLeftNode.Height = mainLeftNode.getTreeHeight() mainNode.LeftNode = mainLeftNode mainNode.Height = mainNode.getTreeHeight() tree.LeftNode = mainNode tree = LeftLeftRotate(tree) return tree } //Right left situation func RightLightRotate(tree *binaryTree) *binaryTree{ mainRightNode := tree.RightNode changeNode := &binaryTree{} mainNode := mainRightNode.LeftNode if mainNode.RightNode != nil { changeNode = mainNode.RightNode } mainRightNode.LeftNode = changeNode mainRightNode.Height = mainRightNode.getTreeHeight() mainNode.RightNode = mainRightNode mainNode.Height = mainNode.getTreeHeight() tree.RightNode = mainNode tree = RightRightRotate(tree) return tree }

### Insertion and deletion of binary balanced tree

In terms of code implementation, you can reuse the code logic of the binary search tree, add logic on the basis of the binary search tree, and add judgment logic after the insertion and deletion of nodes to judge whether the balance of the binary balance tree is damaged. If it is damaged, make relevant adjustments. The process will not be repeated, and the code will be directly and completely implemented

package main import ( "fmt" "math" ) type binaryTree struct { Value int Height int LeftNode *binaryTree RightNode *binaryTree } func main(){ var numArr = []int{10,11,4,2,8,1,3,6,9,5,7,12} tree := createBinaryBalanceTree(numArr) var middle []int tree = deleteNode(9,tree) tree = deleteNode(11,tree) tree = deleteNode(12,tree) fmt.Println("\n") middle := middleForeach(*tree,middle) fmt.Println(middle,"\n") } //Get node tree height, depth first func (tree binaryTree) getTreeHeight() int{ //Node none if tree.RightNode == nil && tree.LeftNode == nil { return 1 } leftHeight,rightHeight := 1,1 if tree.LeftNode != nil && tree.LeftNode.Value != 0 { leftHeight = 1 + tree.LeftNode.getTreeHeight() } if tree.RightNode != nil && tree.RightNode.Value != 0{ rightHeight = 1 + tree.RightNode.getTreeHeight() } //Compare left and right node tree heights height := math.Max(float64(leftHeight),float64(rightHeight)) return int(height) } //Check that the tree is balanced func (tree binaryTree) isBalance() bool { if tree.RightNode == nil && tree.LeftNode == nil { return true } //Equilibrium factor of nodes factor := tree.getTreeFactor() if factor > 1 || factor < -1 { return false } return true } //Gets the balance factor of the node func (tree binaryTree) getTreeFactor() int{ leftFactor,rightFactor := 0,0 if tree.RightNode != nil { rightFactor = tree.RightNode.getTreeHeight() } if tree.LeftNode != nil { leftFactor = tree.LeftNode.getTreeHeight() } factor := float64(leftFactor - rightFactor) return int(factor) } //Create binary balance tree func createBinaryBalanceTree(nums []int) *binaryTree{ tree := new(binaryTree) for index := range nums{ node := &binaryTree{Value: nums[index]} tree = insertNode(tree,node) } return tree } //Insert node func insertNode(tree *binaryTree,node *binaryTree) *binaryTree { if tree.Value == 0 { return node } if tree.Value == node.Value { return tree }else if tree.Value > node.Value { //Go to the left subtree. If it is empty, insert the node directly if tree.LeftNode == nil { tree.LeftNode = node }else { tree.LeftNode = insertNode(tree.LeftNode,node) } //Node height reset tree.LeftNode.Height = tree.LeftNode.getTreeHeight() }else { //Go to the right subtree. If it is empty, insert the node directly if tree.RightNode == nil { tree.RightNode = node }else { tree.RightNode = insertNode(tree.RightNode,node) } //Node height reset tree.RightNode.Height = tree.RightNode.getTreeHeight() } //Node height reset tree.Height = tree.getTreeHeight() //Node imbalance if !tree.isBalance() { //tree = treeInsertRotateBalance(node,tree) //Left subtree too large if tree.getTreeFactor() > 1 { if node.Value < tree.LeftNode.Value { tree = LeftLeftRotate(tree) }else { tree = LeftRightRotate(tree) } }else { //The right subtree is too large if node.Value > tree.RightNode.Value { tree = RightRightRotate(tree) }else { tree = RightLightRotate(tree) } } } return tree } //Delete node func deleteNode(num int,tree *binaryTree) *binaryTree{ //First check whether the deleted value exists in the tree find := findNode(num,tree) if find { //Configure the node value and perform the deletion operation if tree.Value == num { //The deleted node has no left and right nodes if tree.LeftNode == nil && tree.RightNode == nil { tree = &binaryTree{} }else if tree.LeftNode == nil && tree.RightNode != nil { //The left node is empty, and the right node is not empty tree = tree.RightNode }else if tree.RightNode == nil && tree.LeftNode != nil { //The right node is empty, and the left node is not empty tree = tree.LeftNode }else{ //Both left and right nodes exist tree = replaceNode(tree) } }else if tree.Value > num { tree.LeftNode = deleteNode(num,tree.LeftNode) }else { tree.RightNode = deleteNode(num,tree.RightNode) } tree.Height = tree.getTreeHeight() } if !tree.isBalance() { if tree.getTreeFactor() > 1 { if num > tree.Value { tree = LeftLeftRotate(tree) }else { tree = LeftRightRotate(tree) } }else { if num < tree.Value { tree = RightRightRotate(tree) }else { tree = RightLightRotate(tree) } } } return tree } //Replace delete node func replaceNode(tree *binaryTree) *binaryTree{ //The deleted node has no left and right nodes if tree.LeftNode == nil && tree.RightNode == nil { tree = &binaryTree{} }else if tree.LeftNode == nil && tree.RightNode != nil { //The left node is empty, and the right node is not empty tree = tree.RightNode }else if tree.RightNode == nil && tree.LeftNode != nil { //The right node is empty, and the left node is not empty tree = tree.LeftNode }else{ //If both left and right nodes exist, find the node from the right subtree to replace the parent node //If there are no left and right nodes under the right node, it is directly replaced with the value of the right node and the right node is deleted if tree.RightNode.LeftNode == nil && tree.RightNode.RightNode == nil { tree.Value = tree.RightNode.Value tree.RightNode = &binaryTree{} }else if tree.RightNode.LeftNode == nil && tree.RightNode.RightNode != nil { //If the left node under the right node is empty and the right node is not empty, the value of the right node is replaced and the right node of the right node is replaced tree.Value = tree.RightNode.Value tree.RightNode = tree.RightNode.RightNode }else{ //If the left node of the right node is not empty tree.Value = tree.RightNode.LeftNode.Value tree.RightNode.LeftNode = replaceNode(tree.RightNode.LeftNode) } } return tree } //Left left situation func LeftLeftRotate(tree *binaryTree) *binaryTree{ //The left node of the original node becomes the root node mainNode := tree.LeftNode changeNode := &binaryTree{} //Judge whether the left node of the original node exists if mainNode.RightNode != nil { changeNode = mainNode.RightNode } mainRightNode := tree mainRightNode.LeftNode = changeNode //Refresh tree height mainRightNode.Height = mainRightNode.getTreeHeight() mainNode.RightNode = mainRightNode mainNode.Height = mainNode.getTreeHeight() return mainNode } //Right right situation func RightRightRotate(tree *binaryTree) *binaryTree{ mainNode := tree.RightNode changeNode := &binaryTree{} if mainNode.LeftNode != nil { changeNode = mainNode.LeftNode } mainLeftNode := tree mainLeftNode.RightNode = changeNode mainLeftNode.Height = mainLeftNode.getTreeHeight() mainNode.LeftNode = mainLeftNode mainNode.Height = mainNode.getTreeHeight() return mainNode } //Control situation func LeftRightRotate(tree *binaryTree) *binaryTree{ mainLeftNode := tree.LeftNode changeNode := &binaryTree{} mainNode := mainLeftNode.RightNode if mainNode.LeftNode != nil { changeNode = mainNode.LeftNode } mainLeftNode.RightNode = changeNode mainLeftNode.Height = mainLeftNode.getTreeHeight() mainNode.LeftNode = mainLeftNode mainNode.Height = mainNode.getTreeHeight() tree.LeftNode = mainNode tree = LeftLeftRotate(tree) return tree } //Right left situation func RightLightRotate(tree *binaryTree) *binaryTree{ mainRightNode := tree.RightNode changeNode := &binaryTree{} mainNode := mainRightNode.LeftNode if mainNode.RightNode != nil { changeNode = mainNode.RightNode } mainRightNode.LeftNode = changeNode mainRightNode.Height = mainRightNode.getTreeHeight() mainNode.RightNode = mainRightNode mainNode.Height = mainNode.getTreeHeight() tree.RightNode = mainNode tree = RightRightRotate(tree) return tree } //Node lookup func findNode(num int,tree *binaryTree) bool{ targetNode := tree for targetNode != nil{ if targetNode.Value == num { return true }else if targetNode.Value > num { targetNode = targetNode.LeftNode }else { targetNode = targetNode.RightNode } } return false } //Medium order traversal func middleForeach(tree binaryTree,num []int) []int{ var leftNum,rightNum []int //If there is a left node, traverse the left node tree if tree.LeftNode != nil { leftNum = middleForeach(*tree.LeftNode,leftNum) for _,value := range leftNum{ num = append(num,value) } } //Traverse the root node first if tree.Value != 0 { num = append(num,tree.Value) } //If there is a right node, traverse the right node tree if tree.RightNode != nil { rightNum = middleForeach(*tree.RightNode,rightNum) for _,value := range rightNum{ num = append(num,value) } } return num }

The code implementation is relatively complex. It is still a little difficult to write at the beginning, but after completion, I find it has brought me a great sense of achievement. Maybe this is also the fun of writing code. The follow-up meeting will continue to study and strive to realize the red and black tree.