ต้นไม้ 2–3–4

Image:2-3-4-tree-2-node.svg|2-โหนด
Image:2-3-4-tree-3-node.svg|3-โหนด
Image:2-3-4-tree-4-node.svg|4-โหนด

**ต้นไม้ 2-3-4** () หรือเรียกอีกอย่างหนึ่งว่า **ต้นไม้ 2-4** เป็นโครงสร้างข้อมูลแบบต้นไม้ได้ดุล คือจัดสมดุลด้วยตัวเองเมื่อมีการเพิ่มหรือลบข้อมูล ซึ่งโดยทั่วไปจะนำไปใช้เป็นส่วนหนึ่งในการทำระบบพจนานุกรม โดยพื้นฐานเหมือนกับต้นไม้บี (B-trees) ที่สามารถค้นหา เพิ่ม และ ลบข้อมูล ในเวลา O(log n) และ คุณสมบัติอย่างหนึ่งที่สำคัญของ 2-3-4 tree คือ ใบ (leaf หรือ external nodes) มีการประกันความสูงเป็น O(log n) ซึ่งมีความลึกเท่ากัน

**ตัวเลข 2 3 และ 4 บอกถึงรูปแบบของ node ที่ใช้ใน tree มี 3 แบบ ดังนี้**

#ปมแบบ 2 (2-node) คือ ใน 1 node จะมีข้อมูล 1 ตัว และมี child node ได้ 2 nodes
#ปมแบบ 3 (3-node) คือ ใน 1 node จะมีข้อมูล 2 ตัว และมี child node ได้ 3 nodes
#ปมแบบ 4 (4-node) คือ ใน 1 node จะมีข้อมูล 3 ตัว และมี child node ได้ 4 nodes

## คุณสมบัติ
#แต่ละโหนดเก็บค่าได้มากที่สุด 3 ค่า
#โหนดภายในแต่ละโหนดคือโหนด 2 โหนด 3 โหนดหรือ 4 โหนด
#Leaf node ทั้งหมดอยู่ในระดับเดียวกัน
#ทุก ๆ left child node ต้องมีค่าน้อยกว่า parent node
#ทุก ๆ right child node ต้องมีค่ามากกว่า parent node  

### ข้อแตกต่างระหว่าง ต้นไม้ 2-3-4 กับ ต้นไม้แดงดำ
ต้นไม้ 2-3-4 (2-3-4 tree) มีโครงสร้างเหมือนกับ ต้นไม้แดงดำ(red-black trees) เพราะ ต้นไม้แดงดำประยุกต์แนวคิดมาจาก ต้นไม้ 2-3-4 ซึ่งทุก ๆ ต้นไม้ 2-3-4 จะมี ต้นไม้แดงดำ อย่างน้อย 1 ต้นกับ data element ในอันดับเดียวกัน แล้วการเพิ่มและลบข้อมูลของ 2-3-4 trees ที่ทำให้แต่ละ node ขยาย แยก หรือรวมกัน ก็เหมือนกับการสลับสีและการหมุนของ node ใน red-black trees และการจะ implement 2-3-4 trees ในการเขียนโปรแกรมมักจะยาก เพราะมีกรณีเฉพาะที่เกี่ยวข้องกับการทำงานของต้นไม้แบบนี้เยอะ ส่วนใหญ่จึงหันไปใช้ red-black trees แทนเพราะ implement ได้ง่ายกว่า

### การค้นหาข้อมูล
เริ่มจาก root node แล้วทำการเปรียบเทียบค่าที่ต้องการหา ถ้าค่าที่ต้องการหาไม่ได้อยู่ใน root node ให้เปรีบบเทียบค่าใน root node ว่าควรเลือกเส้นทางไหนใน node ถัดไป แล้วทำการเปรียบเทียบค่าต่อไปเรื่อย ๆ จนกว่าจะพบข้อมูลที่ต้องการหาหรือเจอ null
center|thumb|412.986x412.986px|เป็นการค้นหาภายในต้นไม้ 2-3-4

### การเพิ่มข้อมูล
เริ่มต้นที่ root node โดยจะแยกได้ดังนี้

#ถ้า node ปัจจุบันเป็น 4-node ให้นำค่าที่อยู่ตรงกลางไปเก็บไว้ และลบออกจาก node เพื่อให้ได้ 3-nodeแล้วแยก 3-node ที่เหลือออกเป็น 2-node 2 อัน
#*ถ้า node นี้เป็น root node (ซึ่งไม่มี parent) ค่าที่เก็บไว้จะเป็น root ใหม่ของ 2-node 2 อัน และความสูงของ tree เพิ่มขึ้น 1 แล้วย้อนกลับไปพิจารณาขั้นต่อไปที่ root
#*ถ้าไม่ใช่ ดันค่าที่เก็บไว้ขึ้นไปที่ parent node แล้วย้อนกลับไปพิจารณาขั้นต่อไปที่ parent
#หา child node ที่มีช่วงของค่าที่จะทำการเพิ่ม
#*ถ้า child node นั้นเป็นใบ ใส่ค่าที่จะทำการเพิ่มเข้าไปใน node นั้นเป็นอันเสร็จสิ้น
#*ถ้าไม่ใช่ลงไปที่ child node ของ node นั้น และเริ่มทำ step 1 ใหม่
center|thumb|393.976x393.976px|ขั้นตอนแรก
center|thumb|403.993x403.993px|ขั้นตอนที่สอง

