重学Java设计模式读后感之组合设计模式应用

平衡二叉树

平衡二叉树

平衡二叉树（Balanced Binary Tree）: 通常指的是AVL树或红黑树这类自平衡二叉搜索树。这里我将向你展示如何用Java实现一个简单的AVL树，包括插入节点并自动保持平衡的操作。

AVL树简介

AVL树是一种自平衡的二叉搜索树，任何节点的两个子树的高度最大差别为1。这种性质保证了查找、插入和删除操作可以在O(log n)时间内完成。

Java代码实现

下面是一个简单的AVL树的实现，包括节点定义、插入方法以及旋转方法来保持树的平衡：

class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1; // 新节点默认高度为1
    }
}

public class AVLTree {

    Node root;

    // 获取节点的高度
    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    // 获取两节点的高度差
    int getBalanceFactor(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    // 右旋
    Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新高度
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;

        // 返回新的根节点
        return x;
    }

    // 左旋
    Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新高度
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;

        // 返回新的根节点
        return y;
    }

    // 插入节点
    Node insert(Node node, int key) {
        // 普通的BST插入
        if (node == null)
            return (new Node(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else // 相等值不允许
            return node;

        // 更新节点的高度
        node.height = 1 + Math.max(height(node.left), height(node.right));

        // 获取平衡因子以检查是否失衡
        int balance = getBalanceFactor(node);

        // 如果不平衡，则有4种情况
        // Left Left Case
        if (balance > 1 && key < node.left.key)
            return rotateRight(node);

        // Right Right Case
        if (balance < -1 && key > node.right.key)
            return rotateLeft(node);

        // Left Right Case
        if (balance > 1 && key > node.left.key) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        // Right Left Case
        if (balance < -1 && key < node.right.key) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        // 返回未改变的节点指针
        return node;
    }

    // 主方法用于测试
    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        /* 示例插入 */
        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);
    }
}

这段代码展示了如何创建一个AVL树，并通过旋转操作来保持树的平衡。你可以根据需要扩展这个类，例如添加删除节点的功能或者遍历树的方法。

组合设计模式

把相似的对象或方法组合成一组可以被调用的结构树对象的设计思路,称为组合设计模式.

场景

根据性别、年龄的不同组合,发放不同类型的优惠卷

业务模型

为了把不同类型的决策节点和最终的优惠卷组装成一个可被运行的决策树,需要做适配设计和工程方法调用,具体会体现在定义接口和抽象类、初始化配置决策节点(性别、年龄)上.

定义抽象类,抽取的是抽象的名词； 定义接口,抽取的是抽象的动词

UML类

构建Tree节点

{
    "treeNodeMap": {
        "1": {
            "nodeType": 1,
            "ruleDesc": "用户性别[男/女]",
            "ruleKey": "userGender",
            "treeId": 10001,
            "treeNodeId": 1,
            "treeNodeLinkList": [
                {
                    "nodeIdFrom": 1,
                    "nodeIdTo": 11,
                    "ruleLimitType": 1,
                    "ruleLimitValue": "man"
                },
                {
                    "nodeIdFrom": 1,
                    "nodeIdTo": 12,
                    "ruleLimitType": 1,
                    "ruleLimitValue": "woman"
                }
            ]
        },
        "11": {
            "nodeType": 1,
            "ruleDesc": "用户年龄",
            "ruleKey": "userAge",
            "treeId": 10001,
            "treeNodeId": 11,
            "treeNodeLinkList": [
                {
                    "nodeIdFrom": 11,
                    "nodeIdTo": 111,
                    "ruleLimitType": 3,
                    "ruleLimitValue": "25"
                },
                {
                    "nodeIdFrom": 11,
                    "nodeIdTo": 112,
                    "ruleLimitType": 5,
                    "ruleLimitValue": "25"
                }
            ]
        },
        "12": {
            "nodeType": 1,
            "ruleDesc": "用户年龄",
            "ruleKey": "userAge",
            "treeId": 10001,
            "treeNodeId": 12,
            "treeNodeLinkList": [
                {
                    "nodeIdFrom": 12,
                    "nodeIdTo": 121,
                    "ruleLimitType": 3,
                    "ruleLimitValue": "25"
                },
                {
                    "nodeIdFrom": 12,
                    "nodeIdTo": 122,
                    "ruleLimitType": 5,
                    "ruleLimitValue": "25"
                }
            ]
        },
        "111": {
            "nodeType": 2,
            "nodeValue": "果实A",
            "treeId": 10001,
            "treeNodeId": 111
        },
        "112": {
            "nodeType": 2,
            "nodeValue": "果实B",
            "treeId": 10001,
            "treeNodeId": 112
        },
        "121": {
            "nodeType": 2,
            "nodeValue": "果实C",
            "treeId": 10001,
            "treeNodeId": 121
        },
        "122": {
            "nodeType": 2,
            "nodeValue": "果实D",
            "treeId": 10001,
            "treeNodeId": 122
        }
    },
    "treeRoot": {
        "treeId": 10001,
        "treeName": "规则决策树",
        "treeRootNodeId": 1
    }
}