简介
2-3树
“2-3树”是由Aho, Hopcroft和Ullman提出, 它是这样的树:在树中每个结点都有2个或3个子树, 而且从根到叶的每条路径都是等长的;由单个节点组成的树也是“2-3树”。如图《2-3树》所示, 是具有六片叶子的“2-3树”, 这里每个叶结点存放一个关键字值, 每一个非叶结点存放两个值, 这两个值分别是第一个 (最左) 子树中最大关键字值, 和该结点第二个 (中) 子树最大关键字值。非叶结点这两个值能从树的根出发, 用类似于二分搜索的方式来搜索树中某一元素。
通过对“2-3树”的改造, 形成一种新的数据结构，即平衡树 (BT) 。BT解决了“2-3树”实现集合表示的存储空间利用率低问题。同时可以实现求集合的并、交、差、测集合包含关系操作。
性质与基本算法
性质：高为h的BT, 其结点的数目在2^(h+1)-1和1/2(3^(h+1)−1)之间, 叶的数目在2^h和3^h之间。
证明：BT退化为每个结点 (非叶) 只有两棵子树时, 结点的数目最少, 叶子也最少。设层号为i则各层结点数为2^(i-1)个, 那么高为h的BT最大层号是j时, 有h=j-1。整个树的结点数为s=2^0+2^1+2^2+…+2^h, 故s=2^(h+1)-1。其叶子的个数是2^h。同理, 当BT每个非叶结点都有三棵子数时, 结点数目最多。此时结点数为：
s=3^0+3^1+3^2+⋯+3^h‚s=1/2(3^(h+1)−1)，其叶子的个数是3^h。
中根遍历算法:
中根遍历的结果是:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13。
先根遍历算法：
先根遍历的结果是:9, 3, 1, 2, 4, 7, 5, 6, 8, 12, 10, 11, 13。
后根遍历算法：
后根遍历的结果是:1, 2, 4, 3, 5, 6, 8, 7, 10, 11, 13, 12, 9。
应用
在智能电网中，与传统路由协议不同，突发性拥塞不再是数据采集的主要风险，风险的新来源是数据流过度集中在网络的关键节点而导致的拥塞。为此,提出了一种能够实现数据平衡的数据采集路由机制用以克服网络拥塞。该机制抽象出配用通信网络的数学模型;其次,针对无线网状网络(WMNs)路由协议,以节点排队队列长度作为决策参数建立路由度量模型(数据平衡度量模型,DBMM),并以度量值最小作为决策条件,设计了基于平衡树的路由算法(基于DBMM的路由算法,RA-DBMM)。有效地改善数据拥塞问题,提高系统可靠性和吞吐量。
