学步园

参考原文(原文作者：Timothy J. Rolfe

)：http://penguin.ewu.edu/~trolfe/DSWpaper/

DSW算法用于平衡BST（二叉查找树），而且平衡后的二叉树是一颗完全二叉树(complete binary tree-即叶子节点顶多位于最后两层，而且从左到右排列)。该算法的优点是：无须开辟额外的空间用于存储节点，时间复杂度线性O(n)。该算法分两个阶段进行：首先将任意一颗二叉树通过一序列右旋转(right rotations)转换成一个单链结构（称作vine，即每个非叶子节点只有右孩子，没有左孩子）；然后在第二阶段中对单链结构通过几个批次左旋转（left rotations）生成一颗完全二叉树。为了生成完全二叉树，在第二阶段的左旋转中，首先只将一部分节点左旋转（这算是第一个批次左旋转），然后依次对剩下的单链节点做多批次左旋转（每个批次的左旋转所针对的节点位于剩下的vine上依次相隔的一个节点），直到某个批次的左旋转次数不大于1。

实现代码：

import java.util.ArrayList;<br /> import java.util.LinkedList;<br /> import java.util.List;<br /> /**<br /> * DSW(Day-Stout-Warren) algorithm to balance a binary search tree<br /> *<br /> * @author ljs<br /> * see also: http://penguin.ewu.edu/~trolfe/DSWpaper/<br /> */<br /> public class DSW_BST {<br /> static class Node{<br /> int val;<br /> Node left;<br /> Node right;<br /> public Node(int val){<br /> this.val = val;<br /> }<br /> public String toString(){<br /> return String.valueOf(val);<br /> }<br /> }<br /> //the number of nodes in this tree<br /> private int n;</p> <p> //phase one: right rotate the input tree into a vine<br /> //return the root of the elongated tree; and compute the nodes count<br /> private Node createVine(Node root){</p> <p> Node pseudoRoot = new Node(Integer.MIN_VALUE);<br /> Node grandpar = pseudoRoot;</p> <p> Node tmp = root;<br /> int nodeCnt = 0;<br /> while(tmp != null){<br /> if(tmp.left != null){<br /> //right rotation for node tmp.left<br /> Node child = tmp.left;<br /> //postpone grandpar.right update until tmp.left is null<br /> //grandpar.right = child;<br /> tmp.left = child.right;<br /> child.right = tmp; </p> <p> tmp = child;<br /> }else{<br /> grandpar.right = tmp;</p> <p> //move down<br /> grandpar = tmp;<br /> tmp = tmp.right;<br /> nodeCnt++;<br /> }<br /> }<br /> root = pseudoRoot.right;<br /> n = nodeCnt;<br /> return root;<br /> }<br /> //phase two: balance the vine into a complete BST<br /> //return the new root<br /> private Node createCompleteBST(Node root,int n){<br /> //caculate m = 2^log(n+1) - 1;<br /> int tmp = n + 1;<br /> int m = 1;<br /> tmp>>=1;<br /> while(tmp != 0){<br /> m<<=1;<br /> tmp>>=1;<br /> }<br /> m--;<br /> int leftRotates = n - m;</p> <p> root = leftRotate(root,leftRotates);<br /> while(m>1){<br /> m>>=1; //m = m/2<br /> root = leftRotate(root,m);<br /> }<br /> return root;<br /> }</p> <p> //return the new root after a number of left rotations<br /> private Node leftRotate(Node root,int leftRotates){<br /> Node pseudoRoot = new Node(Integer.MIN_VALUE);<br /> Node grandpar = pseudoRoot;</p> <p> Node tmp = root;<br /> int rotations = 1;<br /> while(tmp != null && tmp.right != null && rotations<=leftRotates){<br /> //left rotate for node tmp.right<br /> Node child = tmp.right;</p> <p> grandpar.right = child;<br /> tmp.right = child.left;<br /> child.left = tmp;</p> <p> tmp = child.right;<br /> grandpar = child;</p> <p> rotations++;<br /> }<br /> return pseudoRoot.right;<br /> }<br /> //return the new root<br /> public Node dswBalance(Node root){<br /> root = createVine(root);<br /> n = this.getNumberOfNodes();<br /> root = createCompleteBST(root,n);<br /> return root;<br /> }</p> <p> public int getNumberOfNodes() {<br /> return n;<br /> }</p> <p> //utility method for test purpose<br /> public static void recursiveInOrderTraverse(Node root){<br /> if(root == null)return;</p> <p> recursiveInOrderTraverse(root.left);<br /> System.out.format(" %d", root.val);<br /> recursiveInOrderTraverse(root.right);<br /> }<br /> //utility method for test purpose<br /> public static void levelTraverseCompleteBST(Node root,int n){<br /> LinkedList<Node> queue = new LinkedList<Node>();</p> <p> List<List<Node>> nodesList = new ArrayList<List<Node>>();</p> <p> queue.add(root);<br /> int level=0;<br /> int levelNodes = 1;<br /> int nextLevelNodes = 0;<br /> //System.out.format("%nLevel %d:",level);<br /> List<Node> levelNodesList = new ArrayList<Node>();<br /> while(!queue.isEmpty()) {<br /> Node node = queue.remove();</p> <p> if(levelNodes==0){<br /> //save the prev. level's nodes list<br /> nodesList.add(levelNodesList);<br /> levelNodesList = new ArrayList<Node>(); </p> <p> level++;<br /> //System.out.format("%nLevel %d:",level);<br /> levelNodes = nextLevelNodes;<br /> nextLevelNodes = 0;<br /> }</p> <p> levelNodesList.add(node);<br /> //System.out.format(" %d", node.val);<br /> if(node.left != null){<br /> queue.add(node.left);<br /> nextLevelNodes++;<br /> }<br /> if(node.right != null) {<br /> queue.add(node.right);<br /> nextLevelNodes++;<br /> }</p> <p> levelNodes--;<br /> }<br /> //save the last level's nodes list<br /> nodesList.add(levelNodesList);</p> <p> int maxLevel = nodesList.size()-1; //==level<br /> //expected max level for a complete binary tree = ceiling(log(n+1) - 1)<br /> int expectedMaxLevel = (int)Math.ceil(Math.log1p(n) / Math.log(2)) - 1;<br /> System.out.format("%n[expected max level: %d; real max level: %d]%n", expectedMaxLevel,maxLevel);</p> <p> //Note: expected max columns: 2^(level+1) - 1<br /> int cols = 1;<br /> for(int i=0;i<=maxLevel;i++){<br /> cols <<= 1;<br /> }<br /> cols--;<br /> Node[][] tree = new Node[maxLevel+1][cols];</p> <p> //load the tree into an array for later display<br /> for(int currLevel=0;currLevel<=maxLevel;currLevel++){<br /> levelNodesList = nodesList.get(currLevel);<br /> //Note: the column for this level's j-th element: 2^(maxLevel-level)*(2*j+1) - 1<br /> int tmp = maxLevel-currLevel;<br /> int coeff = 1;<br /> for(int i=0;i<tmp;i++){<br /> coeff <<= 1;<br /> }<br /> for(int j=0;j<levelNodesList.size();j++){<br /> int col = coeff*(2*j + 1) - 1;<br /> tree[currLevel][col] = levelNodesList.get(j);<br /> }<br /> }</p> <p> //display the binary search tree<br /> for(int i=0;i<=maxLevel;i++){<br /> for(int j=0;j<cols;j++){<br /> Node node = tree[i][j];<br /> if(node == null)<br /> System.out.format(" ");<br /> else<br /> System.out.format("%2d",node.val);<br /> }<br /> System.out.format("%n");<br /> }<br /> }<br /> public static void main(String[] args) {<br /> /*<br /> 13<br /> 10 25<br /> 2 12 20 35<br /> 29<br /> 30<br /> 31<br /> 32<br /> 33<br /> */<br /> System.out.format("Test case 1:%n");<br /> Node n13 = new Node(13);<br /> Node n10 = new Node(10);<br /> Node n25 = new Node(25);<br /> Node n2 = new Node(2);<br /> Node n12 = new Node(12);<br /> Node n20 = new Node(20);<br /> Node n35 = new Node(35);<br /> Node n29 = new Node(29);<br /> Node n30 = new Node(30);<br /> Node n31 = new Node(31);<br /> Node n32 = new Node(32);<br /> Node n33 = new Node(33);</p> <p> n13.left = n10;<br /> n13.right = n25;<br /> n10.left = n2;<br /> n10.right = n12;<br /> n25.left = n20;<br /> n25.right = n35;<br /> n35.left = n29;<br /> n29.right = n30;<br /> n30.right = n31;<br /> n31.right = n32;<br /> n32.right = n33;</p> <p> Node root = n13;<br /> System.out.format("%nBefore being balanced, in-order BST:%n");<br /> DSW_BST.recursiveInOrderTraverse(root);</p> <p> DSW_BST dsw = new DSW_BST();<br /> root = dsw.dswBalance(root);</p> <p> System.out.format("%nAfter being balanced, in-order BST:%n");<br /> DSW_BST.recursiveInOrderTraverse(root);</p> <p> System.out.format("%n%n%nAfter being balanced, it is now a complete BST:");<br /> DSW_BST.levelTraverseCompleteBST(root,dsw.getNumberOfNodes());</p> <p> System.out.format("************************************");<br /> System.out.format("%nTest case 2:%n");</p> <p> Node nn5 = new Node(5);<br /> Node nn10 = new Node(10);<br /> Node nn20 = new Node(20);<br /> Node nn15 = new Node(15);<br /> Node nn30 = new Node(30);<br /> Node nn25 = new Node(25);<br /> Node nn40 = new Node(40);<br /> Node nn23 = new Node(23);<br /> Node nn28 = new Node(28);</p> <p> nn5.right = nn10;<br /> nn10.right = nn20;<br /> nn20.left = nn15;<br /> nn20.right = nn30;<br /> nn30.left = nn25;<br /> nn30.right = nn40;<br /> nn25.left = nn23;<br /> nn25.right = nn28;</p> <p> root = nn5;<br /> System.out.format("%nBefore being balanced, in-order BST:%n");<br /> DSW_BST.recursiveInOrderTraverse(root);</p> <p> dsw = new DSW_BST();<br /> root = dsw.dswBalance(root);</p> <p> System.out.format("%nAfter being balanced, in-order BST:%n");<br /> DSW_BST.recursiveInOrderTraverse(root);</p> <p> System.out.format("%n%n%nAfter being balanced, it is now a complete BST:");<br /> DSW_BST.levelTraverseCompleteBST(root,dsw.getNumberOfNodes());<br /> }<br /> }<br />

测试

Test case 1:

Before being balanced, in-order BST:
 2 10 12 13 20 25 29 30 31 32 33 35
After being balanced, in-order BST:
 2 10 12 13 20 25 29 30 31 32 33 35

After being balanced, it is now a complete BST:
[expected max level: 3; real max level: 3]
                   30             
        13                 33     
  10        25       32      35 
 2  12  20  29  31           
************************************
Test case 2:

Before being balanced, in-order BST:
 5 10 15 20 23 25 28 30 40
After being balanced, in-order BST:
 5 10 15 20 23 25 28 30 40

After being balanced, it is now a complete BST:
[expected max level: 3; real max level: 3]
                  25             
        20              30     
   10      23      28      40 
 5  15