問題タブ [binary-tree]

今朝、私はSteve Yegge の: When Polymorphism Failsを読んでいたとき、彼の同僚が Amazon での面接に来た潜在的な従業員に尋ねていた質問に出くわしました。

実際のポリモーフィズムの例として、古典的な「eval」インタビューの質問を見てみましょう。これは (私の知る限り) Ron Braunstein によって Amazon にもたらされました。OOP 設計、再帰、バイナリ ツリー、ポリモーフィズムとランタイム タイピング、一般的なコーディング スキル、および (さらに難しくしたい場合は) 解析理論など、さまざまな重要なスキルを調べることができるため、この質問は非常に豊富です。 .

ある時点で、志願者は、「+」、「-」、「*」、「/」などの二項演算子のみを使用していると仮定して、算術式を二分木として表現できることに気付きます。リーフ ノードはすべて数値であり、内部ノードはすべて演算子です。式を評価することは、木を歩くことを意味します。候補者がこれに気付いていない場合は、そっと誘導するか、必要に応じて伝えることができます。

と言ってしまっても、やはり面白い問題です。

質問の前半は、一部の人々 (名前は息が詰まるまで守りますが、イニシャルはウィリー・ルイスです) は、自分自身を開発者と呼んで Amazon で働きたい場合の仕事の要件であると感じていますが、実際にはちょっと難しいです。 . 問題は、「2 + (2)」などの算術式 (文字列など) から式ツリーにどのように移行するかです。ある時点で、この質問に対する ADJ チャレンジが行われる可能性があります。

後半は、これが 2 人のプロジェクトで、あなたのパートナー ("ウィリー" と呼びます) が文字列式をツリーに変換する責任があるとしましょう。簡単な部分を取得します。ウィリーがツリーを構築するクラスを決定する必要があります。任意の言語で実行できますが、いずれかを選択するようにしてください。そうしないと、ウィリーがアセンブリ言語を渡してくれます。彼が気難しいと感じているのは、もはや生産されていないプロセッサーのためでしょう。

どれだけ多くの候補者がこれを好んでいるかに驚かれることでしょう。

答えは言いませんが、Standard Bad Solution には、switch または case ステートメント (または単に古き良きカスケード if) の使用が含まれます。Slightly Better Solution には、関数ポインターのテーブルの使用が含まれ、おそらく最善の解決策には、ポリモーフィズムの使用が含まれます。いつかやり遂げることをお勧めします。楽しいもの！

それでは、3 つの方法すべてで問題に取り組みましょう。"2 + (2)" などの算術式 (文字列など) から、カスケード if、関数ポインターのテーブル、および/またはポリモーフィズムを使用した式ツリーにどのように移行しますか?

1 つ、2 つ、または 3 つすべてに自由に取り組んでください。

[更新: ほとんどの回答に一致するようにタイトルを変更しました。]

最近読んだいくつかの本で二分木と二分探索について言及されているのを見てきましたが、私はまだコンピュータ サイエンスの研究を始めたばかりなので、アルゴリズムとデータを実際に扱うクラスをまだ受講していません。深刻な方法で構造。

典型的な情報源 (ウィキペディア、Google) を確認しましたが、(特に) 赤黒木の有用性と実装に関するほとんどの説明は、密集していて理解しにくいものでした。必要なバックグラウンドを持っている人にとっては完全に理にかなっていると思いますが、現時点ではほとんど外国語のように読めます.

では、プログラミング中に自分が行っている一般的なタスクのいくつかで、二分木が役立つのはなぜでしょうか? それ以外に、どのツリーを使用することを好みますか (サンプル実装を含めてください)、その理由は何ですか?

berkeley-db Java 版と機能的に類似した、純粋な .Net 永続ハッシュテーブル/バイナリツリーが必要です。

機能的には、memcached や速度などの DHT と同様の方法で動作する必要がありますが、分散する必要はありません。本質的に、永続的なハッシュテーブルを探しています。

アイデアや提案はありますか？

同様の質問もここにあります: Looking for a simple standalone persistent dictionary implementation in C#

ポール

BST（二分探索木）でルートからリーフへの最短パスを見つけるための最も簡単な方法は、できれば再帰を使用することです。Javaが好まれ、擬似コードは大丈夫です。

ありがとう！

わかりました、これは周りの CS 関係者のための理論領域のもう 1 つの問題です。

90 年代、私は BST の実装でかなりうまくいきました。私が理解できなかった唯一のことは、バイナリ ツリー (AVL) のバランスをとるアルゴリズムの複雑さでした。

これについて私を助けてもらえますか？

再帰を使用した二分探索木のトラバーサルの作成。

これが関数です。これは明らかに間違っています。この関数は次のように呼び出されます。

最初はオブジェクトで、print vals は単にオブジェクト内のデータを出力する関数です。各オブジェクトには、data、left、right の 3 つの値があります。関数を使用してこれらのアイテムに実際にアクセスするにはどうすればよいですか?

わかりました、再帰によってこのトラバーサルを作成しようとしています。私は実際にこの問題を以前に投稿しましたが、関数ポインターを使用しなければならなかったため、間違っていました。私は自分が何をすべきか理解していません。私はプライベートなものを呼び出すパブリックラッパーを持っています...しかし、パブリックのものは関数が渡されるものなので、それで何をすればよいですか?? 私は頭が悪いので、誰かが私に小さなヒントをくれたとしても、私はそれを理解すると確信しています. ここからどこへ行けばいいのかわかりません。

それを呼び出すコードの例は次のとおりです。

だから私のコードは以下です。エラーは発生せず、すべてがノードに正常に配置されます。しかし、私のデバッグステートメントに基づいて、何かが挿入されるたびにルートを見つけています。それが正しいかどうかはわかりません。しかし、割り当ての出力ファイルによると、ツリーの高さ、トラバーサルに関しては私の答えが異なり、葉のカウント機能にまだ問題があります。別の話ですが。

デバッグ ステートメントに基づくと、すべてが正しい方向に進んでいるように見えます。しかし、新鮮な目が必要かもしれないと思います。Inorder、preorder、および postorder に影響を与えるノードをどこで処理しているかだけの問題であるため、トラバーサルがどのように変化するかはまったくわかりません。

インサートが実際に問題ない場合に備えて、高さ関数は次のとおりです。

上の画像は、ウィキペディアが不均衡であると示している「AVLツリーに関するウィキペディアのエントリ」からのものです。この木はどうしてまだバランスが取れていないのですか？記事からの引用は次のとおりです。

ノードのバランス係数は、右側のサブツリーの高さから左側のサブツリーの高さを引いたものであり、バランス係数が1、0、または-1のノードはバランスが取れていると見なされます。他のバランス係数を持つノードは不均衡と見なされ、ツリーのバランスを取り直す必要があります。バランス係数は、各ノードに直接格納されるか、サブツリーの高さから計算されます。

左と右の両方のサブツリーの高さは4です。左のツリーの右のサブツリーの高さは3ですが、それでも4より1つ少ないだけです。誰かが私が欠けているものを説明できますか？

ここの誰かがスキップリストを使ったことがあるかどうか疑問に思います。平衡二分木とほぼ同じ利点があるように見えますが、実装は簡単です。持っている場合、あなたはあなた自身を書いたのですか、それとも事前に書かれたライブラリを使用しましたか（もしそうなら、その名前は何でしたか）？