Lua 程式設計教學:二元搜尋樹 (Binary Search Tree)

PUBLISHED ON MAR 14, 2018 — PROGRAMMING

    樹 (tree) 是一種非線性、階層的資料結構,由於樹有數種變體,大部分教科書都會以二元搜尋樹 (binary search tree) 做為樹的實例。以二元搜尋樹存取資料,往往會比串列更有效率。

    由於程式碼略長,我們在這裡展示完整程式碼,讀者可自行觀看。

    一般來說,我們會先建立一個內部節點類別:

    local Node = {}
    
    Node.__index = Node
    
    function Node:new(data)
        self = {}
        
        self._data = data
        self.left = nil
        self.right = nil
        
        setmetatable(self, Node)
        return self
    end
    
    function Node:data()
        return self._data
    end

    接著,建立一個 Tree 物件,將 Node 物件包在裡面:

    function Tree:new()
        self = {}
        self._root = nil
        
        setmetatable(self, Tree)
        return self
    end

    二元搜尋樹在取得元素時,會利用遞迴的特性,在此處我們額外使用一個內部函式來遞迴走訪元素:

    local function contains(node, data)
        if node:data() == data then
            return true
        elseif data < node:data() then
            
            if node.left ~= nil then
                return contains(node.left, data)
            end
        else
            if node.right ~= nil then
                return contains(node.right, data)
            end
        end
        
        return false
    end
    
    function Tree:contains(data)
        if self._root == nil then
            return false
        end
        
        return contains(self._root, data)
    end

    插入元素時,會根據新的資料和現存的元素間的大小來決定插入的位置,日後才能快速搜尋:

    local function insert(node, data)
        if data >= node:data() then
            if node.right == nil then
                local nodeNew = Node:new(data)
                node.right = nodeNew
            else
                node.right = insert(node.right, data)         
            end
        else
            if node.left == nil then
                local nodeNew = Node:new(data)
                node.left = nodeNew
            else
                node.left = insert(node.left, data)
            end
        end
    
        return node
    end
    
    function Tree:insert(data)
        if self._root == nil then
            local node = Node:new(data)
            self._root = node
            return
        end
        
        self._root = insert(self._root, data)
    end

    移除時,也要根據不同的情境採取不同的措施:

    local function remove(node, data)
        if data > node:data() then
            if node.right == nil then
                return node, nil
            else
                node.right = remove(node.right, data)
            end
        elseif data < node:data() then
            if node.left == nil then
                return node, nil
            else
                node.left = remove(node.left, data)
            end
        else
            if node.left == nil and node.right == nil then
                return nil, data
            elseif node.left == nil then
                node = node.right
            elseif node.right == nil then
                node = node.left
            else
                node._data = node.right:data()
                node.right, _ = remove(node.right, node:data())
            end
        end
        
        return node, data
    end
    
    function Tree:remove(data)
        if self._root == nil then
            return nil
        end
        
        self._root, popped = remove(self._root, data)
    
        return popped
    end
    comments powered by Disqus