Face the weakness and work hard!!Copy the code

The introduction

Red-black tree, B tree and B+ tree are all difficult to understand and master in software development. Their essence is still balanced binary search trees. If you go directly to learn red black tree, B tree, B+ tree knowledge, is no different from seeing flowers in a fog. This time we start with the underlying logic design of these data structures without any code level involvement.

The 234 trees

define

  • Two nodes

  • A key and two links left and right; The key is larger than the left link and smaller than the right link

  • Three points

  • Contains two keys and three links (the two keys are called key1 and key2, key1 is less than key2)

  • 1, 2, 3 (key of sublink 1 is less than root key1, key of sublink 2 is greater than root key1 and less than root key2, key of sublink 3 is greater than root key2)

  • Four nodes

  • Contains three keys and four sublinks (the three keys are key1, key2, key3 and in descending order)

  • 1, 2, 3, 4 (key of sublink 1 is less than root key1, key of sublink 2 is greater than root key1 and less than root key2, key of sublink 3 is greater than root key2 and less than root key3, key of sublink 4 is greater than root key3)

  • The above node count refers to the number of sublinks, not the number of keys the node contains

operation

Because the query operation of 2, 3 and 4 trees is consistent with the operation of binary search tree, it is no longer redundant. This section describes the insert and delete operations

You can refer to the previous article to familiarize yourself with some basic definitions and operations of binary trees

Binary Search Tree (BST)

Balanced binary tree (AVL)

insert

We took the numbers 1-10 and we took them and we put them into a 234 tree

Insert 1, 2, and 3 nodes in sequence

To insert four nodes, you need to split the four nodes into three two nodes

At this point, the introduction of insertion logic is complete

delete

Node deletion logic, and binary tree deletion logic is not very different. If it is a leaf node, you can delete it directly. If a non-leaf node needs to be converted to a successor/precursor node deletion mode, all can be converted to extreme value deletion

Non-2 nodes are deleted

2 Node deletion Deletion

If you delete two nodes, you need to delete three or four nodes

The parent node is not 2 nodes, and the sibling node is 2 nodes

The parent node is a non-2 node, and the sibling node is a non-2 node

The parent node is 2 nodes, and the sibling node is not 2 nodes

The parent node is 2 nodes, and the sibling node is 2 nodes

At this point, our 234 tree insert and delete operations introduced. Make it clear that 234 tree inserts and deletes will be preconditions for subsequent red-black trees, B-trees, and B-+ trees.

We are currently sorting out the contents of red black tree, B tree and B+ tree, please stay tuned. Also welcome to share and forward!

A series of

“Programmer inner power center method — Search binary Tree”

Programmer’s Inner power Method — AVL Tree

“Programmer’s Inner Core Method — 234 Trees”

Welcome everyone to pay attention to javascript art, share and communicate with me!