区块链智能交易solidity语言实现AVL-tree插入

智能交易区块链solidity语言编写二叉平衡搜索树（AVL-tree）

AVL 树的难点在于四种旋转，solidity的难点在于此语言不存在指针，只能用mappping和下标来充当指针的形式。这对于树的创建增加了难度。

四种旋转

(1) LL：LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。

(2) LR：LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。

(3) RL：RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。

(4) RR：RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。

LL 的旋转

image.png

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。
对于LL旋转，你可以这样理解为：LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着"左孩子，即k1"使劲摇。将k1变成根节点，k2变成k1的右子树，"k1的右子树"变成"k2的左子树"。

RR的旋转

image.png

图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

LR的旋转

image.png

第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"。

RL的旋转

image.png

第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"。

目前只需要考虑AVL树插入的代码，搜索代码实现十分简单

pragma solidity ^0.4.0;

contract test{
    struct node{
        uint key;
        uint left;
        uint right;
        uint height;
    }
    mapping(uint => node) nodes;
    uint root=0;
    
    function height(uint n)public returns (uint r){
        if(n == 0){
            return 0;
        }else{
            return nodes[n].height;
        }
    }
    
    function max(uint a,uint b)public returns(uint r){
        if(a > b)
        return a;
        else 
        return b;
    }
    
    function leftleftrotation(uint k2) public returns(uint r){
        uint k1;
        k1 = nodes[k2].left;
        nodes[k2].left = nodes[k1].right;
        nodes[k1].right = k2;
        
        nodes[k2].height = max(height(nodes[k2].left),height(nodes[k2].right))+1;
        nodes[k1].height = max(height(nodes[k1].left),height(nodes[k1].right))+1;
        return k1;
    }
    
    function rightrightrotation(uint k1)public returns(uint r){
        uint k2;
        k2 = nodes[k1].right;
        nodes[k1].right = nodes[k2].left;
        nodes[k2].left = k1;
        
        nodes[k1].height = max(height(nodes[k1].left),height(nodes[k1].right))+1;
        nodes[k2].height = max(height(nodes[k2].right),height(nodes[k2].left))+1;
        return k2;
    }
    
    function leftrightrotation(uint k3)public returns(uint r){
        nodes[k3].left = rightrightrotation(nodes[k3].left);
        return leftleftrotation(k3);
    }
    
    function rightleftrotation(uint k1)public returns(uint r){
        nodes[k1].right = leftleftrotation(nodes[k1].right);
        return rightrightrotation(k1);
    }
    
    
    function _insert(uint n,uint key)internal returns(uint r){
        if(n==0){
            n = key;
            nodes[n] = node(key,0,0,0);
        }
        else{
            if(key < nodes[n].key){
                nodes[n].left = _insert(nodes[n].left,key);
                
                if(height(nodes[n].left)-height(nodes[n].right)==2){
                    if(key < nodes[nodes[n].left].key){
                        n = leftleftrotation(n);
                    }else{
                        n = leftrightrotation(n);
                    }
                }
                
            }
            else if(key > nodes[n].key){
                nodes[n].right = _insert(nodes[n].right,key);
                
                if(height(nodes[n].right)-height(nodes[n].left)==2){
                    if(key > nodes[nodes[n].right].key){
                        n = rightrightrotation(n);
                    }else{
                        n = rightleftrotation(n);
                    }
                }
            }
        }
        nodes[n].height = max(height(nodes[n].left),height(nodes[n].right))+1;
        return n;
    }
    function insert(uint key)public returns(uint r){
        root = _insert(root,key);
        return root;
    }
    function insertlist(uint[] keys)public{
        for(uint i=0;i<keys.length;i++){
            root = _insert(root,keys[i]);
        }
    }
}