ต้นไม้ค้นหาไตรภาค

ในวิทยาการคอมพิวเตอร์ ต้นไม้ค้นหาไตรภาค (อังกฤษ: ternary search tree) เป็นทรัยประเภทหนึ่งซึ่งมีการจัดเรียงบัพแบบที่คล้ายกับต้นไม้ค้นหาทวิภาค แต่มีบัพลูกสามบัพแทนที่จะมีสองบัพ ต้นไม้ค้นหาไตรภาคสามารถใช้เป็นโครงสร้างแผนที่สัมพันธ์ที่มีความสามารถค้นหาสายอักขระแนวเดิม อย่างไรก็ดี ต้นไม้ค้นหาไตรนามใช้พื้นที่มีประสิทธิภาพกว่าเมื่อเทียบกับต้นไม้เติมหน้ามาตรฐานแต่มีความเร็วช้ากว่า การใช้ต้นไม้ค้นหาไตรภาคทั่วไป เช่น การตรวจสอบตัวสะกดและการเติมคำอัตโนมัติ

การดำเนินการของต้นไม้ค้นหาไตรภาค

•    ตัวชี้ซ้ายชี้ไปที่โหนดที่มีค่าต่ำกว่าค่าในโหนดปัจจุบัน (LEFT NODE)

•    ตัวชี้ที่เท่ากันชี้ไปที่โหนดที่มีค่าเท่ากับค่าในโหนดปัจจุบัน (MID NODE or EQUAL NODE)

•    ตัวชี้ด้านขวาชี้ไปที่โหนดที่มีค่ามากกว่าค่าในโหนดปัจจุบัน (RIGHT NODE)

ตัวอย่าง

                                                c
                                              / | \
                                             a  u  h
                                            |  |  | \
                                            t  t  e  u
                                          /  / |   / |
                                         s  p  e  i  s

จากกราฟนี้แสดงให้เห็นแต่ละโหนดที่ถูก insert หรือเพิ่มเข้ามาเป็นโครงสร้างของ TST โดยมีการเพิ่มข้อมูล "cute","cup","at","as","he","us" and "i" ตามลำดับ โดยข้อมูลที่ถูกเพิ่มเข้ามาก่อนนั้นจะเป็นกราฟ tree ที่อยู่ในตำแหล่งตรงกลาง และข้อมูลลำดับถัดไปหากลำดับตัวอักษรมีค่าน้อยกว่า parent node ก็จะเป็นกราฟ child node ที่อยู่ซ้ายมือ เช่นเดียวกันหากข้อมูลที่เพิ่มเข้ามามีค่าลำดับตัวอักษรมากกว่า parent node ก็จะอยู่ child node ขวามือ

CODE(PYTHON)

คุณสมบัติของโหนด

class Node:
    def __init__(self, data):
        self.data = data
        self.end = False
        self.left = None
        self.mid = None
        self.right = None
    def print_(self):
        return ''.join(['[', self.data,
                        ('' if not self.end else ' <end>'),
                        ('' if self.left is None else ' left: ' + self.left.print_()),
                        ('' if self.mid is None else ' mid: ' + self.mid.print_()),
                        ('' if self.right is None else ' right: ' + self.right.print_()), ']'])

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

def add(self, node, string):
    if len(string) == 0:
        return node
    head = string[0]
    tail = string[1:]
    if node is None:
        node = Node(head)
    if head < node.data:
        node.left = self.add(node.left,string)
    elif head > node.data:
        node.right = self.add(node.right,string)
    else:
        if len(tail) == 0:
            node.end = True
        else:
            node.mid = self.add(node.mid, tail)
    return node

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

def search(self, node, string):
    if node is None or len(string) == 0:
        return False
    head = string[0]
    tail = string[1:]
    if head < node.data:
        return self.search(node.left, string)
    elif head > node.data:
        return self.search(node.right, string)
    else:
        if len(tail) == 0 and node.end:
            return True
        return self.search(node.mid, tail)