algorithm
バイナリ検索ツリー
サーチ…
前書き
バイナリツリーは、各ノードに最大2つの子があるツリーです。バイナリ検索ツリー(BST)は、その要素が特別な順序で配置されたバイナリツリーです。各BSTでは、左のサブツリーのすべての値(つまりキー)が右のサブツリーの値よりも小さい。
バイナリ検索ツリー - 挿入(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のノード)。
ケースの説明:
- 削除されるノードが葉ノードである場合、単純にノードを削除し、
nullptr
をその親ノードに渡す。 - 削除するノードに子が1つしかない場合は、子値をノード値にコピーして子を削除します(ケース1に変換)
- 削除するノードに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))
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow