[發(fā)明專利]一種業(yè)務(wù)關(guān)系二叉樹節(jié)點(diǎn)修剪方法及裝置

在審

• 申請?zhí)枺?/td>: 201410320923.5
• 申請日: 2014-07-04
• 公開（公告）號(hào): CN104143152A
• 公開（公告）日: 2014-11-12
• 發(fā)明（設(shè)計(jì)）人: 易繼勇
• 申請（專利權(quán)）人: 北京思特奇信息技術(shù)股份有限公司
• 主分類號(hào): G06Q30/02
• 分類號(hào): G06Q30/02
• 代理公司: 北京輕創(chuàng)知識(shí)產(chǎn)權(quán)代理有限公司 11212
• 代理人: 楊立

技術(shù)領(lǐng)域

本發(fā)明涉及一種二叉樹節(jié)點(diǎn)修剪方法，特別涉及一種業(yè)務(wù)關(guān)系二叉樹節(jié)點(diǎn)修剪方法及裝置。

背景技術(shù)

業(yè)務(wù)關(guān)系二叉樹的定義：在電信系統(tǒng)中，一個(gè)套餐業(yè)務(wù)會(huì)包含多個(gè)子業(yè)務(wù)，不同的子業(yè)務(wù)對不同的場景和條件進(jìn)行優(yōu)惠，比如一個(gè)套餐業(yè)務(wù)X會(huì)包含：撥打長途優(yōu)惠子業(yè)務(wù)X1、漫游撥打優(yōu)惠子業(yè)務(wù)X2、本地?fù)艽騼?yōu)惠子業(yè)務(wù)X3、本地?fù)艽蛴H情號(hào)碼優(yōu)惠子業(yè)務(wù)X4，同時(shí)業(yè)務(wù)套餐的子業(yè)務(wù)之間會(huì)存在一些關(guān)系，比如互斥、疊加，如上業(yè)務(wù)套餐中子業(yè)務(wù)X1和X2之間肯定是互斥的關(guān)系，而子業(yè)務(wù)X3和X4的關(guān)系是可疊加優(yōu)惠的。為了描述這些子業(yè)務(wù)之間的關(guān)系，我們引入了業(yè)務(wù)關(guān)系二叉樹的概念。

話單的定義：就是用戶在撥打?qū)嶋H電話完成后產(chǎn)生的文件記錄(文件記錄包括比如：用戶撥打的地點(diǎn)、撥打?qū)Χ颂?hào)碼、通話時(shí)長等信息)，話單會(huì)按照用戶的在撥打的地點(diǎn)以及撥打的對方號(hào)碼，有一個(gè)簡單的分類，比如撥打長途、漫游撥打、本地?fù)艽颉⒈镜負(fù)艽蛴H情號(hào)等。

對用戶撥打的電話產(chǎn)生的話單進(jìn)行計(jì)費(fèi)，就是使用套餐業(yè)務(wù)關(guān)系二叉樹進(jìn)行遍歷訪問計(jì)費(fèi)的過程，默認(rèn)訪問順序是前序遍歷，對上述場景的計(jì)費(fèi)和二叉樹訪問舉例說明如下：

如果話單為撥打長途，假設(shè)遍歷訪問到X1，判斷話單是否滿足X1的條件，即X1子樹滿足條件，執(zhí)行優(yōu)惠，二叉樹的遍歷訪問結(jié)束。

如果話單為漫游撥打，話單不滿足X1節(jié)點(diǎn)條件，則繼續(xù)訪問，按照訪問的順序要訪問到X2，X2滿足話單條件，執(zhí)行優(yōu)惠，則停止二叉樹的遍歷。

如果話單為本地?fù)艽颍琗1和X2都不滿足，則需要繼續(xù)訪問，發(fā)現(xiàn)X3和X4的關(guān)系是可疊加，則需要判斷X3是否滿足和X4是否滿足條件，如果都滿足，則比較執(zhí)行優(yōu)惠，取優(yōu)惠量最大的子業(yè)務(wù)，二叉樹訪問結(jié)束。

如果話單為其他類型的話單，則整個(gè)二叉樹的子業(yè)務(wù)節(jié)點(diǎn)都不滿足條件，則整顆樹訪問結(jié)束后，不會(huì)執(zhí)行任何動(dòng)作。

通過上面的例子我們會(huì)發(fā)現(xiàn)，對于一個(gè)話單的不同場景而言，比如長途撥打，有效的子業(yè)務(wù)的個(gè)數(shù)是有限的，在實(shí)際處理過程中我們對針對不同的場景把原先的二叉樹進(jìn)行修剪，保留有用的滿足本場景的子業(yè)務(wù)節(jié)點(diǎn)，這樣減少遞歸的次數(shù)和邏輯判斷，提高計(jì)費(fèi)效率。

對業(yè)務(wù)關(guān)系二叉樹進(jìn)行修剪，一般的修剪規(guī)則為：對葉子節(jié)點(diǎn)進(jìn)行修剪，若葉子節(jié)點(diǎn)不滿足某種修剪場景的條件，則被修剪掉，另外相鄰的一個(gè)左或右節(jié)點(diǎn)代替被修剪掉葉子節(jié)點(diǎn)的父節(jié)點(diǎn)的位置。這樣就能得到精簡后的關(guān)系二叉樹，在后續(xù)算費(fèi)時(shí)，能減少二叉樹的遍歷以及匹配時(shí)間，提高計(jì)費(fèi)效率。

話單的定義：就是用戶在撥打?qū)嶋H電話完成后產(chǎn)生的文件記錄(文件記錄包括比如：用戶撥打的地點(diǎn)、撥打?qū)Χ颂?hào)碼、通話時(shí)長等信息)，話單會(huì)按照用戶的在撥打的地點(diǎn)以及撥打的對方號(hào)碼，有一個(gè)簡單的分類，比如撥打長途、漫游撥打、本地?fù)艽颉⒈镜負(fù)艽蛴H情號(hào)等。

對用戶撥打的電話產(chǎn)生的話單進(jìn)行計(jì)費(fèi)，就是使用套餐業(yè)務(wù)關(guān)系二叉樹進(jìn)行遍歷訪問計(jì)費(fèi)的過程，默認(rèn)訪問順序是前序遍歷，對上述場景的計(jì)費(fèi)和二叉樹訪問舉例說明如下：

如果話單為撥打長途，假設(shè)遍歷訪問到X1，判斷話單是否滿足X1的條件，即X1子樹滿足條件，執(zhí)行優(yōu)惠，二叉樹的遍歷訪問結(jié)束。

如果話單為漫游撥打，話單不滿足X1節(jié)點(diǎn)條件，則繼續(xù)訪問，按照訪問的順序要訪問到X2，X2滿足話單條件，執(zhí)行優(yōu)惠，則停止二叉樹的遍歷。

如果話單為本地?fù)艽颍琗1和X2都不滿足，則需要繼續(xù)訪問，發(fā)現(xiàn)X3和X4的關(guān)系是可疊加，則需要判斷X3是否滿足和X4是否滿足條件，如果都滿足，則比較執(zhí)行優(yōu)惠，取優(yōu)惠量最大的子業(yè)務(wù)，二叉樹訪問結(jié)束。

如果話單為其他類型的話單，則整個(gè)二叉樹的子業(yè)務(wù)節(jié)點(diǎn)都不滿足條件，則整顆樹訪問結(jié)束后，不會(huì)執(zhí)行任何動(dòng)作。

對于一個(gè)話單的不同場景而言，比如長途撥打，有效的子業(yè)務(wù)的個(gè)數(shù)是有限的，在實(shí)際處理過程中我們對針對不同的場景把原先的二叉樹進(jìn)行修剪，保留有用的滿足本場景的子業(yè)務(wù)節(jié)點(diǎn)，這樣減少遞歸的次數(shù)和邏輯判斷，提高計(jì)費(fèi)效率。

對業(yè)務(wù)關(guān)系二叉樹進(jìn)行修剪，一般的修剪規(guī)則為：對葉子節(jié)點(diǎn)進(jìn)行修剪，若葉子節(jié)點(diǎn)不滿足某種修剪場景的條件，則被修剪掉，另外相鄰的一個(gè)左或右節(jié)點(diǎn)代替被修剪掉葉子節(jié)點(diǎn)的父節(jié)點(diǎn)的位置。這樣就能得到精簡后的關(guān)系二叉樹，在后續(xù)算費(fèi)時(shí)，能減少二叉樹的遍歷以及匹配時(shí)間，提高計(jì)費(fèi)效率。

發(fā)明內(nèi)容

本發(fā)明所要解決的技術(shù)問題是提供一種節(jié)約存儲(chǔ)空間、同時(shí)減少時(shí)間損耗的業(yè)務(wù)關(guān)系二叉樹節(jié)點(diǎn)修剪方法及裝置。

本發(fā)明解決上述技術(shù)問題的技術(shù)方案如下：一種業(yè)務(wù)關(guān)系二叉樹節(jié)點(diǎn)修剪方法，包括以下步驟：