Binary search tree (binary search tree)

Binary search tree is also called binary search tree, also called binary sort tree, it has the following characteristics:

  1. If the left subtree is not empty, the value of the nodes in the left subtree is less than the root node.
  2. If the right subtree is not empty, then the value of the nodes in the right subtree is greater than the root node.
  3. Subtrees also follow these two points.

Binary tree traversal

Binary tree traversal methods: pre-order traversal, middle-order traversal, post-order traversal and hierarchical traversal (MySql).

As long as a tree is a binary lookup tree, its middle-order traversal (left root and right output) must be ordered. For example, look at a binary tree below:

Its preorder traversal (root left and right) is: 530468; Its middle-order traversal (left root right) is: 034568; Its post-order traversal (left and right roots) is: 043865.

What are the applications of binary search trees?

Since it’s a search tree, it must be used for lookups. Let’s analyze its search time complexity:

Let’s start with the following two binary search trees:

The search time complexity is really the depth of the tree.

The time complexity of figure 1: O(n) time complexity, which means that n times of searching, i.e. n times of cycling, are needed to degenerate into a linked list.

The time complexity of figure 2 (similar to binary search) : logn, i.e. 2x=n(tree height)2^x=n(tree height)2x=n(tree height) => x= log2nlog_2nlog2n => logn.

So why does it degenerate into a linked list (Figure 1)? How can we handle it so that it doesn’t become a linked list?

When the value of the inserted node increases from small to large, the binary tree will degenerate into a linked list. Then there is another kind of tree to solve this situation, which is the balanced binary tree (AVL tree).

AVL tree is a binary search tree that pursues the ultimate balance, that is, the tree is adjusted to the optimal situation. Since this tree structure is more demanding and there are many rotations, it will not be discussed here.

Red and black tree

The origin of red black trees

What I want to focus on today is red-black trees. The underlying data structure of red-black tree is binary search tree, that is to say, red-black tree is a special binary search tree, also called self-balanced binary search tree.

The purpose of red-black trees is to solve the problem that binary trees degenerate into linked lists.

The evolution of red-black trees

Linked list -> binary tree -> binary lookup tree -> special binary lookup tree (self-balanced binary lookup tree)

Red and black explanation

Through the above example and the two figures, we found that the structure of binary tree determines the efficiency and performance of its search, so how to optimize the binary tree?

Hence the red-black tree, which we can see below:

Properties of red-black trees:

  1. Each node is either red or black.
  2. There must be no red nodes joined together
  3. The root node (the first node) is black root
  4. The two byte points of each red node are black
  5. All leaf nodes are black (in fact, there are null leaf nodes in the figure above), as shown below:

So if we have these properties, or if we have trees that satisfy these properties, then we have an approximate equilibrium.

How do you determine if a node is root?

  • No parent node
  • A node with an entry degree of 0

Red black tree transformation rules

What do you need to do to the tree to satisfy these properties?

In order for red black to satisfy these properties, so there is rotation, how many transformation rules do red black trees have?

There are three transformation rules:

  • Discoloration: red to black black to red
  • Left rotation
  • Right rotation

Left rotation example:

Rotation and color transformation rules: all insertion points default to red;

  1. If the parent node and uncle node of the inserted node are red, then: 1) Set the parent node and uncle node to black; 2) Set the grandfather node to red; 3) Position the pointer to grandpa node as the node to be operated, and then judge the operation according to the transformation rules.
  2. Left-rotation: If the current parent node is red, the uncle node is black, and the current node is a right subtree, the parent node is required as the left rotation.
  3. Dextral: the current parent node is red, the uncle node is black, and the current node is the left child tree, then: 1) the parent node becomes black; 2) Turn grandpa node red; 3) Rotate right with the parent node.

For example, to insert the number 6 into the image above, the red and black star would evolve as follows:

Step1: after 6 nodes are inserted, see the figure below. Its parent node and uncle node are both red, so it needs to operate according to the transformation rules, and step2 is required.

Step2: According to the transformation rules, both the parent node and the uncle node of the inserted node should be turned into black, and the grandfather node should be turned into red, and then the pointer should be positioned to the grandfather node (blue circle). After the pointer is positioned to grandpa node (12), it is now the node to be operated and judged according to the transformation rules. It can be seen that the uncle node of the current node (12) in the following figure is black, so the case of changing color rules cannot be used. Step3 is performed to perform left or right rotation at this time.

Step3: according to the figure above, it can be known that the current node (12) conforms to the left-rotation rule: the parent node (5) is red, the uncle node (3) is black, and the current node is the right subtree. The next step is to perform a left-handed transformation (in three steps) :

Step4: after left-rotation transformation, it can be seen that the parent node (12) of the current node (5) is red and the uncle node (30) is black, and the current node is a left subtree, which conforms to the rule of right-rotation. 1) Change the parent node (12) to black; 2) Change grandfather node (29) to red; 3) Rotate right with parent node (12)

summary

So here, you can see that after many rotations, this tree is red and black.

The Golang code implements a red-black tree

Directly on the code, as follows:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

