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