자료구조 및 알고리즘 10 - 2-3 Tree and 2-3-4 Tree

0. 2-3 Tree

 

Likewise, 2-3 Tree is also a height balanced tree. The time complextity of search/insert/delete is O(logN)(* A 2-3 tree is a B tree of order 3)

 

1. Properties of 2-3 tree

 

• Nodes with two children are called 2-nodes. The 2-nodes have one data value(* one key) and two children
• Nodes with three children are called 3-nodes. The 3-nodes have two data value(* two keys) and three children
• That means 2-3 tree is not allowed to have a single child node
• Data(* keys) is stored in sorted order
• It is a balanced tree
• All the leaf nodes are at the same level
• Each node can either be leaf, 2 node or 3 node
• Always insertion is done at leaf

 

2. Prove the height

 

2-3 tree of height h has at least 1+2+...+2^h = 2^(h+1) - 1 nodes and at most 1+3+...+3^h = (3^(h+1) - 1) / 2 nodes

 

therefore, we can say the lower bounds of nodes is 2^(h+1) - 1 and the upper bounds of nodes is (3^(h+1) - 1) / 2

In other words, the lower bounds of height is log2(h+1) and the upper bounds of nodes is log3(h+1)

 

3. Search

 

Search is the operation where we are given the root node and target value. If the value is available in the tree, it returns true, otherwise it'll return false

 

There might be 3 cases in Search operation;

• case 1:
  • If the current node is signle-valued(* 2-nodes) and the value is lesser than the node's value, then call the recursive function for the left child.
  • Else, call the recursive function for the right child
• case 2:
  • If the current node is double valued(* 3-nodes), and if the value is lesser than the left value, then call the recursive function for the left child.
  • If the target element is greater than the current node's left value and lesser than the current node's right value, then call the recursive function for middle child
  • Else, call the recursive function for the right child
• base case: 
  • As we know, the recursion base is the most important condition which helps to terminate the recursive calls. If the current node is null, then we will return false, or if the current nodes's value is equal to the target element, then we will return true

 

4. Insertion

 

If we want to insert any element in the tree, then we will find its correct position, and then we will insert it. We can have three cases in the insertion operation.

• case 1:
  • Suppose the node at which we want to put the element contains a single value. In this case, we will simply insert the element
  • For example, Insert 60:

• case 2:
  • If the node at which we want to insert the target element contains the double value and its parent is single-valued, then we will put the element at the node, and the middle value of the node will be shifted to its parent. And the current node will be split into two separate nodes.
  • For example. Insert 14:

• case 3:
  • If the node at which we want to insert is a double-valued node and its parent is also a double-valued node. We will shift the middle element to the parent node and split the current node. Now its parent has three values, so it will also shift its middle element to its parent node and split the parent node into two separate nodes.

 

5. Deletion

 

A value is removed after being replaced by its in-order successor in order to be deleted. Two nodes must be combined together if a node has less than one data value remaining. After removing a value, a node is merged with another if it becomes empty.

https://velog.io/@chanyoung1998/B%ED%8A%B8%EB%A6%AC

B-트리(B-Tree)란? B트리 탐색, 삽입, 삭제 과정

 

 

 

 

 

 

---

 

 

 

 

 

0. 2-3-4 Tree

 

Likewise, 2-3-4 tree(* also called a 2-4 tree) is a self-balancing data structure that can be used to implement dictionaries. The numbers mean a tree where every node with children has either two, three or four child nodes:

• a 2-node has one data element, and if internal has two child nodes
• a 3-node has two data elements, and if internal has three child nodes
• a 4-node has three data elements, and if internal has four child nodes

 

1. Properties

• Every node(leaf or internal) is a 2-node, 3-node or 4-node, and holds one, two, three data elements.
• All leaves are at the same depth(the bottom level)
• All data is kept in sorted order

 

2. Insertion and Deletion

 

We could tell the Insertion and Deletion operation in 2-3-4 tree are similar with 2-3 tree. The different thing in these operations between those two is only the number of keys and children. 

 

The important thing about 2-3-4 tree is we can split nodes during going down to the leaf. Basically it takes at least 3 nodes to split elements of some node. so now on, we can split itself before inserting any element because the max # of element is 3 in 2-3-4 tree. That may make improvement about the performance of operations because we don't need to go up to split the node.