### การลบข้อมูล
#ขั้นแรกต้องหาข้อมูลที่จะทำการลบให้เจอก่อน โดยการลบข้อมูลนั้นจะเกิดขึ้นใน leaf node เสมอ
#ถ้าค่าที่จะลบอยู่ใน leaf node และ node นั้นเป็น 3-node หรือ 4-node ค่าจะถูกลบออกจาก node และจะกลายเป็น 2-node หรือ 3-node ตามลำดับ
#:center|thumb|410.99x410.99px|กรณีที่เลขที่ต้องการลบอยู่ใน leaf node และเป็น 3-node
#ถ้าข้อมูลที่จะต้องการลบอยู่ใน 2-node เมื่อลบข้อมูลแล้ว node นี้จะหายไป เรียกว่า underflow โดยจะถ่ายโอนค่าจากโหนดหลักไปยังโหนดที่เกิด underflow และถ่ายโอนค่าจาก sibling node (คือ node ที่มี parent เดียวกัน) ที่เป็น 3-node หรือ 4-node
#:center|thumb|228x228px|กรณีที่เลขที่ต้องการลบอยู่ใน leaf nodeและเป็น 2-node
#ถ้า node ที่ underflow เกิดขึ้นไม่มี sibling node ที่เป็น 3-node หรือ 4-node จะเกิดการรวม (fused) 2 sibling node เข้าด้วยกัน
#:center|thumb|412.986x412.986px|กรณีที่เลขที่ต้องการลบอยู่ใน leaf node และเป็น 2-node แต่ sibling node เป็น 2-node ทั้งหมด
#ถ้าค่าที่จะลบไม่ได้อยู่ใน leaf node ก็จะถูกแทนที่ด้วยบรรพบุรุษของมันทันที และค่าก่อนจะถูกลบออกจาก tree
#:center|thumb|415.99x415.99px|กรณีที่เลขที่ต้องการลบไม่ได้อยู่ใน leaf node ดังนั้น child node ที่จะนำมาแทนที่ต้องเป็น 3-node หรือ 4-node

### ความซับซ้อนของเวลา
การค้นหาข้อมูลจะใช้เวลา O(log n) เนื่องจากต้นไม้มีความสมดุลอยู่เสมอ

การแทรกจะใช้เวลา O(log n) เนื่องจากการแบ่งแยกทั้งหมดเป็น Conversion และเราไม่จำเป็นต้องมีการส่งผ่านหลายครั้งบนต้นไม้

การลบจะใช้เวลา O(log n) เมื่อพิจารณาการหมุน / ฟิวชั่น เป็น O(1) ทั้งหมด

ความสูงของต้นไม้ที่เลวร้ายที่สุดคือ log n เมื่อโหนดทั้งหมดเป็น 2-nodes

ความสูงของต้นไม้กรณีที่ดีที่สุดคือ 1/2 log n เมื่อโหนดทั้งหมดเป็น 4-nodes

### Code Python การค้นหาข้อมูล

```python3
def Search(self, key):
        pCurNode = self._pRoot  # start at root
        while True:
            childNumber = pCurNode.findItem(key)
            if childNumber != -1:
                return True  # childNumber	#found it
            elif pCurNode.isLeaf():
                return False  # can't find it
            else:  # search deeper
                pCurNode = self.getNextChild(pCurNode, key)
```


### Code Python การเพิ่มข้อมูล

```python3
def insert(self, Value):  # insert a DataItem
        pCurNode = self._pRoot
        pTempItem = DataItem(Value)

        while True:
            if pCurNode.isFull():  # if node full,
                self.split(pCurNode)  # split it
                pCurNode = pCurNode.getParent()  # back up
                # search once
                pCurNode = self.getNextChild(pCurNode, Value)
            # end if(node is full)

            elif pCurNode.isLeaf():  # if node is leaf,
                break  # go insert
            # node is not full, not a leaf; so go to lower level
            else:
                pCurNode = self.getNextChild(pCurNode, Value)
        # end while
        pCurNode.insertItem(pTempItem)  # insert new item
```


## อ้างอิง
Dusk 2-3-4 tree ค้นหาเมื่อ 7 พฤษภาคม 2561

azrael 2-3-4 Tree Delete Example ค้นหาเมื่อ 7 พฤษภาคม 2561

freedman 2-3-4 Trees    ค้นหาเมื่อ 7 พฤษภาคม 2561

สมชาย ประสิทธิ์จูตระกูล โครงสร้างข้อมูล: 12.4 ต้นไม้ค้นหาแบบอื่น - ต้นไม้ 2-3-4 ค้นหาเมื่อ 7 พฤษภาคม 2561

หมวดหมู่:ต้นไม้บี