ツリー(Tree)

★木

ノードがツリーとして接続される構造をツリー構造と呼び,意図的に示す.ツリー内の各要素はノードです.上の図に示すように、ノードは親ノードと子ノードとして接続されています.

ルート(root):ツリーの開始部分.ルートを使用してツリーに移動します.

葉:帯のない部分.

幹線(edge):2つのノードを接続する線.ルートからの幹線の数に応じてレベルを分けます.

完全な木と正の木

Every non leaf has two children except for the last row & the last row is filled left -> right
完全ツリー(Complete Tree):すべてのリーフのノードに2つのサブノードがあるわけではありません.最後の行は左から右に順番に埋め込まれたツリーです.

Every non leaf has two children & all the leaves are on the same level
フルツリー(Full Tree):すべてのリーフのノードに2つのサブノードがあるわけではありません.すべてのリーフが同じレベルのツリーです.

ツリーループ方式

プリアンブルループ:ルートノードから左サブノード、右サブノードへのループ方法.ルートノードは、他のすべてのノードを通過する前にアクセスされるため、名前には「前」(Pre)が含まれます.

中位数ループ:左側のサブノードからルートノード、右側のサブノードへのループ方法.

後方ループ(Post orderループ):左側のサブノードから右側のサブノード、さらにルートノードへのループ方法.

幅優先順位(Breadth first traversal/level order traversal):一番上のノードから左から右への順序.

ツリーを削除する方法

サブノードの数に応じて、ツリー内の特定の要素を削除します.
1.リーフノードを除去する場合
ノードの親ノードのポインタをnullに設定できます.
2.サブノードが1つあるノードを削除する
ノードの親ノードのポインタを子ノードに向けるだけです.親ノードで使用するポインタと同じポインタ(左、右)を使用する必要があります.
3.2つのサブノードを持つノードを削除する
「中尉」の後続メンバーと「中尉」の上級メンバーと位置を交換し、リーフノードを削除します.
中位継承者(順序継承者):削除するノードから1回左に下がり、右に下がり続けるリーフノード.中尉の後継者は、削除するノードの中で最も小さいノードの中で最も大きいノードです.
(中尉がナビゲーションノードを巡回する場合、ルートノードにアクセスする前に遭遇するノードであるため、中尉後続ノードと呼ばれる.)
上級マネージャ(in order predessor):削除するノードから右に1回下がり、左に下がるリーフノードを続けます.アドバンスドマネージャは、削除するノードよりも大きいノードの中で最も小さいノードです.

ツリーの回転

バランスのとれたツリーを作成するには、ツリー内でノードの位置を変更するプロセスを回転と呼びます.
[接続](Connection)リストに示すように、一方向にリストされたツリーはアンバランスを表します.バランスツリーでは、特定の要素をナビゲートする時間の複雑さはO(logn)であり、バランスツリーでは接続リストなどのO(n)である.したがって、データを効率的に管理するには、ツリーをバランスさせる必要があります.
親ノード、親ノード、子ノードのサイズ関係に基づいて右または左に曲がります.ツリーを並べ替える場合、中程度のサイズの要素は常に一番上のルート要素です.

1.左側のサブツリーでアンバランスが発生した場合

サイズ関係は(親ノード)>(親ノード)>(子ノード)です.右に曲がると、親ノードを親ノードの右側の子ノードの位置に移動します.

2.右サブツリーでアンバランスが発生した場合

サイズ関係は(親ノード)<(親ノード)<(子ノード)です.左に曲がると、親ノードを親ノードの左側の子ノードの位置に移動します.

3.木が片方に偏っていなければ

右側のサブアイテムの左側のサブツリーに

のアンバランスが現れると、

になります.

サイズ関係は(親ノード)>(子ノード)>(祖父母ノード)です.子ノードを右に曲がって、親ノードを左に曲がって、親ノードを親ノードの左側の子ノードの位置に移動します.

のアンバランスが左側のサブアイテムの右側のサブツリーに現れる場合、

.

サイズ関係は(親ノード)>(祖父母ノード)>(子ノード)です.子ノードを左に曲がって右に曲がって、親ノードを親ノードの右側の子ノードの位置に移動します.

インプリメンテーション

public class Tree<E> {
    class Node<E> {
        E data;
        Node<E> left, right;

        public Node(E obj) {
            this.data = obj;
            left = right = null;
        }
    }

    private Node<E> root;
    private int currentSize = 0;

    public void add(E obj, Node<E> node) {
        if (((Comparable<E>) obj).compareTo(node.data) > 0) {
            // 비교한 수보다 크면 오른쪽으로
            if (node.right == null) {
                node.right = new Node<E>(obj);
                return;
            }
            add(obj, node.right);
        }
        // 위에서 오른쪽으로 안갔을 경우, 왼쪽
        if (node.left == null) {
            node.left = new Node<E>(obj);
            return;
        }
        add(obj, node.left);
    }

    // 이 메서드를 통해서 위의 메서드를 접근
    public void add(E obj) {
        if (root == null)
            root = new Node<E>(obj);
        else
            add(obj, root);
        currentSize++;
    }

    // 특정 원소 포함됐는지 여부
    public boolean contains(E obj, Node<E> node) {
        // 끝에 도달했는데 null이면 없다
        if (node == null)
            return false;
        // node의 data와 일치
        if (((Comparable<E>) obj).compareTo(node.data) == 0)
            return true;
        // 비교해서 오른쪽 혹은 왼쪽 이동
        if (((Comparable<E>) obj).compareTo(node.data) > 0)
            return contains(obj, node.right);
        return contains(obj, node.left);
    }

    // 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
    public Node<E> leftRotate(Node<E> node) {
        Node<E> tmp = node.right; // set temp=grandparents right child
        node.right = tmp.left; // set grandparents right child=temp left child
        tmp.left = node; // set temp left child=grandparent
        return tmp; // use temp instead of grandparent
    }

    // 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮깁니다.
    public Node<E> rightRotate(Node<E> node) {
        Node<E> tmp = node.left;
        node.left = tmp.right;
        tmp.right = node;
        return tmp;
    }

    // 우측 회전 후 좌측 회전
    public Node<E> rightLeftRotate(Node<E> node) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    // 좌측 회전 후 우측 회전
    public Node<E> leftRightRotate(Node<E> node) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
}