const (
	RED bool = true
	BLACK bool = false
)

type Node struct {
	key int
	value interface{}

	left *Node
	right *Node
	//parent *Node

	color bool
}

type RedBlackTree struct {
	size int
	root *Node
}

func NewNode(key, val int) *Node {
	// Add red nodes by default
	return &Node{
		key:    key,
		value:  val,
		left:   nil,
		right:  nil.//parent: nil,
		color:  RED,
	}
}

func NewRedBlackTree(a) *RedBlackTree {
	return &RedBlackTree{}
}

func (n *Node) IsRed(a) bool {
	if n == nil {
		return BLACK
	}
	return n.color
}

func (tree *RedBlackTree) GetTreeSize(a) int {
	return tree.size
}

// node x
// / rotate left / \
// T1 x ---------> node T3
// / \ /
// T2 T3 T1 T2
func (n *Node) leftRotate(a) *Node {
	/ / left rotation
	retNode := n.right
	n.right = retNode.left

	retNode.left = n
	retNode.color = n.color
	n.color = RED

	return retNode
}

// node x
// / rotate right / \
// x T2 -------> y node
// / \ /
// y T1 T1 T2
func (n *Node) rightRotate(a) *Node {
	/ / right turn
	retNode := n.left
	n.left = retNode.right

	retNode.right = n
	retNode.color = n.color
	n.color = RED

	return retNode
}

// Color change
func (n *Node) flipColors(a) {
	n.color = RED
	n.left.color = BLACK
	n.right.color = BLACK
}

// Maintain red-black trees
func (n *Node) updateRedBlackTree(isAdd int) *Node {
	// isAdd=0 Indicates that there is no new node and no maintenance is required
	if isAdd == 0 {
		return n
	}

	// Needs maintenance
	ifn.right.IsRed() == RED && n.left.IsRed() ! = RED { n = n.leftRotate() }// Check if case 3 is true, yes right rotation is required
	if n.left.IsRed() == RED && n.left.left.IsRed() == RED {
		n = n.rightRotate()
	}

	// Check if case 4 requires color reversal
	if n.left.IsRed() == RED && n.right.IsRed() == RED {
		n.flipColors()
	}

	return n
}

// Insert key,val into the root node of the tree
// Returns 1, which means the node is added
// Return 0, indicating that no new node is added, but only the value corresponding to the key is updated
func (n *Node) add(key, val int) (int, *Node) {
	if n == nil {	// The red node is inserted by default
		return 1, NewNode(key, val)
	}

	isAdd := 0
	if key < n.key {
		isAdd, n.left = n.left.add(key, val)
	} else if key > n.key {
		isAdd, n.right = n.right.add(key, val)
	} else {
		// The number of nodes does not increase. IsAdd = 0
		n.value = val
	}

	// Maintain red-black trees
	n = n.updateRedBlackTree(isAdd)

	return isAdd, n
}

func (tree *RedBlackTree) Add(key, val int)  {
	isAdd, nd := tree.root.add(key, val)
	tree.size += isAdd
	tree.root = nd
	tree.root.color = BLACK // The root node is black
}

// Print key,val,color
func (tree *RedBlackTree) PrintPreOrder(a) {
	resp := make([] []interface{}, 0)
	tree.root.printPreOrder(&resp)
	fmt.Println(resp)
}

func (n *Node) printPreOrder(resp *[][]interface{}) {
	if n == nil {
		return
	}
	*resp = append(*resp, []interface{}{n.key, n.value, n.color})
	n.left.printPreOrder(resp)
	n.right.printPreOrder(resp)
}


// Test the red-black tree code
func main(a) {
	count := 10
	redBlackTree := NewRedBlackTree()
	nums := make([]int.0)
	for i := 0; i < count; i++ {
		nums = append(nums, rand.Intn(count))
	}

	fmt.Println("source data: ", nums)
	now := time.Now()
	for _, v := range nums {
		redBlackTree.Add(v, v)
	}

	fmt.Println("redBlackTree:", now.Sub(time.Now()))
	redBlackTree.PrintPreOrder()
	fmt.Println("Node number :", redBlackTree.GetTreeSize())
}
Copy the code

The test output is as follows:

data source: [1 7 7 9 1 8 5 0 6 0]
redBlackTree: 2.136(including s [[7 7 false] [1 1 true] [0 0 false] [6 6 false] [5 5 true] [9 9 false] [8 8 true] Number of nodes:7
Copy the code

conclusion

A red-black tree is a binary tree that is approximately balanced, but in another way a red-black tree is not a balanced binary tree, and its maximum height is 2 logn.

Binary search tree, AVL tree, red-black tree comparison:

  1. For completely random data sources, ordinary binary search trees work well, but they tend to degenerate into linked lists in extreme cases
  2. For query-heavy usage, the AVL tree works well because its height remains h=logn
  3. Red-black trees sacrifice balance, that is, h=2*logn, but they have an advantage over AVL trees in addition and deletion operations
  4. The statistical performance of red-black tree is better by adding, deleting, modifying and searching all operations