algorithm
バイナリ検索ツリー

前書き

バイナリ検索ツリー - 挿入（Python）

これは、Pythonを使用したバイナリ検索ツリー挿入の簡単な実装です。

例を以下に示します。

コードスニペットに続いて、各画像はこのコードがどのように動作するかを視覚化しやすくする実行視覚化を示しています。

class Node:
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.data = val

def insert(root, node):
    if root is None:
        root = node
    else:
        if root.data > node.data:
            if root.l_child is None:
                root.l_child = node
            else:
                insert(root.l_child, node)
        else:
            if root.r_child is None:
                root.r_child = node
            else:
                insert(root.r_child, node)

def in_order_print(root):
    if not root:
        return
    in_order_print(root.l_child)
    print root.data
    in_order_print(root.r_child)

def pre_order_print(root):
    if not root:
        return        
    print root.data
    pre_order_print(root.l_child)
    pre_order_print(root.r_child)    

バイナリ検索ツリー - 削除（C ++）

削除を開始する前に、BSTの各ノードに最大2つのノード（左右の子）を持つことができるバイナリ検索ツリー（BST）にいくつかのライトを入れたいだけです。ノードの左のサブツリーにはその親ノードのキー以下のキーノードの右側のサブツリーには、親ノードのキーより大きなキーがあります。

バイナリ検索ツリーのプロパティを維持しながらツリー内のノードを削除する。

ノードを削除する際に考慮すべき3つのケースがあります。

• ケース1：削除するノードはリーフノード（値22のノード）です。
• ケース2：削除されるノードには1つの子があります（値が26のノード）。
• ケース3：削除するノードに両方の子がある（値49のノード）。

ケースの説明：

1. 削除されるノードが葉ノードである場合、単純にノードを削除し、 nullptrをその親ノードに渡す。
2. 削除するノードに子が1つしかない場合は、子値をノード値にコピーして子を削除します（ケース1に変換）
3. 削除するノードに2つの子ノードがある場合、右のサブツリーからの最小値をノードにコピーし、ノードの右サブツリーから最小値を削除することができます（ケース2に変換）

注意：右のサブツリーの最小値は最大1つの子を持つことができます。また、それが左の子を持っている場合は最小値でないか、またはBSTプロパティに従わないことを意味します。

ツリー内のノードの構造と削除用のコード：

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

上記のコードの時間複雑度はO（ h ）です。ここで、 hはツリーの高さです。

BSTの最低共通祖先

BSTを考えてみましょう：

22と26の最低共通祖先は24です

26と49の最も低い共通祖先は46です

22と24の最も低い共通祖先は24です

バイナリ検索ツリープロパティを使用して、最も低い祖先ノードを見つけることができます

擬似コード：

lowestCommonAncestor(root,node1, node2){

if(root == NULL)    
return NULL;



 else if(node1->data == root->data || node2->data== root->data)    
    return root;
    
    else if((node1->data <= root->data && node2->data > root->data)
              || (node2->data <= root->data && node1->data > root->data)){
        
             return root;
    }
    
    else if(root->data > max(node1->data,node2->data)){
            return lowestCommonAncestor(root->left, node1, node2);
    }
        
        else {
            return lowestCommonAncestor(root->right, node1, node2);
      }
        }

バイナリ検索ツリー - Python

class Node(object):
    def __init__(self, val):
        self.l_child = None
        self.r_child = None
        self.val = val


class BinarySearchTree(object):
    def insert(self, root, node):
        if root is None:
            return node

        if root.val < node.val:
            root.r_child = self.insert(root.r_child, node)
        else:
            root.l_child = self.insert(root.l_child, node)

        return root


    def in_order_place(self, root):
        if not root:
            return None
        else:
            self.in_order_place(root.l_child)
            print root.val
            self.in_order_place(root.r_child)

    def pre_order_place(self, root):
        if not root:
            return None
        else:
            print root.val
            self.pre_order_place(root.l_child)
            self.pre_order_place(root.r_child)

    def post_order_place(self, root):
        if not root:
            return None
        else:
            self.post_order_place(root.l_child)
            self.post_order_place(root.r_child)
            print root.val

"" "異なるノードを作成してデータを挿入する" "

r = Node(3)
node = BinarySearchTree()
nodeList = [1, 8, 5, 12, 14, 6, 15, 7, 16, 8]

for nd in nodeList:
    node.insert(r, Node(nd))

print "------In order ---------"
print (node.in_order_place(r))
print "------Pre order ---------"
print (node.pre_order_place(r))
print "------Post order ---------"
print (node.post_order_place(r))